カレン素数とウッダル素数

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

## はじめに
素数の研究は様々あるようで、研究した人の名前がついた「●●素数（●●は人の名前）」という素数の集合が色々あります。本稿では、カレンさんが研究したカレン素数と、その研究に触発されたであろうウッダルさんが研究したウッダル素数の２つを紹介し、そのリストを出力するプログラムをHaskellで書いてみましょう。

まずは、ある条件の数列から素数を得るために、素数を判定する関数を考えます。ここでは、フェルマーの小定理の対偶をなる関数`is_prime`を定義します。ただし、この`is_prime`は調べたい数`n`に対して`[2..(n-1)]`の数すべてを確認するように書いてあります。この範囲で調べれば、必ず素数かどうかをチェックできますが、調べる範囲を少しだけにしてもよく、（確率的な）判定法である **フェルマーテスト** の関数`probably_prime`を素数判定に用いましょう。

```Haskell: 素数判定（フェルマーの小定理の対偶 is_prime とフェルマーテスト 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> is_prime n = and $ map (\a -> test n a) [2..(n-1)] where test n a | gcd n a == 1 = (1 == exp_mod a n) | otherwise = False
gchi> 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
```

# カレン素数とウッダル素数
## カレン素数
カレン数（Cullen number）は、$n × 2^n + 1$を満たす数で、アイルランドの数学者であるジェームズ・カレンという方が研究を始めたことから名前が付けられています。その中で素数である数が『カレン素数』です。[^ref1][^oeis_A005849]
ほとんど全てのカレン数は合成数であることが知られている一方、カレン素数も無数にあると予想されています。カレン素数となる n は、次の16個が知られています。
$1, 141, 4713, 5795, 6611, 18496, 32292, 32469, 59656, 90825, 262419, 361275, 481899, 1354828, 6328548, 6679881$

:::note info
<dl><dt>カレン素数の定義</dt>
<dd>$n × 2^n + 1$を満たす素数</dd>
</dl>
:::

素数判定に関数`probably_prime`を使ってカレン素数を出力してみましょう。

