책 이야기

2⁷=128은 "12"로 시작하는 첫번째 2의 거듭제곱수이며, "12"로 시작하는 다음 2의 거듭제곱수는 2⁸⁰ 이다.

p(L,n)을 L로 시작하는 십진수 중 2^j가 n번째 가장 작은 j를 나타낸다고 정의하면, p(12,1)=7이고 p(12,2)=80이다.

또한 p(123,45)=70이다.

p(123,678910)을 구하시오.
--------------------------------------------------------------------------

문제에서 요구하는 대로 구성하면 프로그램의 구조는 간단하다. 2를 계속 곱해가면서 L로 시작되는 n번째 숫자를 찾아 거듭제곱수를 알려주면 된다.

이렇게 구현하면 예시로 나와있는 p(12,1), p(12,2), p(123,45)는 어렵지 않게 구할 수 있다. 하지만, 2의 거듭제곱수 중에서 123으로 시작하는 678910번째 숫자가 2의 몇 거듭제곱인지 찾는 것은 데이터 허용범위가 넓은 파이썬으로도 어려운 일이었다. (이번에는 4300자릿수 이상을 넘을 수 없다는 에러메시지를 봤던 것 같다)

프로젝트 오일러의 높은 번호 문제는 난이도가 낮아도, 간단히 해결 가능한 것이 아니라 (주로 상상도 못한 크기의 숫자로) 한계가 숨어 있고, 이것을 어떻게 해결해내는 것인지가 추가로 포함되어 있는 것 같다.

이번 문제에서는 앞의 3자리만 동일하면 되기 때문에, 일정크기 이상으로 커지면 앞의 3자리에 영향을 미치지 않을 아랫쪽 수를 10000으로 나눠 없애는 형태로 계산했는데, 정확한 숫자를 구하는 것이 아니어서 살짝 걱정되었지만 맞출 수 있었다.

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이지만 파이썬이 큰 숫자를 다루는 데 문제가 없기에 가능한 방법이었던 것 같다.

r을 (a-1)ⁿ+(a+1)ⁿ을 a²으로 나누었을 때 나머지로 하자.

예를 들어, a=7이고 n=3일 때, r=42가 된다(6³+8³=728≡42 mod 49). 그리고 n 값이 바뀌면 r도 바뀌게 된다. 하지만, a=7일 때 r의 최대값인 r_max=42이다.

3≤a≤1000일 때, r_max의 합계(∑r_max)를 구하시오.

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

어렵지 않아 보이지만 실행 시간이 많이 소요되는 문제이다. 나누는 수가 a²이기 때문에 나머지를 확인하기 위해 검증하는 범위를 a²번까지 설정해야 했기 때문이다.

그리고, 나머지 함수의 특성을 살려서 적용해야지 문제에서 제시한 그대로 코딩했을 때에는 숫자가 기하급수적으로 커지면서 실행시간이 매우 많이 필요하게 되었다.

나머지 함수의 곱셈 특징((a*b)%c=(a%c)*(b%c))을 활용하여, 거듭제곱의 경우 분산해서 계산하도록 코드를 개선했다. 즉, a⁷=a*a²*a⁴, a⁹=a*a⁸과 같은 형태로 나누고, 각각에 나머지 함수를 적용해서 숫자가 최대한 커지지 않도록 만들었다.

그렇게 개선했어도 실행시간은 많이 필요했으며(100까지 7초, 200까지 58초, 300까지 173초, 400까지 360초, 500까지 628초, 600까지 942초, 700까지 1365초, 800까지 1777초, 900까지 2415초, 1000까지 3043초로 총 3시간 필요), 이 방식보다는 좀 더 빠른 형태의 수학에 기반한 해법이 있을 것 같다.