読者です 読者をやめる 読者になる 読者になる

Problem 34 続き

Project Euler

先日の記事の続きです。
問題はこちら。

145は面白い数である. 1! + 4! + 5! = 1 + 24 + 120 = 145となる.
各桁の数の階乗の和が自分自身と一致するような数の総和を求めよ.
注: 1! = 1 と 2! = 2 は総和に含めてはならない.


小一時間考えたのですが、
地球に優しくない解法以外思いつきませんでした…orz
腕が鈍っているのかもしれません。
スマートかつ情熱的な解き方がおわかりの方は
是非コメントに書き込んでいただければと思います。


というわけで、1時間程度の計算時間になると見積もったので
以下のようなコードを実行しました。

facts = (1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880)
def f(n):
    str_n = str(n)
    total = 0
    
    for c in str_n:
       total += facts[int(c)]
    
    return total

total = 0
for n in xrange(3, 10 ** 8):
    if n == f(n):
        print n
        total += n

print '-' * 80
print total

悔しいです!


とりあえずProject Eulerに骨のある問題が含まれていることが判明したので、
今後もボチボチと解いてみたいと思います。
Problem 33までの問題が簡単すぎたのは偶然だったのかもしれません。