```Haskell:
ghci> [(n,m)|n<-[1..], let m=n*2^n+1, probably_prime m]
[(1,3),
(141,393050634124102232869567034555427371542904833),
(4713,2677114856136697933736444134296294069473360835877445521815688283880323274251963548043328475062388013916298584523053521328906455532243293122247649120667999141956177739050156409498421757923332060596316640631257195623360333643194334118058524648593843039167229660942243585399944074965037752374533295192204875441765598270265814764416763543087415875057955856191365697724709615260647821897338995140534907463282799065416095977054548356800276266674029692792498226245206108087788958744067541397635326162304833094807878403794238619563706846340722839123274026203037112039234882016873977731485542327942966401620403964681628600273783704173791159988737699108693746557993945705972043987077604198044999064201629092111063116822865053108109451580323761583182883573441641827484464357320276397526264795990226899619110115603669354996361944463273587177835036999103554929836719380259649956100026866321448165342334769969895156786587543447919757410556541225638731325663469341854127624038205973198567197566492339682037220683291035338024135444101013594477954634842574077728099202225361590462071661219598135430746579943708832733976150768764898080904631588529580861113604324147925539738783131955725203411839841729645869865957668949066417125593814511508032774734493285686458186727554501306359481949566591957128778468302813656968772056230991522464422116182032916491702012940045654497185958956226883353614827905443501747130339992754131696049534038385360897),
(5795,170560442105000307313119068727744404053693864509240980690299450514105703199298064073472179487189692781678162595136536040700524687216095265869086768556557711365607977711715592323063282615097287514999255782234270629843561957654165847047198418111102681118500753886078720385210889194768291253379588262261315931991050408069429761546616954705378707206274067077337841938001558242555726220425742230624940536040335137501868474643181040787910538093399912204934875395429501588221304672501281051687411755679106978481392483524720204097749723257071443699922265835866791962577060749779807081052372208913040893721105446660097934150348744963885399809490999967922880112666265509319604867844988014587031709477096884440296577102655131328896804749617356322357742861639843232148109752497263821383504771312950418848042140623971900926358762239551107441082019680473167261983052030035674945685276112681798591196496542035188278126051071963499554047335311308949898670366688690162436827373838947466398083570886321507540959328763213067198162883121334219613882549002272484050119079924046307789281553201194367292019780182686404018891883532902560527419831260880880645482995124362242479769160020587177592812412950802494916064559643649277662617048711057410333121291707203935149604277820909119279860985907082827691574812326256551076441841719746273311616135749896258354805834299564167386245295683007078679812057285907297862828965502205665126133897496863379154867345669093790275046667965622210047564008525620746980854374467717569506369365782890659201704055672949490413098960445125995748276550679331635933146456779375850516467170157763508287836548374843978818581470443096715717621634474093426384414107343304825896366275469726023020437764935408387576193303251653872877863805977379796418561),
(6611,85029278063954401608057442269178958601095881673000902463286174259821984066841791967225240174184337149857896976456884717743919010349235605744148792191588898127478821173454324173271963488242172303134483961600273267212979250796686489765968530994856197004571261974132847578260568271940207848247194054252551772805990934683701848509494302827542270680855795091000111885495338573320945656431277139510684714948341084981827201004364322123006461545824464586045590589670474281907887068380257684048071293198927105026072022102571850174491171742092217224929642094516215930334920511568370849006121313428207346411465283744537990481366260996949312575984488507015308668333803678514952760056525648977742415450792841509883722564923042088284123003994082214003832663725767882638496561001486444234795963214201731441461491718681571275944252746274531864762677697083899416120358800098987013011962195010621311191002861066879387528540829952798530102278110031818233510004403670727238233140278228110315550638423183038850821435971338755754412370572885785609126025834752082763940510421079715996026820348304285306478146238275909923974162347506603504236083395332236511614447396593599557570360036217658529408020441474164838997421700312137328799271957403918406289469896925606688165409212422660976194612847248827573112312001607207419237847358709082490392936334046101710399480909764742095626114571340222471747461007445770507555824242798578974718374549576328232419701802762190703806402390401909971966936174138884216948202010693387764290069737880537733619543589287406382878605942181635939381514887235464762827195238609765243189866240773635810772266392471144834403682496873028809081278655576911595194271788040760076944016441956357700409721980473882095251541000661162730992781965162940281141846718595291821330038946583162716004657793478752593194317937585061849958350272371195185654126538532419810395938763606892267001652367925914583877105773808861724644245312101191592720049353716240116262989268170756900997849006120719701071059723747329)^C
Interrupted.
```

しばらく時間をかけると上記のように`n=6611`まで出力できました。適当な時間までにして`Ctrl-C`で処理を中断します。


## ウッダル素数
ウッダル数（Woodall number）は、$n × 2^n - 1$を満たす数で、ハーバート・ウッダルとアラン・カニンガムが研究を始めたことから名前が付けられています。その中で素数である数が『ウッダル素数』です。[^ref2][^oeis_A002234]
ウッダル素数となる n としては、次が知られています。
$2, 3, 6, 30, 75, 81, 115, 123, 249, 362, 384,\dots$

:::note info
<dl><dt>ウッダル素数の定義</dt>
<dd>$n × 2^n - 1$を満たす素数</dd>
</dl>
:::

素数判定に関数`probably_prime`を使ってウッダル素数を出力してみましょう。

