책 이야기

169와 961은 모두 소수의 제곱이다. 169를 반대로 하면 961이 된다.

다음 조건을 만족하면 reversible prime square(가역 소수 제곱)이라 부른다:

1. 회문(palindrome)이 아니며,
2. 소수의 제곱이며,
3. 반대로 한 것도 소수의 제곱이다.

169와 961은 회문이 아니며, 소수의 제곱을 반대로 한 것이다.

처음 50개 reversible prime square의 합계를 구하시오.

--------------------------------------------------------------------------

프로그램은 어렵지 않게 구성 가능한데, reversible prime square를 만족하는 숫자를 50개 찾는 것이 쉽지 않았다.

50개가 나올때까지 매번 소수를 추가로 만드는 경우 시간이 많이 소요될 것으로 보여서, 일정한 갯수의 소수와 소수의 제곱수 리스트를 먼저 만들어 놓고, 회문이 아니고, 순서를 반대로 한 것도 소수의 제곱수 리스트에 있는 것들을 따로 모으도록 구현했다.

100자리 중 2개, 1000자리 중 2개 등 생각보다 위 조건을 만족하는 숫자가 많이 나오지 않아서, 처음 소수를 만드는 갯수를 계속 키워가며 구해야 했다. 천만의 제곱까지 구해도 50개가 되지 않는다.

문제에서 요구한 조건을 만족하는 reversible prime square가 모두 홀수 자릿수의 숫자인 것은 의아했다. 확실한 이유가 생각되면 짝수 자릿수의 prime square는 검증과정을 생략하도록 해서 성능을 높을 수도 있을 것 같은데, 짝수 자릿수의 숫자가 없는 이유가 명확하게 떠오르지는 않아서 일단 모든 숫자를 대상으로 검증하게 했다.

일단 답은 구했지만 시간이 많이 걸렸다. 검색 끝에 찾은 몇가지 추가 조건은, △끝자리에 올 수 있는 수가 홀수이며 이 중 5의 배수인 5 제외, 1, 3, 7, 9의 제곱수는 1, 9이므로, 첫자리와 끝자리는 1, 9만 올 수 있으며, △첫자리에 1,9만 올 수 있으므로 제곱근은 1,3이 되고 이 경우 3자리 제곱은 5자리, 4자리 제곱은 7자리와 같이 홀수 자릿수로만 나오게 된다. 앞에서 얘기한 홀수 자릿수로만 reversible prime square가 나오는 이유를 알게 되었다.

그리고, 처음에는 소수의 제곱수 목록을 구해서(조건2) 그것을 대상으로 회문과 반대수를 구했는데(조건1,3), 제곱수를 구할 때 추가로 발견한 2가지 조건과 회문까지 판별해서 목록을 만들고(조건1,2), 반대수가 제곱수인 소수이면 정답 목록에 추가하는 방식으로 바꿔서 검증대상을 줄여봤다.

추가로 발견한 2가지 조건으로 검증대상이 500만개 이상에서 40만개 이하로 줄어 실행시간도 많이 개선되었지만, 검증대상 거의 마지막에 가서야 50개를 찾을 수 있어 실행시간은 여전히 필요했다.

작아지지 않는 정수의 수열인 a_n은 다음 과정을 통해 양의 실수 θ에서 만들어 낼 수 있다.

    b₁=θ

    b_n=└b_n-1┘(b_n-1-└_bn-1┘+1) , n>=2일 때

    a_n=└b_n┘

└ ┘은 버림을 나타낸다.

예를 들어, θ=2.956938891377988...는 피보나치 수열(2, 3, 5, 8, 13, 21, 34, 55, 89, ...)를 생성한다.

양의 정수의 수열인 a_n을 연결하면, τ로 표기하는 a₁에서 시작해서 소숫점 아래의 연속된 요소를 결합한 a₁.a₂a₃a₄...모양의 실수가 된다.

예를 들어, θ=2.956938891377988...에서 나오는 피보나치 순열을 연결하면 τ=2.3581321345589...가 되며, θ 값에 대해 θ와 τ는 다르다.

a₁=2에서 시작해서 수열을 결합했을 때 τ=θ가 되는 유일한 값 θ를 찾으시오. 답안은 반올림하여 소숫점 24자리까지 구하시오.

--------------------------------------------------------------------------

처음에는 고민을 많이 하고 접근했는데, 생각보다 어렵지 않게 해결 가능했다.

처음에는 θ=2로 시작해서, 공식을 소숫점 25자리까지 반복 적용해서 나온 숫자(τ)를 다시 θ로 설정하는 작업을 τ=θ가 나올때까지 반복하면 되는데 몇 번 반복하지 않고 답을 구할 수 있었다.

피터는 (피라미드 모양) 4면 주사위 9개를 가지고 있고, 각 주사위 면에는 1,2,3,4가 적혀 있다.

콜린은 (정육면체 모양) 6면 주사위 6개를 가지고 있고, 각 주사위 면에는 1,2,3,4,5,6이 적혀 있다.

피터와 콜린이 주사위를 굴려 합계를 비교해서 합계가 큰 사람이 이긴다. 둘의 합계가 같으면 무승부이다.

4면 주사위를 가진 피터가 콜린을 이길 확률은 얼마인가? 정답을 소숫점 7자리까지 반올림으로 나타내어 0.abcdefg 형태로 제시하시오.

--------------------------------------------------------------------------

처음에 랜덤 함수를 이용하여 둘의 주사위를 생성하고, 합계를 비교하는 몬테카를로 시뮬레이션 방법을 활용하여 천만번 게임을 운영한 승패를 구했는데 답이 맞지 않았다.

