오일러 프로젝트 34

숫자 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)’이라고 부른다고 한다.