著者:関 勝寿
公開日:2015年11月8日
キーワード: math python

素因数分解をするプログラム msieve は相当に速いということなので、インストールした。

Mac で Homebrew を使っている場合には、Homebrew ScienceFormula を入れておいた ので、

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 までの計算結果を貼っておく。

レピュニットの素因数分解はこのサイトで計算結果がまとめられている。