うえぽんSW局

　2016年も最後となってしまったので、以前書いた「素数探しの旅」がその後がどうなったか書いておこうと思います。

　まず探していた素数というのは以下のように1234567890123…と続く数列で素数となるものです。
　1
　12
　123
　1234
　12345
　123456
　1234567
　12345678
　123456789
　1234567890
　12345678901
　123456789012
　1234567890123
　：
　：

　以前の記事では以下の桁数において素数（もしくは確率的素数）となることを発見しました。
　171桁
　277桁
　367桁
　561桁
　567桁
　18881桁

　ではこれ以上の桁数で素数は存在するのだろうか？
　というわけで、あれからチマチマと素数を探し続けていました。
　そうして半年かかって21万1761桁までテストしましたが、発見できませんでした。
　（もしかしたら自分がミスして見逃している可能性があるかもしれませんので、他の方の検証も欲しい所です）

　長らくチマチマと探していましたが、2016年が終わるのを目途として素数の探索はをこれにて打ち切りにしたいと思います。この挑戦はかなり無茶だったかもしれません。


　以下はもしかしたら素数探索の手助けになるかもしれないメモです。

●一般項
　次の式で求められる（^は乗数、[]は小数点以下切り捨てを意味する）。
　[10^k*1234567890/9999999999]
　for文を使うより一般項で普通に計算した方が速い。

●末尾が1と7だけ探索すれば良い
　2と5の倍数を除外すると末尾が1、3、7、9の4つを探せば良いことが分かるが、3と9も除外することができる。なぜなら各桁の数を合計すると必ず3の倍数になるため（3の倍数を求める方法）。

●最大公約数を求めることでさらに除外
　素因数分解や素数判定は時間がかかるが、最大公約数の計算は比較的高速に求めることができる。
　例えば下の2つの数の最大公約数を求めるとその数は7となり、両方とも素数でないことが分かる。
　123456789012345678901234567890（30桁）
　12345678901234567（17桁）
　この例では桁数が30*k+17の形のときは7の倍数になる（つまり素数ではない）ことを意味するので、その形になるものを素数判定の対象から除外することができる。
　他にも、110*k+87桁、110*k+21桁などが素数の判定から除外できる。
　こういうのをたくさん探しておくことで、素数判定の対象を減らせる。

●素数判定の前に軽く素因数分解した方が速いことも
　桁数が大きくなるとミラー・ラビン素数判定法でもかなりの時間を要する。
　そこで素数判定の前に“軽く”素因数分解をやるやり方も有効になってくる。
　自分はポラード・ロー素因数分解法を使った。


　というわけで2016年はこれでお終いです。
　良いお年を。

タグ ：

#数学

#素数