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](m を法として a^b を与える関数)はものともしない感じでした。

 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