레온하르트 오일러는 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가 되는데, 여기서 나머지 함수의 나누기 특성을 위해 페르마의 소 정리를 보면,
ap-1 ≡ 1(%p), 단 p는 소수이고 a는 p의 배수가 아닌 경우
ap-1=a*ap-2≡ 1(%p)가 된다.
이를 위 공식에 적용하면 n=(x*euler(divider-2))%divider가 된다.
그리고 (euler(divider-2))%divider는 상수 형태이므로 프로그램으로 구현하면 어렵지 않게 구할 수 있다(3451657199285664). 페르마의 소 정리를 이용해서 계산했는데, 좀 더 빠른 성능을 위해서는 확장 유클리드 개념을 활용하면 된다고 한다.
이 내용을 구현하면 오일러코인 값이 1부터 시작할 때 몇번째 배열 값이 되는지 쉽게 구할 수 있고, 배열 값이 이전 값보다 큰 경우를 제외하게 되면 실제 오일러코인 합계에 포함되는 값들을 구할 수 있다.
나머지 함수의 나누기 특성만으로 구한 것으로 설명은 되어 있었지만, 정수론에 대한 이해가 부족해서인지 빠른 형태로 구현하지 못해서, 두 프로그램의 결과를 조합해서 문제에서 요구하는 오일러코인의 합계를 구할 수 있었다.