034. 数字阶乘(digit factorials)

\(145\)是一个好奇数,因为\(1!+4!+5!=1+24+120=145\),求所有这样的好奇数字之和。

注:因为\(1!=1\)以及\(2!=2\)都不是和,所以不包括在内。

分析:这道题的解题思路和第三十题的非常相似,也就是先通过好奇数需要满足的条件确定一个合理的上界,然后在上界之内寻找符合要求的值并求和即可。回忆我们在第三十题中的分析思路,假设符合要求的数字\(n\)总共有\(d\)位,则\(10^{d-1}<n<10^d\)。此外,由于该数字等于它各位数的阶乘之和,则各位数的阶乘之和最大只能为\(d\cdot9!\),即\(n<d\cdot9!\),综合上面的两个条件我们有:

$$ 10^{d-1}<d\cdot9! \Leftrightarrow d-1<log(9!)+log(d) \Leftrightarrow d-log(d)<log(9!)+1 $$

解此不等式,我们有\(d<7.43\),因为\(d\)为整数则\(d\)最大为7。因此有:

$$ n<7\cdot 9!=2540160 $$

根据上式,所求数字的首位数只能是1或者2,则可进一步把上界缩小为\(2!+6\cdot9!=2177282\),经过分析,我们还可以进一步缩小上界,不过对于题目中的数字规模,这个上界已经足够了。

from math import factorial

def main():
    fac_dict = {str(n):factorial(n) for n in range(10)}
    res = 0
    for i in range(10,2177282):
        if sum([fac_dict[x] for x in str(i)]) == i:
            res += i
    return res