Problem 34 「桁の階乗」
145は面白い数である. 1! + 4! + 5! = 1 + 24 + 120 = 145となる.
各桁の数の階乗の和が自分自身と一致するような数の和を求めよ.
注: 1! = 1 と 2! = 2 は総和に含めてはならない.
def hoge():
# 階乗計算
f = lambda n : n * f(n-1) if n > 1 else 1
# 計算コストを下げるために0~9の階乗をリスト化
lst_factorial = [ f(n) for n in range(10) ]
# 999999(6桁)→9!*6=2177280(7桁)、9999999(7桁)→9!*7=2540160(7桁)、
# 99999999(8桁)→9!*8=2903040(7桁) なので7桁が問に合致する可能性のある最大の桁数
# 実質 9!*7=2540160 までチェックすれば問題ないはず
for n in range(10, lst_factorial[9]*7):
if n == sum( lst_factorial[int(m)] for m in str(n) ):
yield n
print(sum(hoge()))
遅い。7~8秒くらいかかる。
高速化するうまいやり方が思いつかなかったのでちょっとカンニング調べたところ、
逆転の発想が必要みたいでした。