The number 145 is well known for the property that the sum of the factorial of its digits is equal to 145:
1! + 4! + 5! = 1 + 24 + 120 = 145
Perhaps less well known is 169, in that it produces the longest chain of numbers that link back to 169; it turns out that there are only three such loops that exist:
169 → 363601 → 1454 → 169
871 → 45361 → 871
872 → 45362 → 872
It is not difficult to prove that EVERY starting number will eventually get stuck in a loop. For example,
69 → 363600 → 1454 → 169 → 363601 (→ 1454)
78 → 45360 → 871 → 45361 (→ 871)
540 → 145 (→ 145)
Starting with 69 produces a chain of five non-repeating terms, but the longest non-repeating chain with a starting number below one million is sixty terms.
How many chains, with a starting number below one million, contain exactly sixty non-repeating terms?
다음과 같이, 숫자 145는 각 자릿수의 계승(factorial)의 합과 동일하다는 것이 잘 알려져 있다.
1! + 4! + 5! = 1 + 24 + 120 = 145
169에 대해 덜 알려진 것은, 169로 다시 돌아오는 데 가장 긴 체인을 만든다는 것이다. 그런 종류의 루프는 단 3가지만 있다:
169 → 363601 → 1454 → 169
871 → 45361 → 871
872 → 45362 → 872
모든 숫자가 루프가 된다는 것을 증명하는 것은 어렵지 않다. 예를 들면 다음과 같다.
69 → 363600 → 1454 → 169 → 363601 (→ 1454)
78 → 45360 → 871 → 45361 (→ 871)
540 → 145 (→ 145)
69로 시작하면 반복되지 않는 5개 항을 가지는 체인을 만든다. 하지만, 1백만 이하의 숫자로 시작해서 가장 긴 반복되지 않는 체인은 60개 항이다.
1백만 이하의 숫자로 시작해서 정확히 60개의 반복되지 않는 항을 가지는 체인은 몇 개 있는가?
--------------------------------------------------------------------------
50번 이전의 오일러 프로젝트에 가까운 문제이다. 숫자를 각 자리수로 분해하고 각 숫자에 대한 계승을 합하는 과정을 반복하면서, 이전에 나온 숫자가 다시 나오는지 확인해주고, 체인의 길이가 60개인 경우가 몇 번 나오는지 계산해주면 된다.
성능을 위해서 계승을 매번 계산하지 않고 딕셔너리를 활용하는 형태로 구현했다. 지금 생각해보니 딕셔너리의 앞자리 값이 인덱스와 같으므로 튜플이나 리스트 구조로 구현해도 상관없을 것 같다.