読者です 読者をやめる 読者になる 読者になる

Problem 30

Project Euler

プロジェクトオイラーを解いてみました。

驚くべきことに, 各桁を4乗した和が元の数と一致する数は3つしかない.

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
ただし, 1=1**4は含まないものとする. この数たちの和は 1634 + 8208 + 9474 = 19316 である.

各桁を5乗した和が元の数と一致するような数の総和を求めよ.


まず何桁くらいになるかを見積もってみます。
あるm桁の整数の各桁の5乗和を考えますと、
その最大値は 9**5 * m となります。
一方この数は 10**(m-1) 以上でなければ
題意を満たす特徴の整数にはなりませんので、

10**(m-1) ≦ 9**5 * m
    ⇔ m ≦ 6

より、求める整数は6桁以下となります。


よって例のごとく力技で解いてしまいます。

print sum(filter(lambda n: sum(map(lambda x: int(x) ** 5, str(n))) == n, xrange(2, 10 ** 6)))

答えは

443839

となり、14.187 [sec] で計算することができました。


数学ガール (数学ガールシリーズ 1)

数学ガール (数学ガールシリーズ 1)