PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 417 / 逆数の循環節その2

単位分数とは分子が1の分数である。

分母が 2 および 5 の素因数だけからなるとき,その単位分数は循環節を持たないと考えられる。そのような単位分数の循環節の長さは 0 であるとしよう。

1/n の循環節の長さを L(n) で表す。3 ≤ n ≤ 1,000,000 における ΣL(n) は 55535191115 である。

3 ≤ n ≤ 100,000,000 における ΣL(n) を求めよ。

Problem 417 - Project Euler


「逆数の循環節その1」はなんと第26問。随分と離れた類題です。
variee.hatenadiary.com

「循環節の長さをどう求めるか」「2と5をどう処理するか」がポイントかと思います。

循環節の長さをどう求めるか

問題26では素直に RealDigits[1/n] で循環小数を求めてその長さを調べましたが,さすがにこの方法では 10^8 は扱えそうにありません。
 10^x \equiv 1\pmod{n} をみたす x の最小値として求めました。

n=10^3 ではほぼ同じスピードですが,n=10^5 では約5倍違います。

2と5をどう処理するか

上の f417[n] は n=2^a 5^b のとき1を返します。「このような n の個数を求めて最後に引く」と「If 文を使って 0 を返すようにする」を試してみましたが,大差ありませんでした。


本番

以上をもとに最終的なコードを書きました。いろいろ工夫したものの1分の壁は厚く,5分かかりました。


英語版 wikipedia を参考に

正解者掲示板で英語版 wikipedia がくわしいと知りました。

Repeating decimal - Wikipedia

その情報をもとに書いてみたのがこちらのコードです。残念ながら,私の腕ではかえって遅くなってしまいました。