그래서 어쩔수 없이 단순하게 전체 경우를 구하는 형태로 접근을 바꿨다. 파이썬 라이브러리의 중복순열(from itertools import production)을 이용하여 피터와 콜린의 경우의 수를 각각 구하고, 그것을 합계로 바꿔 반복문을 통해 두 사람의 모든 경우를 비교하는 형태로 구현했다. 이렇게 설명하면 간단하지만 두 사람의 경우를 곱하면 122억이 넘기 때문에 보기보다 많은 시간이 걸리는 문제였다(몬테카를로 시뮬레이션을 활용하더라도 100억 번은 넘어야 결과에 가까운 답이 나올 수 있다는 뜻으로 이해되었다).

다시 생각해보니, 피터는 9~36, 콜린은 6~36의 합계가 나올 수 있지만 경우의 수는 각각 262,144, 46,656이므로 많은 경우 중복되어 나온다. 앞의 방식처름 122억 회 이상 비교하는 것 보다는 각 값에 대한 발생횟수를 가중치 형태로 만들어서 계산하니 2초 내외에 답을 구할 수 있었다.

문제를 잘못 이해해서 답을 abcdefg 형태로 구했는데 계속 틀리게 나와 알고리즘을 다시 검토하는 등 시간을 많이 소모했는데, 답은 이미 맞게 구했고 '0.abcdefg' 형태로 답을 쓰면 되는 것이었다.

이항계수 (n k)는 위 그림과 같이 파스칼 삼각형이라 불리는 삼각형 형태로 나타낼 수 있다.

파스칼 삼각형의 첫 8줄은 12개의 서로 다른 수로 구성된다: 1, 2, 3, 4, 5, 6, 7, 10, 15, 20, 21, 35.

n이 제곱수로 나눠지지 않으면 양의 정수 n을 squarefree라 부른다. 파스칼 삼각형 첫 8줄의 서로 다른 12개 숫자 중에서 4와 20을 제외하고는 squarefree이다. 첫 8줄에서 sqarefree인 숫자의 합계는 105이다.

파스칼 삼각형 첫 51줄의 서로 다른 squarefree 숫자의 합을 구하시오.

--------------------------------------------------------------------------

생각가능한 몇 개의 단계로 나눠 답을 구했는데 그래도 25초 내외 시간 안에 답을 구할 수 있었다.

처음에는 파스칼 삼각형 모양의 리스트를 만들어가면서 서로 다른 숫자의 리스트를 구했다. 파스칼 삼각형 자체를 만들려고 했는데, 그것이 뒤에 다시 쓰이지 않기 때문에 파스칼 삼각형의 현재 행을 구하면서 서로 다른 숫자는 별도 리스트에 추가하는 형태로 했다.

서로 다른 숫자 리스트를 정렬하고, 그 최대값 이하의 제곱수 리스트를 만들었다. 서로 다른 숫자 리스트의 각 숫자에 대해 제곱수 리스트 숫자로 모듈러 연산(%)을 수행하고, 나머지가 0인 경우는 sqaurefree가 아니므로 해당하는 숫자의 리스트를 만들었다.

마지막으로, 서로 다른 숫자 리스트에서 squarefree가 아닌 숫자를 제외한 숫자를 모두 더해서 합계를 구했다.

그렇게까지 까다로운 문제는 아니었는데 2가지 오류때문에 해결하는데 시간이 좀 걸렸다. 하나는 51줄을 55줄로 잘못 설정해서 발생한 것이었는데 문제를 다시 읽고 해결할 수 있었다. 다른 하나는 2번째 단계에서 처음에는 나머지가 0인 경우에 서로 다른 숫자 리스트에서 해당하는 숫자를 삭제하는 형태로 해서 바로 결과를 구하도록 구성했는데, for문 대상 리스트에서 숫자가 삭제되면서 인덱스 값이 모두 바뀌어서 엉뚱한 연산을 하는 상황이 생겼다. 상황을 보고도 어떤 문제 때문에 생기는 것인지 빨리 인지하지 못해서 오류를 해결하는 데 많은 시간이 걸렸다.

적어도 2개의 소수를 약수로 가지고 있는 수를 합성수라 한다. 예를 들어, 15=3x5, 9=3x3, 12=2x2x3이다.

(서로 다를 필요가 없는) 2개의 소수로 구성된 합성수는 30이하에 10개가 있다:

4, 6, 9, 10, 14, 15, 21, 22, 25, 26

10⁸보다 작은 n에 대해, (서로 다를 필요가 없는) 2개의 소수로 구성된 합성수는 몇 개인가?

--------------------------------------------------------------------------

1억 이하의 숫자 중에 2개 이상의 소수의 곱으로 구성된 합성수가 몇 개인지 묻는 문제이다. 문제에서 (서로 다를 필요가 없는)으로 설명된 부분은 동일한 소수로 곱해도 된다는 뜻이므로, 예시와 같이 9=3x3을 허용하게 구현하면 된다.

빠른 계산을 위해서 1억 이하의 소수 목록을 구하고, 2중 반복문에서 소수끼리 서로 곱하게 해서 목록을 구하고, 파이썬의 집합을 이용해서 중복을 제거해서 구했다. 1억 이하의 소수가 5백만 개 이상 나오더니 목록을 구하면서 메모리 에러가 발생했다. 생각보다 리스트가 커져서 문제가 생긴 것 같았다.

그래서, 결과값 리스트를 만들지 않고, 생성되는 합성수의 갯수를 구하도록 바꿔서 답을 구할 수 있었다. 소수 2개의 곱을 구하는 것이어서 다른 약수가 있을 수 없기 때문에 중복을 제거하는 과정이 필요없었다.