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

Problem 34

久々にProject Eulerを解いてみます。
今回はいつもより難しそうな問題です。


Problem 34

145は面白い数である. 1! + 4! + 5! = 1 + 24 + 120 = 145となる.
各桁の数の階乗の和が自分自身と一致するような数の総和を求めよ.
注: 1! = 1 と 2! = 2 は総和に含めてはならない.


まず、自然数 n の各桁の階乗の和を返す関数を f(n) とします。
つまり f(145) = 1! + 4! + 5! ということです。


まずはどこまで調べれば良いのかという下限を見定めるため、

n > N なる全てのnに対して f(n) < n となるNが存在する。

という命題が真であることを証明し、Nの値を1つ求めます。
(Nの値は厳密に下限である必要はありません。)


k桁の自然数の中で f(n) を最大にするような n は、
999...999 という 9 が k 個並ぶ数です。
つまり
f(999...999) < 100...000 (右辺はk桁の数、すなわちk桁の自然数の中で最も小さい数)
を満たせば、
これより大きい自然数nについては常に f(n) < n が成り立ちます。


9! = 362880 なので、
f(999...999) = 362880k
つまり
f(10**k - 1) = 362880k
となります。


f(10**k - 1) = 362880k < 10**(k - 1) となる最小のkは 8 なので、
N = 100,000,000 とすれば、命題は成立します。


おっと、ここで問題発生です。


f(1)〜f(100,000,000) を計算してそれが f(n) = n を満たすか否かを調べていけば
答えを求められるということがわかりましたが、
1億回もループを回すような地球に優しくないことをするわけにはいきません。
(会社から帰る前に実行すれば朝までには終わる気がしますが。)


そこで、不要な処理をうまく端折ることを考える必要が出てきました。
というわけで、続きはまた今度(笑)。