久しぶりのブログ更新です。ブログを更新していなかった間ですが、素数を探してました。

　1
　12
　123
　1234
　12345
　123456
　1234567
　12345678
　123456789
　1234567890
　12345678901
　123456789012
　1234567890123
　：
　：
　となる数列から素数を探すということをやってました。

　まず最初はJavaScriptやC言語で探そうとしましたが、せいぜい10進で20桁までしか計算できないために素数は発見できませんでした。
　そこでpythonで計算することにしました。pythonで扱える整数には桁数の制限はありません。

　で、pythonで作ったプログラムによって以下の桁数で確率的素数（PRP）であることを発見しました。
　171桁
　277桁
　367桁
　561桁
　567桁

　まだまだここで終了しません。これ以上の桁数にも素数がないかと続行します。
　しかしここで新しい壁に衝突しました。計算にかなりの時間がかかるようになってきました。pythonでは1000桁までの計算がせいぜいのようです。
　そこで1000桁以上ではC言語でGNU Multi-Precision Library（GMP）を使うことにしました。

　で、なんとか18881桁が確率的素数（PRP）であることを発見できました。
　確率的素数（PRP）と言いますが、ミラー・ラビン素数判定法で乱数を100回テストしてもパスしています。かなりの高い確率で素数だと思われます。

　これ以上の桁数でも素数はあるのかと現在12万桁までテストしていますが、まだ見つかっていません。
　他にも計算速度アップのために色々と工夫しましたが、今回は取り急ぎの更新のため以上です。


【まとめ】
　1234567890123456……と続く数列で確率的素数（PRP）となるのは以下の通り。
　171桁
　277桁
　367桁
　561桁
　567桁
　18881桁
　これ以降は12万桁までテストしたもののみつからず。
タグ ：
#素数