Project Euler 119

プロジェクトオイラー
http://projecteuler.net/index.php

Q119.
(5 + 1 + 2)³ = 512のように数字の和のべき乗が元の数になるもののうち小さいほうから30番目のもの

これもやはり逆から考える。すなわち、ある数のべき乗を考えて、その各桁の総和が元の数になるものを探す。
順番をつけなければいけないので、桁数ごとに考える。N桁とすると、その各桁の総和はN〜9Nだから、指数eは、

N^e < 10^N, 10^N-1 < (9N)^e
Nlog10/log(9N) < e < (N+1)log10/logN

の範囲で調べればよい。

from itertools import count

from math import log
def pow_range(N):

    return range(int( (N - 1) * log(10) / log(9 * N)) + 1,

    int(N * log(10) / log(N)))
def sum_digits(n):

    s = 0

    while n:

        s += n % 10

        n /= 10

    return s
def first_pow_num(n, e):

    m = int(10 ** (float(n - 1) / e))

    while m ** e < 10 ** n:

        m += 1

    return m
def find_pow(N):

    b = [ ]

    for e in pow_range(N):

        begin = first_pow_num(N - 1, e)

        end = first_pow_num(N, e)

        for n in xrange(begin, end):

            if n == sum_digits(n ** e):

                b.append(n ** e)

    b.sort()

    a.extend(b)
M = 30

a = [ 0 ]

for N in count(2):

    find_pow(N)

    if len(a) > M:

        break

print a[M]