Project Euler Problem 034

http://projecteuler.net/index.php?section=problems&id=34
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2034

145は面白い数である. 1! + 4! + 5! = 1 + 24 + 120 = 145となる.

各桁の数の階乗の和が自分自身と一致するような数の総和を求めよ.

注: 1! = 1 と 2! = 2 は総和に含めてはならない.

Problem 30 と同じような問題なので、同じように解いた。

まず、どこまで調べたら良いのかを確認する。
7桁のときに 9! * 7 で 2540160 となり桁が追いつかなくなるので、最大値が分かる。

次に、問題の例で f(145) は f(14) + 5! 、つまり

f(n) = f(n/10) + (n % 10)!

となることが分かるのでキャッシュを使いながら計算していく。

計算範囲がProblem30よりも広いので、そのぶん時間がかかってしまう。もうちょっと良い方法ないかな。。

import itertools
import operator
import datetime


def euler034():
    def limit_value():
        x = reduce(operator.mul, range(1, 10))
        for i in itertools.count():
            n = 10 ** i
            m = x * (i + 1)
            if n > m:
                return x * i
    
    def make_facttable():
        d = [ 1 ]
        x = 1
        for i in xrange(1, 10):
            x *= i
            d.append(x)
        return d
    
    limit = limit_value()
    d = make_facttable()
    
    cache = [ 0 ] * limit
    cache[1] = 1
    cache[2] = 2
    
    result = 0
    for i in xrange(3, limit):
        x = cache[i/10] + d[i%10]
        
        if i == x:
            print '', i
            result += i
            
        cache[i] = x
        
    print result



begin = datetime.datetime.now()
euler034()
end = datetime.datetime.now()
print end - begin

答え: 40730 (145, 40585)
実行時間: 1.216319秒くらい