책 이야기

레온하르트 오일러는 1707년 4월 15일에 태어났다.

배열 1504170715041707n mod 4503599627370517을 생각해 보라.

이 배열의 요소는 이전에 찾은 모든 오일러코인보다 작은 오일러코인으로 정의된다.

 예를 들어, 첫 요소인 1504170715041707은 첫 오일러코인이다. 두번째 요소인 3008341430083414는 1504170715041707보다 크기 때문에 오일러코인이 아니다. 세번째 요소인 8912517754604는 새로운 오일러코인이 된다.

처음 두 오일러코인의 합계는 1513083232796311이다.

모든 오일러코인의 합계를 구하시오.

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

프로젝트 오일러의 문제가 그렇듯 문제 자체는 간단하고 프로그램으로 구현하기도 쉽다. 다만, 정수론에 대한 이해 없이 문제를 정직하게 구현하면 시간의 함정에 빠지게 된다. 문제를 보면 오일러코인이 1이 되면 끝나는데, 최악의 경우 4,500조 횟수를 반복해야 구할 수 있기 때문이다.

문제대로 정직하게 구현하면 처음 16번 오일러코인까지는 그런대로 빨리 구할 수 있지만 그 이후로는 시간이 많이 소요되며, 처음 20번 오일러코인까지 나온 특성(이전 코인과의 차이가 같거나 크게 나옴)을 이용해서 구현하면 54번째까지는 빨리 구하지만 그 뒤로는 마찬가지로 시간이 너무 많이 소요된다.

그래서 정수론의 도움을 받으려면, 나머지 함수의 나누기 특성에 대한 이해가 필요하다. 문제를 공식으로 만들어  설명하려면 우선 상수 1504170715041701=euler, 4503599627370517=divider로 정의하자.

(euler*n)%divider=x 형태가 된다.

n=(x/euler)%divider

n=(x*euler^-1)%divider가 되는데, 여기서 나머지 함수의 나누기 특성을 위해 페르마의 소 정리를 보면,

a^p-1 ≡ 1(%p), 단 p는 소수이고 a는 p의 배수가 아닌 경우

a^p-1=a*a^p-2≡ 1(%p)가 된다.

이를 위 공식에 적용하면 n=(x*euler^(divider-2))%divider가 된다.

그리고 (euler^(divider-2))%divider는 상수 형태이므로 프로그램으로 구현하면 어렵지 않게 구할 수 있다(3451657199285664). 페르마의 소 정리를 이용해서 계산했는데, 좀 더 빠른 성능을 위해서는 확장 유클리드 개념을 활용하면 된다고 한다.

이 내용을 구현하면 오일러코인 값이 1부터 시작할 때 몇번째 배열 값이 되는지 쉽게 구할 수 있고, 배열 값이 이전 값보다 큰 경우를 제외하게 되면 실제 오일러코인 합계에 포함되는 값들을 구할 수 있다.

나머지 함수의 나누기 특성만으로 구한 것으로 설명은 되어 있었지만, 정수론에 대한 이해가 부족해서인지 빠른 형태로 구현하지 못해서, 두 프로그램의 결과를 조합해서 문제에서 요구하는 오일러코인의 합계를 구할 수 있었다.

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¹⁰보다 큰 경우를 찾으면 된다.

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

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시간 필요), 이 방식보다는 좀 더 빠른 형태의 수학에 기반한 해법이 있을 것 같다.