책 이야기

회문인 숫자 595는 다음과 같이 연속된 제곱수의 합계로 나타낼 수 있다는 점에서 흥미롭다.

6²+7²+8²+9²+10²+11²+12²

천 이하에는 연속된 제곱수 합계로 나타낼 수 있는 회문이 11개 있고, 이들의 합계는 4164이다. 주의할 것은 1=0²+1²이지만 양의 정수의 합계를 고려하고 있으므로 해당하지 않는다.

10⁸(1억) 이하의 숫자 중에 회문이면서 연속된 제곱수의 합계로 나타낼 수 있는 숫자의 합을 구하시오.

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

회문은 4번 문제에서 처음 나온 이후에 오일러 프로젝트에 몇 번 나온 문제이고 여기까지 풀었으면 함수로도 가지고 있을 것이다.

일단 문제에서 요구한 대로 구현해 봤다. 1은 제외한다고 했으므로 2에서 1억까지 올라가면서 회문에 해당하는 숫자를 대상으로, 각 숫자가 연속된 제곱수의 합계로 나타낼 수 있는지 판별하는 것이다. 이를 위해 제곱수의 목록을 만들어두고 시작하는 자리를 이동해가면서 차례로 합해나가는 과정을 반복하도록 하고, 제곱수가 비교할 숫자보다 크면 그 수에 대해서는 검증을 중단하도록 했다.

실행해보니 처음에는 빠르지만 천만이 넘어가면서 실행속도가 엄청나게 느려지는 것이 보였다. 하지만 조금 기다려주면 끝이 나는 수준이어서 이렇게 해결하기로 했는데, 제곱수를 1억까지 만들었다가 그것이 넘는 경우가 필요해지면서 거의 마지막에 리스트의 인덱스 에러가 생기고 결과를 확인하지 못했다. 제곱수 리스트를 조금 더 크게 만든 후에 답을 구할 수 있었다.

하지만, 다른 사람은 어떻게 접근했는지 확인했을 때, 정반대로 접근하는 것이 있었는데 빠른 해결을 위해서는 좋은 방법 같아서 아이디어를 적는다. 접근을 반대로 해서, 1만의 제곱이 10억이므로, 1만 이하의 제곱수 목록을 만들고 각 숫자를  연속해서 나오는 결과 목록을 생성한 후에, 이 중 회문인 것만 답으로 선택하는 방법이다. 실험삼아 구현해봤는데, 결과 목록을 만드는 데 생각보다 많은 시간이 걸려 큰 차이가 나지 않을 것 같았다.

n의 근인 rad(n)은 서로 다른 소수 n의 곱이다. 예를 들어, 504=2³*3²*7이고, rad(504)=2*3*7=42이다.

n이 1이상, 10이하일 때 rad(n)을 계산하고, rad(n)을 기준으로 정렬하고, 근 값이 같을 때 n 값에 따라 정렬하면 위의 표와 같다:

E(k)를 정렬된 n의 k번째 요소라고 하자. 예를 들어, E(4)=8이고, E(6)=9이다.

rad(n)이 1이상, 10만 이하의 값으로 정렬되었을 때, E(10000)을 구하시오.

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

미리 만들어 둔 약수 함수를 이용해서 결과 중 소수만 찾으면 rad(n) 값을 구할 수 있다.

10만개 결과 리스트에 대해 rad(n)값을 1순위, n값을 2순위로 해서 정렬하면 답을 구할 수 있다. 파이썬 리스트의 인덱스가 0부터 시작하는 것 때문에 1만번째 값을 다른 것을 구하는 덕분에 다시 한 번 더 실행해야 되어서 시간이 좀 걸렸다.

약수 함수를 아무리 개선해도 성능에 한계가 있어서 문제에서 10만개를 요구했으니 다행이지 다른 문제처럼 몇조 단위의 처리를 요구했으면 시간내에 해결하지 못했을 것 같다.

p_n을 n번째 소수(2, 3, 5, 7, 11, ..), r을 (p_n-1)ⁿ+(p_n+1)ⁿ을 p_n²으로 나눴을 때 나머지로 하자.

예를 들어, n이 3일 때, p₃=5이고, 4³+6³=280은 5 mod 25와 합동이다.

나머지가 처음으로 10⁹을 초과할 때 가장 작은 n의 값은 7037이다.

나머지가 처음으로 10¹⁰을 초과할 때 가장 작은 값을 구하시오.

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

이전 오일러 프로젝트 문제를 통해 소수와 나머지를 다루는 데 익숙해져 있으면 난이도 30%이지만 크게 어렵지 않게 해결 가능한 문제이다.

우선 충분한 크기의 소수 목록을 만들어 두고(천만 이하의 소수 목록을 만들어서 해결했는데, 결과론으로 보면 더 작은 목록을 만들어도 해결 가능했다), 각 소수에 대해 문제에서 제시한 공식을 대입해서 나머지 값을 구하면서 10¹⁰보다 큰 경우를 찾으면 된다.