```Haskell:
ghci> [(n,m)|n<-[2..], let m=n*2^n-1, probably_prime m]
[(2,7),
(3,23),
(6,383),
(30,32212254719),
(75,2833419889721787128217599),
(81,195845982777569926302400511),
(115,4776913109852041418248056622882488319),
(123,1307960347852357218937346147315859062783),
(249,225251798594466661409915431774713195745814267044878909733007331390393510002687),
(362,3400689659856510513983967904150960015639988330819247172784157326778638668365953026135436149661145081990241845247),
(384,15130370379415480017515151398455147701150619879858731520492144667230357160254928874783078241875807606069745148277817343),
(462,5501738854392961162179176026017924626372727744717470824039194165599524472559859148008657148801167643264160317146644057379520281844448806043647),
(512,6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151),
(751,8895424555342349321723049894983973838790293875538933982585358280621065257777931531024854164354808845068483625439036834547690251259843640197560575436065117153492322441037431938692087017130511719236545657306526703124393676660277247),
(822,22989432637682048935578359759258512929075458593285426151563351225878608019921960174786937174324066918557552262283220478419095917521791323874771300201334066843810139337069250339905576793882539603587327037857904876391811440492908489972485276368673701887),
(5312,6260298383829657225286112584739828350961566071813614817090655661726702203000727443155352137677415727639270005152424260690857553900368341450346970741308511417934442673066866644403367228220364439878425897186245253177691894131530314490537670719045204854370814516293642618537389174767012520242616529405673247696080934123952725656223766315340714614855806548932055139425179151479881206038701763802779138916668883306784294260180704008909313195142729581852896420768539776228014321360869785451249902588785914955877269128146778963486558120668354631060167501141743903122509454201202547688715196727040523077806030531988397663538853730963809344267934674614590712227267805424158243982282344265009362357321981931239055386336840472883326309867734816135908681990888503697042094651571968230153780164618679215781152726244096578224696053246041697606541689435068727931476353894324623910695079566421040585311985103805812421650786510353427759898861776000121326090856058979212077591696177260616037165555751507285878767478858118625647588877281294325434409067338807313030610213165442239480105674376617197846030146545262330219853080619480300992036754949135625216566071983425953282414885683202259216717086223201216107231214643841453821800479705443657770734535275127870398933661350313638594922371398078999763881759388037191499672886496845677727495900732005269358724467804503279937265707718167486322051615118497652040645286382390708500068385222336755432189454238226603697941580242718059483611416057744941499700978593848565252669806462644516538399273148998665777617816962249185512503379530702903585164261671957932841026458847073533951),
(7755,23834068123225913434555279410745878744839896081672903810579146490637390810869254357840358304091122339778107874421215192035877339109770982288272053293885526907980778450504129302708747973430299059987255443332815173019929728697709827665786212256796864342232189277250047426741023425335215616826029656733789628647570775055551944629595620868267162695612544680069717341601111520180166772387982580324963289088440732135947750410287037383068150352456055026053148475851299905041088790970894452984875122025041978085263290526132158848805482367674130589367320003804794144330563297942999543266311098579369944247666071293742285905669346180436081501509642702060860408213502800544678110849191172520936777216869758713949577277043819139466907209814532731126691993784170243205478206279801555142229223664725647150726133047164897219503100246085596400213808966327574619145168565347565669979908045345647436413085863420181299470059425829625324390368896888482253150201488119395909126588189125415394724232601158970633256027539120708831383658210321857424861562716912820086153399857022156898055298462870006306201182868135539099043169824878314538441778418113257523145039356965986798141654320549329169990228165917944468096415449409378480193540566443523600464658362464357400438079372151065509766268736590209124147680611004457829143208408370593407131419693236474753622612620472290999982723196481851182230922694567273278077107599959258709339908216451486771470139642093313481985573266560862518575094798426212070291165772888574851111265990578392440431272939348293551709799853524116065013067653668766124312742053966224955624330807721321510211151198692883695859617685059751651356524563789067046267692473360756271976679359169680268905625576876664467917023396008041685445673155814446256494763980407281325801218648336324793192754725204710974555602592150202388648183883822342215489216940673787326305191780989752830214731875692120055717826032924838880157775248410261577911018959865732595526560075574399034621408261675128213627853824607903798882734585067589924964828003363277930805850512248373735362045090498519689108288711388277733467499500387934174182672534397264398361586510647295363657102712406238814352412738214455608142036691732035718186785976705303492175334421797035484160432166878516145780568191038741650466952058620563534032374062675510887508186230354102341368709197426851839),
(9531,124746147684619503926174540733076565776609601926898802513142869553185795774960944351511570995569623511548276941282819486306760956730621900868142529031819333115115633049735051008214096481829612884632848946161025655296365386276767914917985007954248173857028949072656941316347525158318250609224162046967213913500346320633240139963127469022758844428808590609444072999001783262194658417531803389272765166272943448543016351387358354378605531275827507040730637157235882847839952817198477434783817179263014187955257766254154941202715414377880869147474574919751019805446922486086130124641439728104576130673895821258815133886904763689129860713532820470867706007294407373759664092181810886166140289632438144712308264657405814890890554593722354721358462830947046915859458433319022458467836403953134510728041906205017400626353732872491934301433775353928435226147920301972121231257290150893261256716277312552051114751747983330876266802872897807426164012336641295828003612902925390844597236152332865172415170561526106833227713897188594340591349967964327874866959160696007343552958234225867601731778004836105045469500581310658851579127996127186280748894102772239324973092837665555179390602779857873176736748778931664800530768248233501812665707231533847473472164582102220871580221356968474043446671471866699377130582740422114965677369229031487602497815053497411465540439122330209113967495412712620639854918799621149861584307466809332533382677802273371312223008246895362164954187438227536354863236265449259514222867054723768477658925262465457317881694713418292501428549992241444034262235045273152416910435876257486994802504441170238631420259310123265130030779997975461173536695108528589112967372182707130465788660824952225164046272646122782535730288099029268043895022570738183673402720490059219712845368752041990818682108522788639832666220299816452443189957136240792652403511211538422826310523341694088008054594764821971165839115100120429037030696055164626607217216859671084685831232046398868233548530418081898883400475215689907730638887541826002462950488845556182194365839960235273676843311562454304448634963401737197354692156399474242460111658103958565421442398148795374492871076828264712935097059606718815864539781819293731184108824579195671853408087941547294953000671985500894369909515044753494233744089941708881761550967528595866500669155432431761508387521589170534144816199908440336428443296738604422620779483256747188297144536885164988336293914529729781974866867897258761183126596113905604577545148279141249075172383683226742152231712685133428512280694160823554345629819970867928254932173640720319166277947038987116978932117793114926516933983749032345769147336600136975349302930159718732631583950684387829693480869973919594016078031085441668710468359002726316632877439486449918181244314436001560547538064318326139348029900469027411324680515203638821216739228381876077619031655829209087)^C
Interrupted.
```
参考サイトのオンライン整数列大辞典（[^oeis_A002234]）で調べてみると、この出力は全て素数となっており、ウッダル素数が得られています。

