どうも、さっさと１億桁の素数を見つけて早期退職したい吟遊詩人です。
ネット上で死なないために素数を探し始めたわけですが
https://ginyusizin.com/2019/11/09/0014/
基本的に巨大素数を見つけようとした場合、それはメルセンヌ素数がターゲットになります。
メルセンヌ数（メルセンヌすう、英: Mersenne number）とは、2の冪よりも 1 小さい自然数、すなわち 2n − 1（n は自然数）の形の自然数のことである。これを Mn で表すことが多い。2進数表記では、n 桁の 11⋯11 となる。
出典: フリー百科事典『ウィキペディア（Wikipedia）』：メルセンヌ数
現在発見されている最も巨大な素数はM82,589,933でやはりメルセンヌ素数です。１０進数の桁数は24,862,048で、これより約５倍大きい素数を見つければ１０万ドルもらえるわけですね。（たしかM77,232,917を発見した人はFedEx社員だった気がする。）
なぜ発見された大きい素数がメルセンヌ数ばかりかと言うと、リュカ・レーマーテストという高速な素数判定法があるからなんですよね。
このメルセンヌ数、いくつか大事な性質があります。
基本的な性質
Mn が素数ならば n もまた素数であることは、次の式から分かる[2][3]：2ab − 1 = (2a − 1)(1 + 2a + 22a + ⋯ + 2(b−1)a).
対偶命題「n が合成数ならば Mn は合成数である」が示される。また、この等式より、m | n のとき Mm | Mn である。
出典: フリー百科事典『ウィキペディア（Wikipedia）』：メルセンヌ数
nが合成数ならば、Mnも合成数なのですが、２進数で書くとわかりやすいと思います。
図のように、２進数表記で1が合成数個並んでいるとしたら、その約数個の１の束と、別の約数個の１の間に０を挟んだものに分解できるというわけですね。
Mpが素数ならpも素数ですが、pが素数でもMpは素数とは限りません。最小の反例はM11です。
全てのpに対してMpが素数であってくれればM_Mpとすることでいくらでも巨大な素数を見つけることができたのですが、そうはいかなくなりました。
2,3,7,13などはメルセンヌ素数を与える素数なのに対し、11はメルセンヌ素数を与えない素数になります。メルセンヌ素数を与える素数の法則のようなものが見つかると良いのですが……。
メルセンヌ数の未解決問題
メルセンヌ数に関する未解決問題は以下のとおりです。
未解決問題
・メルセンヌ素数は無数に存在するか？
・素数 p に対して Mp が合成数であるとき、これをメルセンヌ合成数と呼ぶことにして、それは無数に存在するか？
・平方因子を持つメルセンヌ数 Mp（p は素数）が存在するか？
・n を奇数とするとき、次の3つの条件のうち2つが満足されれば、残りの1つも満足されると予想されており、n < 105 に対してこの予想は正しいと確認されている[43]。
１．Mn が素数
２．n = 2k ± 1 または 4k ± 3
３．(2n + 1)/3 が素数
出典: フリー百科事典『ウィキペディア（Wikipedia）』：メルセンヌ数
１つめと２つめの予想は少なくともどちらかは正しいと思います。
吟遊詩人予想
さて、今後素数探索をしていくに当たって、闇雲に探すのもあれなので、いくつか予想を立てて行きたいと思います。
吟遊詩人予想
- M_2147483647は素数である
- M_170141183460469231731687303715884105727は素数である
- MP(0)=M_2, MP(n+1)=M_MP(n)としたとき、MP(n)はメルセンヌ素数である
- MP(0)=M_5, MP(n+1)=M_MP(n)としたとき、MP(n)はメルセンヌ素数である
とりあえず一番上の予想だけでも当たれば１億桁超えの素数なので、１０万ドルGETですね。（数ギガの剰余算を20億回近く繰り返す必要があるのか……）
次回は実際にどのように判定していくのか、リュカ・レーマーテストのお話をしたいと思います。
おまけ
最近素数の話題で双子素数問題が解かれたというのがありましたね。
ちょっと前に６００離れた素数が無限に存在する証明がされていましたが、
いやー数学の進歩ってすごいですね。
私も素数探索を通して理論の方も勉強して、少しでも理解できるようになりたいです。
つづく
そーめんブログ 
“吟遊詩人の素数探索その１〜メルセンヌ素数について〜” への1件のフィードバック