こんにちは|こんばんは。カエルのアイコンで活動しております @kyamaz です。
はじめに
人名がついた「●●素数(●●は人の名前)」という素数を紹介する第6弾です。これまでの5つのエントリは脚注にリンクを貼っておきます。12345
このあとプログラムでそれぞれの素数の列を求める例を示しますが、その前に事前準備として確率的素数を判定する関数を定義しておきます。
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
また、素数列を利用するためにワンライナーで素数列を定義しておきます。
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によると、フランソワ・モラン氏が1990年の学会での講演でこの素数を名付けたとされており、数学者のサミュエル S. ワグスタッフ・ジュニアから命名されています。
ワグスタッフ素数の定義は以下のとおりです。
- ワグスタッフ素数の定義
- $q$が素数であり、$\displaystyle p = \frac{2^q+1}{3}$ が素数である素数 $p$
この定義を用いて、確率的素数の判定関数を使ってワグスタッフ素数のリストを出力してみましょう。この処理はいつもどおり停止しないため、適当なところでCtrl-C
で停止しています。
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.
新メルセンヌ予想
『新』がつかない「メルセンヌ予想」はマラン・メルセンヌによって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年に次の「新メルセンヌ予想」を発表しました。
- 新メルセンヌ予想
- 任意の正の奇数 $n$ に対して、次の条件のうち、もし2つの条件を満たしているならば、3つめの条件も同様に満たされるであろう
- ある自然数 $k$ に対して、$n = 2^k \pm 1$ あるいは $n = 4^k \pm 3$
- $2^n − 1$ が素数 (メルセンヌ素数)
- $(2^n + 1) / 3$ が素数 (ワグスタッフ素数)
この予想を満たす数は$ 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環境を記しておきます。お手元の環境で検証する際に、動作が異なるときには参考になるかもしれません。
本稿の環境
本稿のために使用した環境は以下となります。- macOS: Sonoma 14.5 (chip: Apple M1)
- GHCup: 0.1.30.0
- GHC: 9.6.4
(●)(●) Happy Hacking!
/"" __""\