Project Euler Problem 030

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

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

   1634 = 1^4 + 6^4 + 3^4 + 4^4
   8208 = 8^4 + 2^4 + 0^4 + 8^4
   9474 = 9^4 + 4^4 + 7^4 + 4^4

As 1 = 1^4 is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

まず、どこまで調べたら良いのかを確認する。
7桁のときに 9^5 * 7 で 413343 となり桁が追いつかなくなるので、6桁の数字が最大ということが分かる。

次に、問題の例で f(1634) は f(163) + 4^4 となるので f(n) は、

f(n) = f(n/10) + (n % 10) ^ 5

となることが分かる。キャッシュを利用すれば計算量を減らせそう。

プログラム的な工夫としては、上述のキャッシュを利用することと、5乗の数を毎回計算せずにあらかじめ用意しておくくらい。

import itertools
import datetime

def euler030():
    N = 5
    
    def limit_value():
        for i in itertools.count():
            n = 10 ** i
            m = 9 ** N * (i + 1)
            if n > m:
                return 9 ** N * i
    
            
    limit = limit_value()
    d = [ i ** N for i in xrange(10) ]
    
    cache = [ 0 ] * limit
    cache[1] = 1
    
    result = 0
    for i in xrange(2, limit):
        x = cache[i/10] + d[i%10]
        
        if i == x:
            print '', i
            result += i
        
        cache[i] = x
        
    print result


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

答え: 443839
実行時間: 0.178024秒くらい