ワグスタッフ素数と新メルセンヌ予想

こんにちは｜こんばんは。カエルのアイコンで活動しております @kyamaz :frog: です。

## はじめに
人名がついた「●●素数（●●は人の名前）」という素数を紹介する第６弾です。これまでの５つのエントリは脚注にリンクを貼っておきます。[^ref1][^ref2][^ref3][^ref4][^ref5]

このあとプログラムでそれぞれの素数の列を求める例を示しますが、その前に事前準備として確率的素数を判定する関数を定義しておきます。

```Haskell: 確率的素数を判定する関数：probably_prime
ghci> exp_mod a n = iter a (n-1) n where iter a n base | n == 1 = a | even n = (iter a (n `div` 2) base) ^ 2 `mod` base | otherwise = a * (iter a ((n-1) `div` 2) base) ^ 2 `mod` base
ghci> probably_prime n = and $ map (\a -> test n a) $ takeWhile (<n) [2,3,5,7,11,13,17,19] where test n a | gcd n a == 1 = (1 == exp_mod a n) | otherwise = False
```

また、素数列を利用するためにワンライナーで素数列を定義しておきます。

```Haskell: 素数列を生成する
ghci> p=2:3:5:5#p;m#(a:b:x)=[n|n<-[a^2..b^2-2],(mod (n+1) 6)*(mod (n-1) 6)==0,gcd n m<2]++(m*b)#(b:x)
```

