Project Euler with Ruby on WSL [Problem 30]

Project Euler Programming ruby

はあ30

年齢に近い大きさの整数をみると「ん？」ってなる時ありますよね

まぁ年齢を正確に思い出せるかは別問題だけど

問題

Digit fifth powers

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

1634 = 14 + 64 + 34 + 44

8208 = 84 + 24 + 04 + 84

9474 = 94 + 44 + 74 + 44

As 1 = 14 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.

私訳

各位の5乗

10進表記した各位の4乗の和が、元の数自体に一致するのは以下の3例しかない。

1634 = 14 + 64 + 34 + 44

8208 = 84 + 24 + 04 + 84

9474 = 94 + 44 + 74 + 44

なお 1 = 14 は自明だが、含めないものとする

「各位の5乗和がそれ自身と一致する数」すべての和を求めよ

解答方針

最終的には虱潰しに実行するが、探索範囲を制限したい。

d 桁の自然数 n を考えると 10^{d-1} \le n \lt 10^d で、その各位の5乗和 S は 1 \le S \le d \cdot 9^5

S = n となりうる範囲を考えているので結局 10^{d-1} \le d \cdot 9^5 \lt 10^d となるような d の範囲を考えることになる

9^5 = 59049 \approx 10^{4.771} だから d-1 \le 4.771 + \log d \lt d

よって d = 5 が確定。与えたのは上限だけなので、2 以上の範囲で調べる

と思ったんだけどなんか 6 桁の例が紛れてますね。うーーーーんなんで。まぁいいや