素因数分解プログラム msieve
素因数分解をするプログラム msieve は相当に速いということなので、インストールした。
Mac で Homebrew を使っている場合には、Homebrew Science に Formula を入れておいた ので、
brew install homebrew/science/msieve
で、インストールできる。これで、
msieve -q 素因数分解したい数
で、手軽に素因数分解ができるようになった。
ためしに、レピュニット Rn = (10n - 1) / 9 について、R100 までの素因数分解をしてみた。python が入っていれば、
python -c "for i in range(101): print ('1'*i)" | msieve -m -l rep100.txt
で、rep100.txt に計算結果が保存される。計算は1時間半ほどで終了した。あまり細かいログがいらない時には、
python -c "for i in range(101): print ('1'*i)" | msieve -m -q | grep -v next > rep100.txt
とすれば、計算結果だけが保存される。たとえば、R97 の計算結果は
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 p8: 12004721 prp36: 846035731396919233767211537899097169 prp54: 109399846855370537540339266842070119107662296580348039
となる。これはつまり、
\[\begin{eqnarray*} R_{97} &=& \frac{10^{97}-1}{9} \\ &=& 12004721 \\ &\cdot& 846035731396919233767211537899097169 \\ &\cdot& 109399846855370537540339266842070119107662296580348039 \end{eqnarray*}\]であることを示している。
ここで、p8 は8桁の素数であることを、prp36 は36桁の「おそらく素数」であることを示している。素数判定には確率的手法を使っているため、prp (probably prime) はまだ素数であることが確定しているわけではないが、ほぼ確実に素数、というくらいの「おそらく」である。計算の確認は、calc を使うか
$ calc "12004721 * 846035731396919233767211537899097169 * 109399846855370537540339266842070119107662296580348039"
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
Online Arbitrary Precision Calculator を使う。
ここに、R100 までの計算結果を貼っておく。
レピュニットの素因数分解はこのサイトで計算結果がまとめられている。