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

 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万桁までテストしたもののみつからず。