# ワグスタッフ素数
[ワグスタッフ素数のWiki](https://ja.wikipedia.org/wiki/%E3%83%AF%E3%82%B0%E3%82%B9%E3%82%BF%E3%83%83%E3%83%95%E7%B4%A0%E6%95%B0)によると、フランソワ・モラン氏が1990年の学会での講演でこの素数を名付けたとされており、数学者のサミュエル S. ワグスタッフ・ジュニアから命名されています。

ワグスタッフ素数の定義は以下のとおりです。

:::note info
<dl><dt>ワグスタッフ素数の定義</dt>
<dd>$q$が素数であり、$\displaystyle p = \frac{2^q+1}{3}$ が素数である素数 $p$
</dd></dl>
:::

この定義を用いて、確率的素数の判定関数を使ってワグスタッフ素数のリストを出力してみましょう。この処理はいつもどおり停止しないため、適当なところで`Ctrl-C`で停止しています。

```Haskell:
ghci> [(q,w) | q<-p, let x=2^q+1, x `mod` 3 == 0, let w = x `div` 3, probably_prime w]
[(3,3),
(5,11),
(7,43),
(11,683),
(13,2731),
(17,43691),
(19,174763),
(23,2796203),
(31,715827883),
(43,2932031007403),
(61,768614336404564651),
(79,201487636602438195784363),
(101,845100400152152934331135470251),
(127,56713727820156410577229101238628035243),
(167,62357403192785191176690552862561408838653121833643),
(191,1046183622564446793972631570534611069350392574077339085483),
(199,267823007376498379256993682056860433753700498963798805883563),
(313,5562466239377370006237035693149875298444543026970449921737087520370363869220418099018130434731),
(347,95562442332919646317117537304253622533190207882011713489066201641121786503686867002917439712921903606443),
(701,3506757267698915671493993255253419110366893201882115906332187268712488102864720548075777690851725634151321979237452145142012954833455869242085209847101253899970149114085629732127775838589548478180862167823854251),
(1709,9619252724870106900591857521914969755994617926162485749828680263442652106934332647419115450350548509594113720023679578428867652599441500099408187466188831829627322561298620142064115434370067980896141705699219480691615366345077753886654052361984948213632109502554264973588138936426510951217614006613784979416372970841528398839021290713797778493018446941241754769857894878843499740605322478881600054025752566680081461168156277505142145985544055010083285836939763680507287209419644373726922686975212036857299070528171),
(2617,20815047099026323257806675143935315245000606320386981580413335663090242082815432995265098589392031228667730473843062779195713776017918917013121073130839039077907880629653588944202322774462326914006584257849232002558050878023575918651686915831015715166128163750577661757268447302500316523850227465632729819785840933960476441995094447131053119719237234706945743000184938183584415225694074338513980952813759887400071071078397968831132690191141545644878174595251413988926012846145007091998393975114834622586096614105658373816787662498366560890295299138528254067663483963612747930019524852659168022079446368475164502311988764660026941548192256786223297786584104610756947392835265037107071204166614305707510898432511257347889222531434492328170692410272342633590329039652079499645847933435947691),
(3539,737960982013072251717827114247527699664069926110661926761160893989171826141119521929101931369383490982766847861989655122674917393968130587829514313057964897260666603966014551135454876960320216137860473967819079126559583788823053318306935359861441837366855882806862688379176110552962626629416447849146630431273272995724167758732603285383186777757585738831334876769323045488159378902977467713837514310434260339455526629562477584638188948029810999272419754692499619209623001613278324156579182194830724641306437197442253758831506979191793352123575900078074622075861772974340085081499946707336416327925893771446279902695718233584641686166117068880549847126723693094451226465616453469916241963304631414866552321857691895960230071117582088132687611887380755935649761769000294914373494533422904682091065786979568675767012114940615503154724612851260976803588566734355505597767200432478724025353578867345462382931420365933103311751585395715447345608189334178143604853988249079586934366138135363609181014186399426964456547292271975820619495426338199733732972086304686486497963),
(5807,40184962373430040768164262611955195801203915388544783256109666339130109882331025047163764577482253760929177681316034030641895261365379707161333299051346585318005768001563823189834179211471871709027147062642023152133404071242534559074220576392469173532434805172124155231396249763691166003672291833317362672271230513169536054259128159129895380196542915084772838687262259566379537221677528914388251736302629434754538583384438857812325657982776303732609332736248446275832871092238438147121750851381168949316064631148533445843220182137530321161626781758050640200098685121144555064940495632309911734292875922319226985233237184893418153443754681384447058782943976044070929050255569221038164042681517908465197283854614634335528404501261587086360501280487592630364029769699671706205742625441348571504261179637376411055183519708553427441971351890205239752952693765604033625397002643517092150103011207142716778096307459923065526222484062992318595625759100194127428314347037349946641734271288488518544018947978954312524801562799251364022919926414340413843502315293005100759556930797359340145419213093372649459958651420809254410141594986745360202697632903617356640617456395992239253388532841327984997193007552510062772854727151020486207907092944072897231681283977822476420495288943078013357761888483655267944153338146912898215955116021373314594264290899684488329828054709093873699885544241764526433485616491057486589395711483874167444252898927846313774322183030611939738557502382567879185135433869414504728104050747582406677605971356709871310443102788797013436004644899772354373435023696768678959761261372804102959274000698496458857688219898471334344514133724813728758732251002483552883032284401725498434956174010666249957554660346205019459748642466686663568043)
^CInterrupted.
```

## 新メルセンヌ予想
『新』がつかない「[メルセンヌ予想](https://ja.wikipedia.org/wiki/%E3%83%A1%E3%83%AB%E3%82%BB%E3%83%B3%E3%83%8C%E4%BA%88%E6%83%B3#%E6%96%B0%E3%83%A1%E3%83%AB%E3%82%BB%E3%83%B3%E3%83%8C%E4%BA%88%E6%83%B3
)」はマラン・メルセンヌによって1644年に発表された$n \le 257$の範囲で $2^n-1$ で表されるメルセンス数が素数となる$n$についての予想です。計算機がない時代の予想でしたので、素数となる$n$には誤りがありましたが、現在では$$n = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127$$でメルセンヌ素数となることが判明しております。
このメルセンヌ予想から着想をうけ、ベイトマン、セルフリッジ、ワグスタッフ（Bateman, Selfridge and Wagstaff ）は、1989年に次の「新メルセンヌ予想」を発表しました。

:::note info
<dl><dt>新メルセンヌ予想</dt>
<dd>任意の正の奇数 $n$ に対して、次の条件のうち、もし2つの条件を満たしているならば、3つめの条件も同様に満たされるであろう

1. ある自然数 $k$ に対して、$n = 2^k \pm 1$ あるいは $n = 4^k \pm 3$
2. $2^n − 1$ が素数 （メルセンヌ素数）
3. $(2^n + 1) / 3$ が素数 （ワグスタッフ素数）

</dd></dl>
:::

この予想を満たす数は$ 3, 5, 7, 13, 17, 19, 31, 61, 127 $が知られており、新メルセンヌ予想は「127よりも大きい数字はこれら3つのすべての条件を満たさないだろう」ということも含んでいます。
新メルセンヌ予想は、127よりも大きい数字で証明するか、反例を見つければよいのですが、3つの条件のうち1つの条件が既知のすべての奇素数を探索的に調べられており、$p \le 12,441,900$までは検証されています。また2024年時点では、48番目（$2^{57,885,161}-1$）までの既知のメルセンヌ素数で、条件3が成立しないとわかっているそうです。

さらに、ワグスタッフはLenstra、Pomeranceとともに「メルセンヌ素数が無限にある」（正確にはメルセンヌ素数の個数に関する予想で「$n$より小さいメルセンヌ素数の個数は漸近的に$\displaystyle e^{\gamma }\cdot \log \log(n)/\log(2)$（$\gamma $はオイラーの定数）によって近似される」）という予想も立てています。

いずれも予想ですので、証明（または反例）の与えられていない未解決問題です。

## おわりに

ご一読いただきまして有り難うございます。
最後に、本稿を記載するために検証したHaskell環境を記しておきます。お手元の環境で検証する際に、動作が異なるときには参考になるかもしれません。

<details><summary>本稿の環境</summary>
本稿のために使用した環境は以下となります。

* macOS: Sonoma 14.5 (chip: Apple M1)
* GHCup: 0.1.30.0
* GHC: 9.6.4

</details>


（●）（●） Happy Hacking!
/""　＿＿""＼

[^ref1]: [ウォルステンホルム素数](https://qiita.com/kyamaz/items/848f4868b9055bc09fc0)
[^ref2]: [カレン素数とウッダル素数](https://qiita.com/kyamaz/items/7b73265525cd9ebe4f31)
[^ref3]: [ヴィーフェリッヒ素数](https://qiita.com/kyamaz/items/d550448562f07b9d75fb)
[^ref4]: [キネア素数とキャロル素数](https://qiita.com/kyamaz/items/04b1a58ef7a25e988a76)
[^ref5]: [プロス素数とピアポイント素数](https://qiita.com/kyamaz/items/98d6fa9b4dbd0de52284)