PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 62 / 立方数置換

立方数 41063625(=345^3) は桁の順番を入れ替えると2つの立方数になる。56623104(=384^33) と 66430125(=405^33) である。41063625 は立方数になるような桁の置換をちょうど3つもつ最小の立方数である。

立方数になるような桁の置換をちょうど5つもつ最小の立方数を求めよ。

Problem 62 - Project Euler

第1案:とりあえず答えを出す

立方数を桁ごとに区切ってソートしたもののリストを作って重複を調べました。この場合,
(重複度5の数として得られる数)=(並べ替えで得られる最大の数)
なので,それと同じ数字を使う数の最小値を求めています。

1分を少しオーバーしてしまいました。何度も何度もリストを作るのは無駄なので,次はここを直します。

第2案:リスト作りも集計も1回だけ

重複度が4以下なら新しい数をリストに追加していく方法も考えましたが,毎回集計しなおす点は変わらないので却下。リスト作りも集計も1回で済ませる方法を考えました。

まずはリストの大きさの見積もりです。上のコード中の g[n] を使います。n の値を1000刻み,100刻み,……で調べていくと 8384^3 がわかります。

この数は12桁です。並べ替えで桁数は変わらないので,n^3 が13桁になる n=10^4 まで調べれば十分だとわかります。

コードをそれっぽく直せばできあがり。0.05秒。約1500倍ですね。


第3案:Split でグループ分け

第1案,第2案とも最後にリストを再検索するところが無駄なので,f[n] を定義し直して
{(n^3 を桁ごとに区切ったリスト), n^3}
を返すようにしました。

こうすると Tally で重複度を調べることはできなくなるので,Split でグループ分けして,各グループの要素数を数えます。時間は0.04秒。第2案よりちょっと速くなりました。