숫자 145에는 신기한 성질이 있습니다. 각 자릿수의 팩토리얼(계승)을 더하면 1! + 4! + 5! = 1 + 24 + 120 = 145 처럼 자기 자신이 됩니다. 이렇게 각 자릿수의 팩토리얼을 더하면 자기 자신이 되는 모든 수의 합을 구하세요. 단, 1! = 1 과 2! = 2 의 경우는 덧셈이 아니므로 제외합니다.
http://euler.synap.co.kr/prob_detail.php?id=34
접근
문제의 조건, 각 자리의 팩토리얼을 합한 값이 자기 자신이 되는 조건을 통해서 검사할 수 있는 범위를 어디까지 설정해야 할지를 먼저 결정해야 한다. 한자리 수의 팩토리얼 중에 가장 큰 값은 9!로 이 값은 362,880이다. 9! x 6 = 2,177,280 이고 9! x 7 = 2,540,160이다. 즉, 약 254만이상 부터는 각 자리 수의 팩토리얼을 더해도 자기 자신이 되기에는 턱없이 부족한 숫자만 나올 것이다.
실제로는 250만 이하의 수 중에서 각 자리 숫자의 계승의 합이 가장 크려면 2,499,999 인데, 이 수의 각 자리 숫자의 계승의 합은 1,814,426 에 그친다. 다시 1,814,426 이하에서 계승의 합이 가장 큰 수를 만들어보면 1,799,999 인데, 이 수의 각 자리 계승의 합은 1,819,441로 원래 값보다 크다. 따라서 검사할 수 있는 가장 큰 수의 범위는 1,799,999로 잡을 수 있다.
이 값은 2백만에 가까운 수이기 때문에, 파이썬이라면 루프를 돌기에 상당히 부담스러운 범위이기는 하다. 따라서 각 자리 숫자의 팩토리얼의 합을 구하는 함수가 얼마나 빠르게 작동하느냐가 관건이 될 수 있다. 우선, 다음과 같이 팩토리얼을 계산하는 함수와, 각 자리 숫자의 계승의 합을 구하는 함수를 작성할 수 있을 것이다.
from functools import reduce
# 팩토리얼을 계산하는 함수 준비
_prod = lambda xs: reudce(lambda x, y: x * y, xs, 1)
_fac = lambda n: 1 if n < 2 else _prod(range(1, n + 1))
def process(n: int) -> int:
xs = map(int, str(n))
return sum(_fac(x) for x in xs)
이 함수를 180만번 모두 다른 값에 대해서 호출해야 하는데, 이 함수에는 정수를 문자열로 바꾸고 다시 문자를 정수로 바꾸며, 누적곱을 계산하는 과정이 들어가기 때문에 그 자체로는 간단하지만 상대적으로 비싼 연산을 많이 사용하고 있다.
우선 주목할 것은 팩토리얼 연산인데, 실제로 각 자리 숫자의 팩토리얼 값만 구하면 되기 때문에 팩토리얼은 0~9 사이의 숫자에 대해서만 계산할 것이다. 그렇다면 매번 계산하기 보다는 미리 계산한 값을 사용하는 것이 훨씬 빠를 것이다. (참고로 팩토리얼은 누적곱이므로, 0! = 1 로 간주할 수 있다.)
fs = (1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880)
fs[n]그리고 각 자리 숫자를 구하는 것은 10으로 반복해서 나눈 나머지들을 사용하면 된다. 따라서 각 자리 계승의 합을 구하는 함수는 아래와 같이 작성된다.
def process(n: int) -> int:
fs = (1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880)
s = 0
while n > 0:
n, r = divmod(n, 10)
s += fs[r]
return s
%%time
s = 0
for a in range(10, 180_0000):
if process(a) == a:
s += a
print(s)기타
사실 문제에서 제외한 1과 2를 포함하여 이 조건을 만족하는 수는 딱 4개 밖에 없다. 이러한 수들을 ‘팩토리올(factoriols)’이라고 부른다고 한다.