Project Euler 030を解いてみる。「各桁の5乗」

Project Euler 030

030

驚くべきことに, 各桁を4乗した数の和が元の数と一致する数は3つしかない.
1634 = 1⁴ + 6⁴ + 3⁴ + 4⁴
8208 = 8⁴ + 2⁴ + 0⁴ + 8⁴
9474 = 9⁴ + 4⁴ + 7⁴ + 4⁴
ただし, 1=1⁴は含まないものとする. この数たちの和は 1634 + 8208 + 9474 = 19316 である.
各桁を5乗した数の和が元の数と一致するような数の総和を求めよ.

->次の問題

考え方

総当りばっかりやってますが、今回もそれで行きます。もうダメかもわからんね(^q^)
探索範囲について、各桁の5乗が最も大きくなるのは全ての桁が9の場合(9, 99, 999, 9999,...)です。99999の時、9⁵×5=295245で各桁の5乗のほうが大きく、999999の時、9⁵×6=354294で元の数のほうが大きくなります。元の数は桁が1つ増えるたびに約10倍ずつ増えていきますが、各桁の5乗は9⁵=59049ずつしか増えていかないので7桁以上では必ず元の数のほうが大きくなります。
よって探索範囲は9⁵×5=295245までで良さそうです。
あとは総当りをしていきます。

コード

euler030.py

def main():
    answer = 0
    for i in range(2, 9 ** 5 * 5):
        sum_five = sum([int(j) ** 5 for j in str(i)])
        if i == sum_five:
            answer += i
    print(answer)


if __name__ == '__main__':
    from time import time as t
    st = t()
    main()
    print(t() - st, 'sec')

paizaにて実行
結果 443839 0.6426656246185303 sec