ユークリッド素数とクンマー素数（素数階乗素数）

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

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

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

```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)
```


# 素数階乗素数
[素数階乗](https://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0%E9%9A%8E%E4%B9%97)とは、$2$ 以上の自然数に対してそれ以下の素数全ての総乗で、自然数$n$の素数階乗は、記号では$ n\\\# $で表します。


```Haskell:m番目の素数階乗を計算する
ghci> :{
ghci| p' 0 = 1
ghci| p' m = (p!!(m-1)) * (p' (m-1))
ghci| :}
```

素数階乗素数（Primorial prime）とは、$ n\\\# \pm 1$ の形で表される素数です。$+1$の方をユークリッド素数、$-1$の方をクンマー素数を呼びます。

## ユークリッド素数
素数が無数に存在することの証明が、背理法をつかって紀元前3世紀頃のユークリッドの『原論』に記され、『ユークリッドの定理』と呼ばれています。この証明に$(素数の積+1)$を考えることから、その名が付けられました。

あらためて、ユークリッド素数の定義は以下のとおりです。

:::note info
<dl><dt>ユークリッド素数の定義</dt>
<dd>$ n\\\# +1$の形で表される素数 $p$
</dd></dl>
:::

これをHaskellで計算すると次のようになります。（ある程度の時間まで出力したところで、`Ctrl-C`で計算を中断しております。）

```Haskell:
ghci> [(p!!(n-1),x)| n<-[1..], let x=(p' n)+1, probably_prime x]
[(2,3),(3,7),(5,31),(7,211),(11,2311),(31,200560490131),
(379,1719620105458406433483340568317543019584575635895742560438771105058321655238562613083979651479555788009994557822024565226932906295208262756822275663694111),
(1019,20404068993016374194542464172774607695659797117423121913227131032339026169175929902244453757410468728842929862271605567818821685490676661985389839958622802465986881376139404138376153096103140834665563646740160279755212317501356863003638612390661668406235422311783742390510526587257026500302696834793248526734305801634165948702506367176701233298064616663553716975429048751575597150417381063934255689124486029492908966644747931),
(1021,20832554441869718052627855920402874457268652856889007473404900784018145718728624430191587286316088572148631389379309284743016940885980871887083026597753881317772605885038331625282052311121306792193540483321703645630071776168885357126715023250865563442766366180331200980711247645589424056809053468323906745795726223468483433625259000887411959197323973613488345031913058775358684690576146066276875058596100236112260054944287636531),
(2657,78244737296323701708091142569062680832012147734404650078590391114054859290061421837516998655549776972299461276876623748922539131984799803433363562299977701808549255204262920151723624296938777341738751806450993015446712522509989316673420506749359414629957842716112900306643009542215969000431330219583111410996807066475261560303182609636056108367412324508444341178028289201803518093842982877662621552756279669241303362152895160479720040128335518247125849521099841272983588935580888630036283712163901558436498481482160712530124868714141094634892999056865426200254647241979548935087621308526547138125987102062688568486250939447065798353626745169380579442233006898444700264240321482823859842044524114576784795294818755525169192652108755230262128210258672754900845837728345782457465793874408469588052577208643754019053756394151041512099598925557724343099264685155934891439161866250113047185553511797406764115907248713405817594729550600082808324331387143679800355356811873430669962333651282822030473702042073141618450021084993659382646598194115178864433545186250667775794249961932761063071117967553887984011652643245393971),
(3229,689481240122180255681227812346871771457221628238467511261402638443056696165896544725098860107293247422610010824870599655026129367004672337297193288816463520704235722580204218943598425089855869341564771022924163236141415235947085902422536824665765244189167643048218572769125400511177245717452516267205786258497574258715214994129786103824740384634788909041221747073062941769355745272170421584636198911899164272930590704655882680817754473306122122423384160639995940152584830810911265680382263051658031509463010733595465426943956643445876702680730987739513538299069540636616098525527546435002783615353417794625251129892373849727119530335366131575986221685088118143088371896087248659669154564925048225211644681303874490648860319990785185350796853298548942407689617641587755314125485345107782298938892240282038605672241010302874153509795545077305234459038983235361138814897166376363090128647084552385969054439430382421762883708894899853286109068224980793075241538872287253835877394821667363465425187353453157415169810167271517665273484442461468031313956356871467191959110440864194544244079053955897287010339385419923838571256564818350769518898003780557167344272499224580817920441512610104625622872289967615843092782763554732404239287463466833602966629613502579134371295289680374088987611189907873072122808833765972650050982877578244899073193043546490795625023568563926988371)^CInterrupted.
```

$p\\\# + 1$ が素数となるような素数 $p$ は、2004年3月現在で次の22個が知られているそうです。

$2, 3, 5, 7, 11, 31, 379, 1019, 1021, 2657,
3229, 4547, 4787, 11549, 13649, 18523, 23801, 24029, 42209, 145823,
366439, 392113$

上の計算で11個が正しく出力されていることが確認できました。

## クンマー素数
クンマー素数の定義は以下のとおりです。

:::note info
<dl><dt>クンマー素数の定義</dt>
<dd>$ n\\\# -1$の形で表される素数 $p$
</dd></dl>
:::

ドイツの数学者エルンスト・エドゥアルト・クンマーがユークリッドの定理を証明するのに用いた形式の数であり、そこから命名されたという由来があります。

こちらもHaskellで計算すると次のようになります。（ある程度の時間まで出力したところで、`Ctrl-C`で計算を中断しております。）


```Haskell:
ghci> [(p!!(n-1),x)| n<-[2..], let x=(p' n)-1, probably_prime x]
[(3,5),(5,29),(11,2309),(13,30029),(41,304250263527209),
(89,23768741896345550770650537601358309),
(317,19361386640700823163471425054312320082662897612571563761906962414215012369856637179096947335243680669607531475629148240284399976569),
(337,2159704595610254721415747050533376368260798239989520222949435936418441984820398307416727184404426847652711313512004598759003964186453789),
(991,19649288510530675457635414441530973968028056560270178760163094612807087579117222328838467049939300222263018614960316970059367632623084520289159762277685706141788095679442344974064203568968298530551124858332193301576974333066317468633561818590965385004001920654119546949528482322103750771653865564789273369859966306024106155051816131935006029725093179578640416314145736960424258769442998811239035580823050358968029),
(1873,7148872308348669964510112805799367345041876048527043577174997635789953888187751121056510536208835758341865360994540924539992624902598731397121474422984243643637526103097113473245267463770365459016338957939649642778222396242426052481835019495804240323401742312674588410373705010749720211707550895270264340811085438304597637054470385918725430396398595971450288989411650994587997549686345680439253363054848175668330867740879106096721018270650903296195483819063779403932787178928305095386606901073837751456724670785524431615536310559839378149309443539692477252909302829418092926751382580131554544779707098497432274483929631206536169123617068452095459440167498814490434614831017102124653601802925310283316398582840798663581750159791496432870626882826015508727506279345339667063871022000761714929),
(2053,40476351620665036743811179797005129273452304284765356847983761772791530086135011097687712896135586057006669510277749580009189011838624238398091180781883625723815622247180448952722758952833721651896915176331157999595686954902803303329952152642546062055978053941555691691138563718631526843506494980054351627108794263950679711565391711967079317265398549713254703576670919763865921746705195302279366467692168438445319219572166714692777489122838492688269671368059586621187176715894578474225639877240877871847772786810836209350254272525213939175671725658033448781955352584784675731029986412669253419747768484495001648564335105611237094526021231636017810522526742347546247305364949820477821970973010599736548532239253873249173498530813871335394883471325759646608578314670746436618564353397514883985883420792654621343980946271801533711209640277008013461010663664196050230069),
(2377,13372477493552802137730694707478973075249077111924625039725420082740961528278551284828276796015813181527539752988792824104161576841170718606614004916024991273932827667649317762976694850388846845885246766695024417056792411109964873116302652161774413274847634875486760316355655986853321514456545223162769857594978170273159745394056908418453710941377288018909842114696199761393094958194818952796364555607538598879051704793840139426034830786085702324408925503526119558196480836003984069137558719954346064731884316864278068816476675464140758404497328799453094965104083755300333907358786890460784613647553680495470537374341059849790345153270402888688217036859196817547278437096892402463658647299463696779426677383358307999402427728850709528225482386272312057225599453250791747547007474654805928181905824658752817376534978078632405527402899573507025949546155246193792773350395163364364480858911536040970462045306911215814804383220096747582211554527874220927850604104145580216012429989076742011921698973741675973189)^CInterrupted.
```

$p\\\# − 1$ が素数となるような素数 $p$ は、2021年10月現在で次の20個が知られているそうです。

$3, 5, 11, 13, 41, 89, 317, 337, 991, 1873, 
2053, 2377, 4093, 4297, 4583, 6569, 13033, 15877, 843301, 1098133, 
3267113$

上の計算で12個が正しく出力されていることが確認できました。

## おわりに

ご一読いただきまして有り難うございます。
最後に、本稿を記載するために検証した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)
[^ref6]: [ワグスタッフ素数と新メルセンヌ予想](https://qiita.com/kyamaz/items/08d73cc92ac6a40c9952)
[^ref7]: [ウィルソン素数とウィルソンの定理](https://qiita.com/kyamaz/items/2d7804d95af63e96bdfb)
[^ref8]: [ピタゴラス素数とチェビシェフの偏り](https://qiita.com/kyamaz/items/7c07ae7a995a6d42d025)