오일러 74번 문제는 자릿수의 계승(팩토리얼)값을 합하는 연산에 대한 문제이다.
145는 각 자릿수의 계승값을 모두 더했을 때 자기 자신이 되는 수로 잘 알려져 있습니다.
1! + 4! + 5! = 1 + 24 + 120 = 145
그보다 덜 유명하긴 하지만 169는 위와 같은 방법으로 계산해서 자기자신으로 되돌아오는데 가장 많은 단계를 거치는 숫자로, 그런 특성을 가진 숫자는 3개 밖에 없다고 합니다.
169 -> 363601 -> 1454 -> 169
871 -> 45361 -> 871
872 -> 45362 -> 872
어떤 숫자로 시작해도 결국 위와 같은 반복 루프에 들어간다는 사실은 어렵지 않게 증명이 가능한데, 몇 개의 숫자의 예를 들면 다음과 같습니다.
69 -> 363600 -> 1454 -> 169 -> 363601 (-> 1454)
78 -> 45360 -> 871 -> 45631 (-> 871)
540 -> 145 (-> 145)
69로 시작하면, 반복이 일어나기 전에 다섯 번의 단계를 거친 다음 루프에 들어갑니다. 1백만 이하의 숫자로 시작하는 경우는 최대 60번의 반복되지 않는 단계가 존재합니다. 1백만 이하의 숫자로 시작했을 때, 반복되지 않는 단계를 정확히 60번 거치는 경우는 모두 몇 번이나 됩니까?
풀이
어떤 수를 변환하는 연산을 수행하고 그 결과에 똑같은 연산을 수행하여 순환마디에 다다르는 경로와 관련된 문제이다. 결국 전수조사 해야하는 문제이다. 순환마디에 다다르기 전에 이전에 계산된 결과를 만단다면 조금 더 시간을 단축할 수 있으므로 메모이제이션을 적용한다.
또한 계속 반복해서 계산되는 팩토리얼과 계승의 합 구하는 시간을 최소화하는 것이 목적이다.
팩토리얼 함수
팩토리얼을 구하는 것은 reduce 를 이용하거나, 반복문, 재귀등의 여러 방법으로 구현할 수 있는데, 이 중에서 가장 추천하지 않는 것은 재귀이다. 왜냐하면 재귀에서는 계속해서 함수 호출이 일어나는데, ‘함수를 호출한다’는 것은 함수 내의 이름 공간을 할당하는 등의 작업이 수반되기 때문이다. 이 문제에서는 문제 특성상 0에서 9까지의 숫자의 팩토리얼을 구하기만 하면 된다. 따라서 이 때 가장 빠르게 계승을 계산하는 방법은 미리 계산된 10개 숫자의 팩토리얼을 튜플로 만들어 놓고 인덱스로 해당 값을 찾는 것이다.
이는 한 줄짜리 함수가 되므로 람다식으로 써도 좋겠으나, 람다식으로 표현한 들 여전히 함수 호출이 발생하므로, 각 숫자의 계승의 합을 구하는 과정에서 인라인 평가식으로 쓰자.
계승의 합
계승의 합을 구하는 것은 정수를 문자열로 바꾸고 다시 각 글자를 정수로 바꾸면서 계승을 맵핑하고 합을 구하면 된다. 이를 코드로 표현하면 다음과 같은데
lambda n: sum(factorial(int(x)) for x in str(n))코드는 간단하지만 계산 과정에서 자리수 + 1 개만큼의 타입 변환이 일어난다. 어차피 1백만 정도의 값을 쓸 것이기 때문에 간단하게 while문을 쓰자.
def tr(x):
s = 0
while x > 0:
x, y = divmod(x, 10)
s += (1,1,2,6,24,120,720,5040,40320,362880)[y]
return s조립
이제 나머지 코드를 조립해보자. 먼저 문제에서 예로 들어준 케이스들을 캐시에 정리한다. 주어진 수 n에 대해서 이 값이 캐시에 있으면 그 값을 쓰면 되고, 그렇지 않다면 계승의 합을 구해본다. 계승의 합과 그 자신이 같으면 단계는 0이다. 그렇지 않다면 단다음 숫자의 총 단계를 구해서 + 1 하는 식으로 재귀 구현한다.
def e074():
memo = {169:3, 363601:2, 1454:3, 871:2, 45361:2, 872:2, 45632:2}
def helper(n):
if n in memo:
return memo[n]
m = tr(n)
if m == n:
memo[n] = 0
return 0
r = helper(m) + 1
memo[n] = r
return r
print(sum(1 for x in range(100_0000) if helper(x+1) == 60))
수행 성능은 뭐 썩 좋지 않은 컴퓨터에서도 2~3초대에 수행되니 이정도면 준수하다 하겠다.