Project Euler 34

题目

Digit factorials

\(145\) is a curious number, as \(1! + 4! + 5! = 1 + 24 + 120 = 145\).

Find the sum of all numbers which are equal to the sum of the factorial of their digits.

Note: as \(1! = 1\) and \(2! = 2\) are not sums they are not included.

解决方案

解法与30题相同。

一个\(n\)位数如果全是\(9\)，那么其和数位和的\(k\)次幂为\(n\cdot 9!\)。因此一个\(n\)位数的值绝不会超过\(n \cdot 9!\)。

如果\(n\)满足\(10^n>n\cdot 9!\)，那么停止循环退出。

代码

from itertools import count

fac = [1]
for i in range(1, 10):
    fac.append(fac[-1] * i)
ans = 0
for n in count(1, 1):
    mx = min(10 ** (n + 1) - 1, n * fac[9])
    st = 10 ** n
    if st > n * fac[9]:
        break
    for i in range(st, mx + 1):
        s, w = 0, i
        while w:
            s += fac[w % 10]
            w //= 10
        if s == i:
            ans += i
print(ans)