앞에서 나온 나머지 문제를 해결할 때 중간값이 너무 커져서 에러가 발생한 경우를 봤기 때문에 부분계산을 할 때마다 나머지 연산을 적용해서 큰 수가 만들어지지 않게 하면서 답을 구했는데 생각보다 빠른 시간 내에 답을 구할 수 있었다.

가방에 붉은 색 원반 1장과 푸른 색 원반 1장이 있다. 게임에서 원반 1장을 랜덤하게 꺼내고 색을 기록한다. 각 회차가 끝나고 나면 원반을 다시 가방에 넣고 붉은 색 원반 1장을 추가한 후, 원반 1장을 랜덤하게 꺼낸다.

참가자는 1파운드를 내고 경기에 참가하고, 게임이 끝났을 때 푸른 색 원반이 붉은 색 원반보다 많은 경우 승리한다.

게임이 4회차로 구성된 경우, 참가자가 승리할 확률은 정확하게 11/120이고, 주최측이 손실을 입지 않으려면 할당해야 하는 최대 상금은 10파운드가 되어야 한다. 모든 상금은 파운드 단위로만 되어야 하고 참가비 1파운드가 포함되므로, 예시에서 참가자가 획득하는 돈은 9파운드가 된다.

게임이 15회차로 구성되는 경우 할당해야 하는 최대 상금을 구하시오.

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

확률과 조합을 이용하여 해결하는 문제이다.

예시를 조금 설명하면, 참가자가 승리하는 경우는 파란색 4장을 꺼낸 경우와 3장을 꺼낸 경우이다. 그러면 전체 가능한 경우 120(2*3*4*5) 중 파란색 4장을 꺼낸 경우는 1회이며(1/2*1/3*1/4*1/5), 3장을 꺼낸 경우는 10회(처음 나올 경우 1회, 2번째 2회, 3번째 3회, 4번째 4회)가 된다.

15회차 게임에서 승리할 경우는 전체 경우 20,922,789,888,000(2*3*4*5*6*7*8*9*10*11*12*13*14*15*16) 중 파란색을 8장 이상 꺼낸 경우를 계산하면 된다. 위 예시 설명에서 나오듯이 파란색을 꺼내는 경우는 1, 붉은색을 꺼내는 경우는 '해당 차수 원반 전체-1'이 된다.

붉은 색인 경우를 대상으로 계산을 하면 되므로, 붉은 색이 0장에서 7장인 경우를 계산하는 반복문을 만들고, 각 반복에서 가능한 조합을 생성해서 조합의 갯수를 합하는 형태로 구성하였다. 참고로, 붉은색 공이 2개인 경우 2개를 곱하는 방식을 통해 조합의 전체 갯수를 구하고, 조합의 갯수를 합해야 한다.

그리고, 참가자가 우승할 조합 갯수에 상금을 곱해서 전체 경우보다 작으면서 가장 큰 상금을 구하면 된다.

조합이나 확률을 잘 이해하면 좀 더 짧은 코드로 구현 가능했을 것 같은데, 기초만 이해하는 상황에서는 이 구성이 최선이었고 빠른 시간 내에 답을 구할 수 있었다. 난이도는 35%였지만 적성에 맞는 문제인지 어렵지 않게 해결 가능했다.

512는 각 자리수의 합을 거듭제곱한 것과 같다는 점에서 재미있는 수이다: 5+1+2=8이고 8³=512이다.

이러한 속성을 가진 다른 수는 614656=28⁴이다.

an을 이런 수열의 n번째 숫자라고 정의하고,  a_n은 두자리 이상의 숫자가 되어야 한다.

a₂=512이고 a₁₀=614656임을 알려준다.

a30을 찾으시오.

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

처음에는 brute force에 가까운 방법으로 접근했는데, 시간 문제가 생겼다. 즉, 10부터 1씩 키워나가며 자리수의 합을 구하고, 자리수의 합에 대해 거듭제곱을 하면서 원래 숫자가 만들어지는지 확인하는 방법이었는데, 예시로 제공한 10번째 숫자까지는 비교적 빠른 시간 내에 구했지만, 그 이후로는 숫자가 기하급수적으로 커지면서 10분 이상이 지나도 답이 나오지 않는 상황이 되었다.

그래서, 다른 사람은 어떤 식으로 접근했는지 찾아봤는데, 파이썬이 큰 수를 다루는 데 유리한 점을 이용하여 해결했다는 것이 있어서 그것을 참조해서 해결했다. for 반복문 2개를 이용해서 일정크기 이내의 밀과 지수에 대한 거듭제곱을 만들어서, 거듭제곱 각 자리수의 합이 밑과 동일한 경우를 구하는 방법이다. 그 이후에는 정렬하고, 30번째 요소를 찾으면 되는 것이다.

만약, 찾은 것이 정답이 아니면 밑을 충분히 크게 만들지 않았기 때문에 밑의 반복범위를 키우고, 그래도 안되면 거듭제곱의 반복범위를 키우는 방법으로 접근하면 어렵지 않게 구할 수 있을 것이다. 생각하기에 따라 상당히 위험한 방법의 brute force이지만 파이썬이 큰 숫자를 다루는 데 문제가 없기에 가능한 방법이었던 것 같다.