PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 132 / 巨大なレピュニットの素因数

1のみからなる数をレピュニット数という。長さ k のレピュニット数を R(k) であらわす。

R(10) = 1111111111 = 11×41×271×9091
の素因数の和は 9414 である。

R(10^9) の最初の40個の素因数の和を求めよ。

Problem 132 - Project Euler


非常に大きな数が相手ですが,Mathematica に組み込まれている
PowerMod[a, b, m](a^b を m で割った余り)はものともしませんでした。

 p\, \left|\, \dfrac{10^k-1}{9} \right.\ \Leftrightarrow\ 9p\, |\, (10^k-1)

 \therefore 10^k \equiv 1\pmod{9p}

これをみたす素数を探します。適当に範囲を広く取って探したら 0.033 秒。

次に普通にループさせて40個数えました(p=2, 3, 5 は明らかに不適なので除きました)。ほんのすこし速くなって 0.024 秒でした。


variee.hatenadiary.com