Project Euler Problem 30

うーん、数学的な工夫をあまり思いつかなかったのだが、とりあえず効果のあった高速化は次の2つ。
- 計算の上限を設定。これは、計算してみればわかるが明らかに 6 * 9^5 である。各桁の5乗の和というのは、どうがんばっても6桁のこの数以上にはならないことがわかる。だから6桁以下で計算すればよいのだが、単純に < 1000000 とかやるよりもこの数を使った方がかなり計算量が少ない。
- 計算結果の再利用。例えば、各桁の五乗を求める関数をf(n)とすると、 f(n) = f(n/10) + (n%10)^5 だから、f(n/10)部分の計算はキャッシュして再利用できる。

これを使うと、手元のPCで1.3秒くらい。むむむ。まぁこれで満足すべきなのかな。てかこの問題こそGPU化しろよ>自分

LIMIT = 9**5 * 6 + 1
POWER=5
cache = {1:1, 0:0}

def get_5power(n):
    global cache

    ans = 0
    if cache.has_key(n/10):
        ans= cache[n/10] + (n%10) ** POWER
    else:
        i = n
        while i > 0:
            ans += (i % 10) ** POWER
            i /= 10
            
    cache[n] = ans
    return ans

if __name__ == "__main__":
    ans = [n for n in xrange(2,LIMIT) if n == get_5power(n)]

    print ans
    print sum(ans)