PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 206 / 覆面平方数

平方すると 1_2_3_4_5_6_7_8_9_0("_"は1桁の数) の形の数になる自然数がただ一つある。その値を求めよ。

Problem 206 - Project Euler

第1案

もとの数を n とします。n^2 の一の位が0なので,n は10の倍数です。また,n^2 の百の位が9であることから,n の十の位は3か7だとわかります。

n の範囲もおさえましょう。与えられた数の _ に0や9を埋めた数の √ をとります。

n は1010101010以上1389026623以下。下2桁を30や70に変えたものに100を最高 3789256 回足したものまで調べればいいことがわかります。

「上から1桁目が1,3桁目が2,……」は「上から 2k-1 桁目が k」ですね。これで一応解けます。

計算時間は272秒。1分を超えてしまいました。

第2案:周期性は?

n^2 の百の位について調べました。周期25。

一周期中に8は3回あらわれるので,この性質を使えば計算量は 3/25=12% になります。ただ,この方法は第1案と本質的には同じですね。

第3案:StringMatchQ[]を使う

『Mathematicaクックブック』の第5章「文字列とテキスト処理」にパターンマッチングの方法が書いてあります。

「"1" ~~ _ ~~ "2"」は正規表現です。「_」は任意の1文字をあらわし,これで「aではじまって2で終わる長さ3の文字列」をあらわします。

問題文中の式に「~~」をはさめばマッチング用のパターンが作れます。ついでに第1案でリストを2つ作るのが無駄に思えたので,小さなリストを Flatten する方式に変えました。計算時間は23秒。


Mathematicaクックブック

Mathematicaクックブック