PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 133 / レピュニットの非因数

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

R(10^n) というレピュニット数について考える。

R(10), R(100), R(1000) は 17 では割り切れないが,R(10000) は 17 で割り切れる。さらに,R(10^n) が 19 で割り切られるような n は存在しない。驚くべきことに, R(10^n) の因数となりうる100未満の素数は 11, 17, 41, 73 の4個のみである。

R(10^n) の因数となりえない100000未満の素数の和を求めよ。

Problem 133 - Project Euler


レピュニット数の問題の中では問題129と似ています。

variee.hatenadiary.com

R(10^n) が素数 p で割り切れる条件は

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

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

p≠3 はわかっているので,法から9を落とせます。

 10^{10^n} \equiv 1\pmod{p}

これをみたす n が存在すれば,その n に対して R(10^n) は p で割り切れます。問題129同様,乗法的位数を求める関数
MultiplicativeOrder を使って言い換えます。

R(10^n) の因数になりえない
= MultiplicativeOrder[10, p] は 10^n の約数ではない
= MultiplicativeOrder[10, p] は 2, 5 以外の素因数をもつ


最初に書いたコードがこちらです。

2, 5 以外の素因数をもつかどうか判定する方法がわからなかったので,2, 5 以外の素数を全部かけたものを用意して,それと互いに素かどうか調べるという力技をやっています。意外に時間はかからなくて0.18秒でした。

また,2と5は MultiplicativeOrder[10, p] が定義できないので,2, 3, 5は別扱いとしています。

素因数の判定部分を MatchQ で書き直したのが次のコードです。だいぶスッキリしましたが,時間はほとんど変わりませんでした。