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

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 34 / 桁の階乗

145は面白い数である。1! + 4! + 5! = 1 + 24 + 120 = 145 となる。

各桁の数の階乗の和が自分自身と一致するような数の和を求めよ。

(注)1! = 1 と 2! = 2 は総和に含めてはならない。

Problem 34 - Project Euler

どこまで調べればいいか

どこかの国の数学コンテストに類題が出ていたような気が…… まず何桁まで考えればいいのか調べます。

k 桁の数の場合,左辺は k*1! 以上 k*9! 以下。
右辺は10^(k-1) 以上 10^k 未満(10^k -1 以下)。

これらが共通部分をもつには 10^(k-1) ≦ k*9! が必要です。

7桁までですね。一応グラフも描いてみました。

f:id:variee:20170312000735p:plain

桁ごとの!をとって足す

適当に判定条件を作って Select して Total します。

今までで一番時間がかかりました。計算時間94秒。1分をオーバーしてしまった……

ためしに各桁の数の階乗の和が自分自身と一致する数を全部書き出してみたら,その数4個。約10^7個チェックしてヒットするのは2つだけという効率の悪さでした。


追記(2017/04/20)

PCを新調したので再計算してみました。素の状態で52秒。並列化して13秒。無事1分を切れました。