このように最初の素数列を計算してみると、ある数$n$までを比較するとカレン素数よりもウッダル素数の方が数が多いのではないかと推察されますが、果たしてどうなのでしょうか。（恐らく未解決問題（？）だと思われます）

## おわりに
カレン数とウッダル数は、定義より$2$だけ離れた数です。だとすれば、$2$だけ離れた素数（双子素数）となるカレン素数とウッダル素数の存在も考えられそうですが、果たしてそんな双子素数はあるのでしょうか。これも既知のカレン素数・ウッダル素数の数列の中にはありませんので、未解決な問題（？）なのではないでしょうか。

人名のついた素数はまだ他にもありますので、今後も紹介していければと思います。飽きずにお付き合い頂ければ幸いです。

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

<details><summary>本稿の環境</summary>
本稿のために使用した環境は以下となります。
macOS: Sonoma 14.4 (chip: Apple M1)
GHCup: 0.1.22.0
GHC: 9.6.4
</details>


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


[^ref1]: [カレン素数の参考サイト](https://www.weblio.jp/content/%E3%82%AB%E3%83%AC%E3%83%B3%E7%B4%A0%E6%95%B0)
[^ref2]: [ウッダル素数の参考サイト](https://www.weblio.jp/content/%E3%82%A6%E3%83%83%E3%83%80%E3%83%AB%E7%B4%A0%E6%95%B0)

[^oeis_A005849]: [オンライン整数列大辞典（カレン素数）](https://oeis.org/A005849)
[^oeis_A002234]: [オンライン整数列大辞典（ウッダル素数）](https://oeis.org/A002234)