Haskellで見るメルセンヌ素数

メルセンヌ数と呼ばれる数があります. 自然数nに対して, メルセンヌ数M_nM_n = 2^n - 1で定義します. 小さい方から,
M_0 = 0
M_1 = 1
M_2 = 3
M_3 = 7
M_4 = 15
M_5 = 31
M_6 = 63
M_7 = 127
M_8 = 255
M_9 = 511
M_{10} = 1023
となります*1. この数字が素数の時はメルセンヌ素数と言います. 小さい方から挙げていくと,
M_2 = 3
M_3 = 7
M_5 = 31
M_7 = 127
M_{13} = 8191
M_{17} = 131071
M_{19} = 524287
M_{31} = 2147483647
M_{61} = 2305843009213693951
M_{89} = 618970019642690137449562111
M_{107} = 162259276829213363391578010288127
となります*2. メルセンヌ数素数テストのしやすさから, 巨大素数の探索によく使われます. 大きな素数のランキングを見てみると, その上位のほぼすべてがメルセンヌ素数であることに気が付きます*3.

さて, ではメルセンヌ数素数判定はどのようにするのでしょうか. それには, リュカ-レーマーテスト(Lucas-Lehmer primality test)と呼ばれるものがあり, これが使われます. 今回はこのアルゴリズムを見ていきましょう.

nは素数でなくてはいけない

まず, M_n素数であるためにはn素数でなくてはなりません. 仮にnが合成数n=ab(a, b > 1)だったとしましょう. すると
M_n = 2^{ab} - 1 = (2^a - 1) (2^{(b-1)a} + \cdots +2^{2a} + 2^a + 1)
因数分解できるので, M_nは合成数です. 対偶を取って, M_n素数ならばn素数です.
或いは, 2進数表現のイメージをしてもいいでしょう. 即ち, メルセンヌ数は2進数表現では111\dots 1_{(2)}のように, 1n個ならんだ形なのですが, するとM_{ab}1ab個ならんだ形になります. と言うことは1a個ならんだ数M_a=2^a-1で割れることは直ぐわかります. 臨機応変に. 私達が数の表示法として10進数を選ぶ必然性はありません.
例えば, M_6=63は, M_2=3で割れますし, M_3=7でも割り切れます. M_{10}=1023は, M_2=3M_5=31で割り切れます.

という訳で, メルセンヌ素数を探索するときは, n素数のケースのみ探せばいいことになります. これにより, 探索しなければならないnが激減します. なぜなら, nくらいの数を適当に取ってきた場合, それが素数である確率は1/\ln nくらいですから, 例えば素数探索の現時点最高であるn=43112609とすると, 1/\ln n \sim 0.056885と, たったの5%だけ調べればいいということです. ちなみにM_nは巨大ですが, nはたったの8桁程度ですので, 篩法で頑張ったら素数判定出来るのです. 431126092610944番目の素数です.

Lucas-Lehmer test

では, n素数のケースでM_n素数かどうか判定するアルゴリズム, Lucas-Lehmer testを見て行きましょう*4.

nを奇素数とします. これを満たさないメルセンヌ素数は唯一, M_2=3に限ります.
数列\{s_i | i \ge 0\}を次で定義します*5.
s_i = \begin{cases} 4 & (i = 0) \\ {s_{i-1}}^2 - 2 & (i \ge 1) \end{cases}
この時, 次が成り立ちます.
M_n \;\text{is prime}\; \Leftrightarrow \; s_{n-2} \equiv 0 \;\mathrm{mod}\;M_n

証明はいろんな所に書いてあるのでここには書きません. 例えばLucas–Lehmer primality test - Wikipedia, the free encyclopediaLucas-Lehmer Test - ProofWikiなどを見て下さい*6.

結局最後に\mathrm{mod}\;M_nを取るので, 漸化式の時点で毎回\mathrm{mod}\;M_nを取っていいことに気が付きます. Proof wikiの漸化式では毎回\mathrm{mod}を取った形で定義していますが, \{s_i\}という数列が捉えにくくなるので好きではないです.

小さな数で確かめてみる

例えばM_5=31素数なので, これで確かめてみましょう.
s_0 = 4
漸化式に従って, s_3まで求めます.
s_1 = 4^2 - 2 = 14
s_2 = 14^2 - 2 = 194 \equiv 8 \;\mathrm{mod}\; 31
s_3 \equiv 8^2 - 2 = 62 \equiv 0 \;\mathrm{mod}\; 31
つまり, s_{5-2} \equiv 0 \;\mathrm{mod}\; M_5となったので, M_5=31素数です.


もう少し大きな数で確かめてみます. M_{17} = 131071素数です.
s_0 = 4
s_1 = 4 ^ 2 - 2 = 14
s_2 = 14 ^ 2 - 2 = 194
s_3 = 194 ^ 2 - 2 = 37634
s_4 = 37634 ^ 2 - 2 = 1416317954 \equiv 95799 \;\mathrm{mod}\; 131071
s_5 \equiv 95799 ^ 2 - 2 = 9177448399 \equiv 119121 \;\mathrm{mod}\; 131071
s_6 \equiv 119121 ^ 2 - 2 = 14189812639 \equiv 66179 \;\mathrm{mod}\; 131071
s_7 \equiv 66179 ^ 2 - 2 = 4379660039 \equiv 53645 \;\mathrm{mod}\; 131071
s_8 \equiv 53645 ^ 2 - 2 = 2877786023 \equiv 122218 \;\mathrm{mod}\; 131071
s_9 \equiv 122218 ^ 2 - 2 = 14937239522 \equiv 126220 \;\mathrm{mod}\; 131071
s_{10} \equiv 126220 ^ 2 - 2 = 15931488398 \equiv 70490 \;\mathrm{mod}\; 131071
s_{11} \equiv 70490 ^ 2 - 2 = 4968840098 \equiv 69559 \;\mathrm{mod}\; 131071
s_{12} \equiv 69559 ^ 2 - 2 = 4838454479 \equiv 99585 \;\mathrm{mod}\; 131071
s_{13} \equiv 99585 ^ 2 - 2 = 9917172223 \equiv 78221 \;\mathrm{mod}\; 131071
s_{14} \equiv 78221 ^ 2 - 2 = 6118524839 \equiv 130559 \;\mathrm{mod}\; 131071
s_{15} \equiv 130559 ^ 2 - 2 = 17045652479 \equiv 0 \;\mathrm{mod}\; 131071
よって, s_{17-2} \equiv 0 \;\mathrm{mod}\; M_{17}となったので, M_{17}=131071素数です.


素数でないケースを見てみましょう. n=11, M_{11}=2047の時を考えてみましょう. n素数です.
s_0 = 4
s_1 = 4 ^ 2 - 2 = 14
s_2 = 14 ^ 2 - 2 = 194
s_3 = 194 ^ 2 - 2 = 37634 \equiv 788 \;\mathrm{mod}\; 2047
s_4 \equiv 788 ^ 2 - 2 = 620942 \equiv 701 \;\mathrm{mod}\; 2047
s_5 \equiv 701 ^ 2 - 2 = 491399 \equiv 119 \;\mathrm{mod}\; 2047
s_6 \equiv 119 ^ 2 - 2 = 14159 \equiv 1877 \;\mathrm{mod}\; 2047
s_7 \equiv 1877 ^ 2 - 2 = 3523127 \equiv 240 \;\mathrm{mod}\; 2047
s_8 \equiv 240 ^ 2 - 2 = 57598 \equiv 282 \;\mathrm{mod}\; 2047
s_9 \equiv 282 ^ 2 - 2 = 79522 \equiv 1736 \;\mathrm{mod}\; 2047
従って, s_{11-2} \equiv 1736 \not\equiv 0 \;\mathrm{mod}\; M_{11}となったので, M_{11}=2047素数ではありません. 実際, M_{11} = 2047 = 23 \times 89は合成数です.

Haskellで確かめる

小さな数で少し感じが掴めたところで, Haskellでちょっとだけ確かめてみましょう. 最初は簡単なとこから

Prelude> 2^17 - 1
131071

nを書き換え安いように引数としておきましょう.

Prelude> (\n -> let m = 2^n-1 in m) 19
524287
Prelude> (\n -> let m = 2^n-1 in m) 107
162259276829213363391578010288127
Prelude> (\n -> let m = 2^n-1 in m) 127
170141183460469231731687303715884105727

さて, s_{n-2}を計算しなければなりません. 手始めに, 数列\{s_i | i = 0,\dots , n-2\}を計算してみます. インデックスが0から始まるので項数はn-1個です.

Prelude> (\n -> let m = 2^n-1 in take (n-1) $ iterate (\k -> mod (k*k - 2) m) 4) 17
[4,14,194,37634,95799,119121,66179,53645,122218,126220,70490,69559,99585,78221,130559,0]

あ, 最後が0になりましたね. と言うことで, s_{n-2}を取って

Prelude> (\n -> let m = 2^n-1 in iterate (\k -> mod (k*k - 2) m) 4 !! (n-2)) 17
0

それを判定する.

Prelude> (\n -> let m = 2^n-1 in iterate (\k -> mod (k*k - 2) m) 4 !! (n-2) == 0) 17
True
Prelude> (\n -> let m = 2^n-1 in iterate (\k -> mod (k*k - 2) m) 4 !! (n-2) == 0) 107
True
Prelude> (\n -> let m = 2^n-1 in iterate (\k -> mod (k*k - 2) m) 4 !! (n-2) == 0) 109
False
Prelude> (\n -> let m = 2^n-1 in iterate (\k -> mod (k*k - 2) m) 4 !! (n-2) == 0) 111
False
Prelude> (\n -> let m = 2^n-1 in iterate (\k -> mod (k*k - 2) m) 4 !! (n-2) == 0) 127
True
Prelude> (\n -> let m = 2^n-1 in iterate (\k -> mod (k*k - 2) m) 4 !! (n-2) == 0) 1279
True

つまり, M_{127}とかM_{1279}とかは素数ということが分かりました. M_{127}=

Prelude> 2^127 - 1
170141183460469231731687303715884105727

はEdouard Lucas(1842-1891)によって1876年に素数と発見されたものです. 彼はこの計算に19年費やしたそうです*7. また, この発見は, 巨大素数の歴史において約75年もの間トップとしての地位を維持し, また手計算で求められた最も大きな素数として知られています.
ここで素数と分かったもう一つのM_{1279}=

Prelude> 2^1279 - 1
10407932194664399081925240327364085538615262247266704805319112350403608059673360298012239441732324184842421613954281007791383566248323464908139906605677320762924129509389220345773183349661583550472959420547689811211693677147548478866962501384438260291732348885311160828538416585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729087

は, なんと10進数で

Prelude> length $ show $ 2^1279 - 1
386

386桁の数字です. メルセンヌ素数としては15番目になります. 先程のLucasの求めたM_{127}の次の次の次です. だんだん扱う数が大きくなってきて楽しくなって来ませんか?

nを見つける

問題は, M_n素数であるようなnを見つける事です. こういうn素数の範囲から探すのですが, 今回はprimesパッケージを使いましょう.
http://hackage.haskell.org/package/primes

sudo cabal install primes
Prelude> :m Data.Numbers.Primes
Prelude Data.Numbers.Primes> take 100 primes
Loading package primes-0.2.1.0 ... linking ... done.
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541]

おお, 良いですなー パッケージの説明見なくてもコイツは使えますなー 無限リストの恩恵. で, これを使って, さっきの式をif ... print nでくるみます.

Prelude Data.Numbers.Primes> mapM_ (\n -> if let m = 2^n-1 in iterate (\k -> mod (k*k - 2) m) 4 !! (n-2) == 0 then print n else return ()) $ take 100 primes
3
5
7
13
17
19
31
61
89
107
127
521

つまり, 3から541までの素数の中で, M_n素数となるようなものは 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521だけということになります. 1000以下で探索すると,

Prelude Data.Numbers.Primes> mapM_ (\n -> if let m = 2^n-1 in iterate (\k -> mod (k*k - 2) m) 4 !! (n-2) == 0 then print n else return ()) $ takeWhile (<1000) primes
3
5
7
13
17
19
31
61
89
107
127
521
607

となります. primesが無限リストなので, これを突っ込んでしばらく放置しましょう.

Prelude Data.Numbers.Primes> mapM_ (\n -> if let m = 2^n-1 in iterate (\k -> mod (k*k - 2) m) 4 !! (n-2) == 0 then print n else return ()) primes
3
5
7
13
17
19
31
61
89
107
127
521
607
1279
2203
2281
3217
4253
4423
9689
9941
11213
^CInterrupted.

18分03秒で, 11213, これはメルセンヌ素数としては23番目なのですが, これがでてきました! ワンライナーで(M_2も含めて)23個ものメルセンヌ素数を見つけることができたのです!!!



一旦冷静になりましょう... n=11213の時, M_nはいくらになるかというと,

Prelude Data.Numbers.Primes> 2^11213-1
2814112013697373133393152975842584191818662382013600787892419349345515176682276313810715094745633257074198789308535071537342445016418881801789390548709414391857257571565758706478418356747070674633497188053050875416821624325680555826071110691946607460873056965360830571590242774934226866183966309185433462514537484258655982386235046029227507801410907163348439547781093397260096909677091843944555754221115477343760206979650067087884993478012977277878532807432236554020931571802310429923167588432457036104110850960439769038450365514022349625383665751207169661697352732236111926846454751701734527011379148175107820821297628946795631098960767492250494834254073334414121627833939461539212528932010726136689293688815665491671395174710452663709175753603774156855766515313827613727281696692633529666363787286539769941609107777183593336002680124517633451490439598324823836457251219406391432635639225604556042396004307799361927379900586400420763092320813392262492942076312933268033818471555255820639308889948665570202403815856313578949779767046261845327956725767289205262311752014786247813331834015084475386760526612217340579721237414485803725355463022009536301008145867524704604618862039093555206195328240951895107040793284825095462530151872823997171764140663315804309008611942578380931064748991594407476328437785848825423921170614938294029483257162979299388940695877375448948081108345293394327808452729789834135140193912419661799488795210328238112742218700634541149743657287232843426369348804878993471962403393967857676150371600196650252168250117793178488012000505422821362550520509209724459895852366827477851619190503254853115029403132178989005195751194301340277282730390683651120587895060198753121882187788657024007291784186518589977788510306743945896108645258766415692825664174470616153305144852273884549635059255410606458427323864109506687636314447514269094932953219924212594695157655009158521173420923275882063327625408617963032962033572563553604056097832111547535908988433816919747615817161606620557307000377194730013431815560750159027842164901422544571224546936793234970894954668425436412347785376194310030139080568383420772628618722646109707506566928102800033961704343991962002059794565527774913883237756792720065543768640792177441559278272350823092843683534396679150229676101834243787820420087274028617212684576388733605769491224109866592577360666241467280158988605523486345880882227855505706309276349415034547677180618296352866263005509222254318459768194126727603047460344175581029298320171226355234439676816309919127574206334807719021875413891580871529049187829308412133400910419756313021540478436604178446757738998632083586207992234085162634375406771169707323213988284943779122171985953605897902291781768286548287878180415060635460047164104095483777201737468873324068550430695826210304316336385311384093490021332372463463373977427405896673827544203128574874581960335232005637229319592369288171375276702260450911735069504025016667755214932073643654199488477010363909372005757899989580775775126621113057905717449417222016070530243916116705990451304256206318289297738303095152430549772239514964821601838628861446301936017710546777503109263030994747397618576207373447725441427135362428360863669327157635983045447971816718801639869547525146305655571843717916875669140320724978568586718527586602439602335283513944980064327030278104224144971883680541689784796267391476087696392191

という数字になるのですが, これは10進数で

Prelude Data.Numbers.Primes> length $ show $ 2^11213-1
3376

3376桁の数字です. 2進数だと11213桁です. 一万桁!!! アホに素数判定すると, 3, \dots, \sqrt{2^{11213}-1}くらいの奇数で割らなくてはなりませんので, およそ2^{11211}回の割り算が必要です. 無理っす. 死ねます. いかにLucas-Lehmer testが驚くべきテストかということが分かります. こんな巨大な素数が, たった半時間もかからずに出てくるとは驚きです.

さらに大きなメルセンヌ素数を求めて

とは言うものの, このM_{11213}素数であることは1963年には発見されていたそうですから, 時代としては古いものです. この後のメルセンヌ素数はn = 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269...と続くのですが, いくら位までならすぐに確かめられるでしょうか...*8

Prelude Data.Numbers.Primes> (\n -> let m = 2^n-1 in iterate (\k -> mod (k*k - 2) m) 4 !! (n-2) == 0) 9689
True
Prelude Data.Numbers.Primes> (\n -> let m = 2^n-1 in iterate (\k -> mod (k*k - 2) m) 4 !! (n-2) == 0) 9941
True
Prelude Data.Numbers.Primes> (\n -> let m = 2^n-1 in iterate (\k -> mod (k*k - 2) m) 4 !! (n-2) == 0) 11213
True

これくらいなら数秒で返ってきます.

Prelude Data.Numbers.Primes> mapM_ (\n -> if let m = 2^n-1 in iterate (\k -> mod (k*k - 2) m) 4 !! (n-2) == 0 then print n else return ()) [19937, 21701, 23209, 44497]
19937
21701
23209
44497

うん, まだ何とか, 分のレベルの計算時間で答えが返ってきます. M_{44497}は1979年発見されたものです. 次は1980年代です.

 $ cat a.hs
main = print $ (\n -> let m = 2^n-1 in iterate (\k -> mod (k*k - 2) m) 4 !! (n-2) == 0) 86243
 $ ghc --make -O3 a.hs && time ./a
[1 of 1] Compiling Main             ( a.hs, a.o )
Linking a ...
True
./a  570.68s user 1.16s system 99% cpu 9:36.57 total

ぎりぎり10分で計算できましたー!!! 次は110503です.

 $ cat ./a.hs 
main = print $ (\n -> let m = 2^n-1 in iterate (\k -> mod (k*k - 2) m) 4 !! (n-2) == 0) 110503
 $ ghc --make -O3 a.hs && time ./a
[1 of 1] Compiling Main             ( a.hs, a.o )
Linking a ...
True
./a  1083.34s user 2.23s system 98% cpu 18:18.99 total

18分で計算できました. つまり, M_{110503}=

Prelude> 2^110503 - 1
5219283133417550597608921138394131714748003987111696388844721857021695621345566328693730284546120701185550350229748838662252951341253421746795073087191036889245882078365188808677470720357783212747307528673196680088458323693474572645646430349088271293578783855910006177172218945638975265804307407923864296665887203966818881644127188326278536823185302433682452220866505473927329966261635224705976307336848031449051946470250326355850564065070219415063390427891641945141848406032059956642759451697871131937435974734468812612404366795155477504403442852091868360651937341101803746125038414968100853875769649772568976533115626733686633581147178167854537374386645054536421581487787680673873260827329457946477205293076461503204195229898682736527831015184366661152864587615185846767471910458921833277044360716991019765678686642856418011096226793070226165298245200286805907696043158401359233205933894872270757840780311842993502030651236226420390626397948002732496153425437136287482563891064276318845679420730548518354628798521087698057831570193388325181647160191379350631674091897212262818278445060746814976957862342535407548922347134501697060190457417366250455037928704152728620313194049459090938561074166466321977154209854449604435530303555162486890044423150383891465784220859099339814855122982824292907630042351718406860216298441018976432899012907690738344741325809832514370637919675751564228983581067713001959082281741038000510382863445395122241581297039798297231129157645252235222643331292666424360475348246102972693436258291783024959062081981838812572142511803956525449888847112458483851365748838790507346393979150203170197392307844865039294565185258407625913055060713900922073408886771350586379576558646737634415678011238370510372009244595665266604273647744438936460505842615012921299723039609880229752363633215766432725435987253902189301146196983131735602940755230848663445117927665658368356420346865950111317140432850742151588086112978702994240762421583385188191350001231200565700667791389021354205858177467953946405058508219437914852128789874720946029689233060816869125386142828340576189232460988484979947357301166335302699325444851058733209447959819326191635260772935604990851134296788845298869594134244897534525730181304428393857426219940590672281276723518776582169544067334705480920742604001168622762198273693428380553897726338361872954339053214349828778842361781853106705246246112826667187778644452294726844594574918377285572198422309281050239527692661557089591842761278181057933278000401648351356081767219918593264919576995069142249170223836224702255068465253482078539098187443071918215944764927958379845359365240314888899686669959635761817082650578399550074453202478150863419553174171457756089567615842152519360157327308360698725072256365040969792621539584036465460483849963364877060077099462804508783747443748521994786797187208616764402042119167359653346884051067448362794008940082341100994444181614418213550484684610370257475208798374548203571375481853250719794707737297289106817344273543178234366780318872649407377187072730875789746785084870361011603837828596063380436934427559741399079630414229895319266149914612519280272823995869813896972841782561116929003166739744612062920048993540969166539567069660783098613110181470263393931915610974133757611745434282513504673223466819904565802892335444902334736162918420861856512137424964551732430578193645849344558708572144258113789862433670385490704828913699643122856631354937003427216841447763823770059461987956351233769350148968100975738387546952316818146789228505502633995283191008860757224878910306387822619841228487510959391915230081278738478964587060771579566927543809518001023256799064843500598047448092769672112496204842133809466280596134763991644871105523092033002144386358014252471014304933512315525855464929326002127213531185766066959495012425333202747713991260204270554711267603519448421573364790583464599414079092630562559049529970854068245838058972902782716657303398011079570340993681978602146016260731415392796070099302915857446184284492338184900216275081239194286014920899856256657301752101626142771298248388740363577822427523530496698324976089830267271770433302612928863492471906219529755857499316371756474544420059869354061575644223098201545184395439200495673217450313417117617847652221602698562899339244049925561342019071478094656156692298970839460894861033151782740390479827962701287562750064371964027625677232269761059437891312572243255115277459236700764735484999611933639503357777150911412524162248723431001175341571889620281950611889360490007342476142047713725454664181989231971490749598648207558524714435823528801963270106690871228191029010653103641813849875532556927413266316430858480756663121051354045742088249205913851178254507537826478453318305024009219910295626907315048440247469362688952564187604507596955998539879540191650667035389903303539491945912991638480371092660980900779331006985407097736196322796802626314674103633849922510328783478267810901914263565926331779841234341557171622225997181620978940634079517600724299703807480826218272492787987996449775919730062045133756639675098203801102844045509184301293110435898724583832877280053291902793566611159694010696228754063771664996095787812423235160254094397254125391108561499107218473169425539288882278513046714043407319219068949468172288158436366324718101955588003305237184455698919819573905719538347163800330464965350384709792997192244756941845904840558998378244156887880300448205407800127556895875369630084390234520371765003246158785015315017571785917762532744084067842701965827402808244353884339008814967552009585707585930199840219015697516779314043811604512416068649879615394713114751547609261771572859645987657096712479535823843294183064535902637275082610415092299017574941271253130505203786422599954246588012241306721923065806890956746479029456426379831947739549627656030524765928950331915786548762562328083171649815759067667516704588106333557929886109775405451970851524312228546878654197960754013026372859274195306213445266974071935007298641663616314033269884667955620111309575343217861185691394535706369722324626811632890909545866042361012706332668814574002886089482457047069792424592306019142598077930541370804870536746764718703756101315103402498751465888822984172394408820511781517872764205955480840803205483107196994531153451950583461658019927392514304980398554764126899265779300584663624849476060120748057077601917768935135399413692676935044564082114422782031238459636513796777783240689793652195084844112602537745301670926262492546259891100605861657849178159354817407487478931490801670084160896230614396947358808585239738180232916108965188695590452014440883246282331273025204280241388275626868589146434017242042021840309157931211813867467410616665884021235841658135804262812971569692978840911041081726688997548959744100838476816595900886448055145128729248758017622720446939441868806149463547490282358163060869321029448427336843444204243515131163997504195558101171711507769963992597654450780344736522510720458589263076972478692329843045248108600587281975177627285940306164121502635012077569268382618992424728960577293015052952673828205703560705531570968207693918162579001277852045222671248467264497211694624169858653954833760474356592813229626505890505354134635151787948216365327901508819411785142152833432627728196612826280426493418494354332715759068513275267431843575112419627392320363061901254840884481021434867813860576688519853931319751135758131820799087677142019115811990730366088825026705967895514998294919077502618682136729305438490581592513614486145775140327508036090571478743601469925100309139079297515952651542458232938433515373375950850550901991034330759166084076529135116217558488006169081262614724001416460184550734010510439401941574568085146192143492506415272776443357698527499205920188662762249868506706790255417996527667702229820002517515132500604313453961565148329696168408722070991415891197822983055527178331435752092793749578216888157239353475522775912927356042862965707543262449655486923996924705591337073224376318210126946003029950798609319746198936150871899457221884322874567454461496564928537222435306561085047593752078023600242671756689325995928149581875252520763579817026930285253426477336763345530568689085250180550154101605421383187700964376878757622750533373212825816132162211868283524579681634439593450986867763869643415251323936438759726268396342400872357875606140671113018462893096298958797589424541173503692724334748353008327094914861878511664919938546847178441862054576369254241418859359997673824895122765329123670077022738684049477623013354061028433153254934063535551741212284366260945270521912247754058217884488363961097022478341654879669119039422474711453560713897625651902545874268502591066142164065201145925431736206354259681236123782295953421146036233320706202542802046619108202210601905731146091245445382171357426106435391257241247454462347439843026848957008024971000728739612764701650820745557077521019023663558599300030098767733318296212267791898625397335732188623883018403444800160899513961282647304597132863167285590498796533476782410947610427209426752715165869523201813729432914018824665609813028365558164278232504560433356526239382675492262016251904662875264317012930368279881629876130193702623522145536349509128321152604697440779119762879148757698034629396659742679932515174448457818126556092989541554952290365028495230047528076275510817038546562525047710332555203233199920185022949987410470356466217859084515621715814744078133458401690440973632241126599062439131812445571831195750648033599093956943441851996548154573576590514545685636340512675499356488849184088303003552394888593264605119630946263677978036135351207949364007605467423376526619612619708816827290437234533145243193982617179538944195289996255922150763223450417133426698647254499958391012721079500439885784286798208974008103527525798997123332642177873443192384052822584344480513642088070178308582176337990887892534104789618366717917812438060665661167665404965586160176289888772605859421114049525300201228676436639481076283265730005578214880015011360655245823382454752145003922761176793176860917776210439643878167980131866355801604038300074595892903069711260374423051281344007558766331046287488860890165799881131335225761972320295123203858013644354191760983660411514591556087245015247095059134575699390131848115923393546207714885164019016901853980277478069412283251180591353065417541684186732481744926646830063532770223682901032098939874367730081608222995311565991349593473838913982760300921230171795098158732723221531830432950856290007606569936454419490342239200539463842248283452814424560739976630988284771270307905269366578858096343588951243106238857167947528386703433424496340998917553854024438991607375269389374913330083682670659443407860772695251623499496681365629776020551122942020147967701233170971164565472853581741935610647156261442384055202447461052756324428747528360646913527525663305805317605697845478025727444978208876304016703016714358509239681996268496084710105913501244180545330136150204618138276030314331596601730799483529675130449879705835640253303475624331762638560430115055607878412858576302603986169310524352365499033295536709243931053749941781216666676849722636559670195363085481243708523193553203468045286868687572241116457429815818493904095679641472113827308948644547480831048764793974598219440703597760450979730526784548348528478981126440100335589564511210080718338720668292455434033777745737329876314888817706542072502546494305848810503776519846387216503354243469167270879296292107216458214318938620321916242246419321692446400984188491107920927885540506689869333319550124121531961967637785140171734782180729355318808490350500625033283733486196374702998782686801906999697823374757576051529793966335783838480147339455936666307689959754516238886484633922071530920738265836010765063579426399950855264177745045360357798058459894165283550388823443191581207989394041699662793780547315971739049404334692755294151636293340145938553396184505733191406711054032381118628275046047882209953569468206198402245769816997661783644787630668623255824944069180939286643322416802183432233004319271910928887103445885987503538865217204903661862802860195870304417691385203611714502909568732628386772288321101737981952503908657510268626233956746929677891343398693108833172456699933150924423772966255944302389807107679885786647357304745578601085057960865716938291990517461346949345588040786702324417668600590221394530822148873687230167938390325669700283394317526993044736683267934127199505163235323859199411955121008904060213692888039563072698548205248121582170609366676650613275568505188142341951040544825408567652588518558585906517079389070196584208638012431962769864845935249042575015105851544443130170041766567612163646516289495143859625803124769550214130927323677706000126547367711187358932033441900785783804522154484942994157381726864957796374317989124569595601718921105964163751627872221731073259057071671114748468089122507573108262957947467318792776413329324126543145101325421150794742401365275910113372357193932014729097560576009796970589125132018505242435049021999190501788022198184026497465786915101220787507788225473024214784688957422903036584053396565930862638025590443803676419182052755763247523593787911111805458919102073103089396698803580832272305421557256437585106474206596838008830418989029710524037994857577266645231673510146636159675360017287419793516512154770352296551724089267870934698157466371337582272478646002708199948393973530096606317370926740805647404584433338728747758787449799483214725657610666333689585296497210167818951260851947688849515831641598466707355270906108846342509978285495939770115709354671057029584411551950522223690988001144258550273342538920445248869080701571113838148084007434013046317661547673470938239992648254419143712021487373234721473431991119240737093415252683167731028644293446183013582418288512964757209870743934472061672081647165005618387786132070667312550890485505403716544778872192898136970375010274357427081353375089376782143678081963907852958319626245972043515519964702779613588349712822541044839786471769356045279301841071830155320088747687777679036500221131503499979504575800139618953991070532853066560299227796553133876492788471387931546473614682116573648894401928950676697741655042663160432049093844423771487564784140078212230826253199064718726442268863914621131705728934425922395324963886584520126767794172859617162078663860451891957154839984407506434112876487007685201545638383474365134030372400663301518149134174638959201138045043800404284330813643848642446512698685902193797912679197289529539539521449810714442565198278216365455011915421576258652895730215900302374917580018053651570992106524489590657900587570625744379186519421488520877903999425363706741239465560275250037105968752819708824658441551336227303560387773930367130490497737191158528370720480058629520189288387537450696844122530346385463324853957538538851116972967092999704879118387132854330328107827693937467287347538274594902731750244394464490197158501231457149736399183870541715899012829219207981459949070532694275286603818617396937996420009899103467474958498036633243200853183286600971353965870623674945011038720236579523799590804766006303206878480096490186884063849257660694003423814016730899173658625753071641084366116314733298531659941798174164443634526932808426209736448529423480715074538236051281356370205557298537804473520654085821963484446213447093493478105436390068371505767925883351873517238268285535258153641140173662913456752338996439694947459295909147107537308689499566226198769034114271441514924367202736600421291624626185612691833660991367335133933654955867668171632815842871816078544099135459253981792139261130052057679273911020068865592888176034404772670409620548469870812571242224766785903597368375801740705093657243994581280287940391862903474036903047520272297974628936388853144078848752869911250165499502068388850141263761703550768959086097423353432540696692709809622981960562366641400485907192259570580297159789983018699762191288261917134227355803146407182277730848943505098284684041046525667958811928772384811052101237341231033701944375149189914793181092191086396866352334748449769231395635567602908214466139766841051481060326459152770437486389005272441707123755307243210430531732049068456449825816806929054541919639401470321710848514620892330591633550185766036860943234581259615801049107411151644671751101708383202164583986339558524487030803831599546653763421487059629455443224227763350548492160495112475253019491484247273334953981051246738563060559894847220100004561228283032663663490607024016762521772414059741405138019007589458785491351732514198581173710128958313941112314580263851166875856301200483439518868872555780218919671127410917048448654558133796680189124421049177485066749163860074544198930562352634858744568269433666369070064786744129288067330503196284249790618086683008925426583395932006123930513722216691405542976461576026663694155384806250863078586676024022532674700237232099790022638523214039980502078812635646671328978030000908199777004485283855464685557392854298946097263278796029029961820226986513291912643982774325100751655317537416095015757565889337111322486974074849380906325640899329823738483073861429628431453876727125004662470132712133930125059635927596905880616217949752457825440734336306740027529307085515497399778432231317434153722079091833009196835600565804017627356689466438397325852365287526877981067745783317426861460181565818435176585563553263968772882565448961613374975233510610270510643855817864951332096384347681579804133304412738579769371697995736436783801260965236316121819658236938848772963092662966740383338170368504160178690538808181150207965829454043970734605092665203282180306998737108740832392018885366175510813263906162171005118202219769546450218933629837449315986873995014879164622028047281551856288025869366226377962913079159223152980479974082188868134816820741028507402946930810315225846318849761982037990066600742078985463760789106179824322081072404870576639155178597387895741078337970325011843427140903118912861728232683648500345589286390175032466675195084882765161130942389193657015081427997289345223523148674977428470938294436264427377992263874282907014732045997521204039060022970634867936562050371836147130070902356551551316667000212465890035317022959564724972037608536949462213866438499643572609436856201172162249098182377970815406162324050253705846134150989653354393374265505371966391919009566402477187481459454261412338219115016224152566657471830602849081762507889894286772740319563048102338426499339934988291650899581977816703568304505456412329805350562463820858908729713680280814714554636119382888658716766350039873582718858924117791327355333060161513935413057383024626266388104235168826332573188570849559945315731231480139024165079490103997398738515187430543249422093761887076959636534766976657766190468183508532583690193944749450489143056996156898388636551440241518490912419187703156009441384697748060593244163827938361962226484334594535539173840754798551270516667050496731065869507321920919270878338465956919689177567361370314710280030473826043672826789413194236074292601814069920257625928283832406785075494703228337816044689608816258562393204100895940889180970760107109380326213421017610476805064077669496648922573499327690724180178120388273960987627968879558583043095376705550199191021286378462589686405293702483227357466451253247376011216255490247352656747435617419406346634947543340002158660581492596821313105549952810516800577681304284116785753044174476706869021994353640048589565581924137759347425774607724917148319421422687770421201675030116537294507236323292313150944942750893948610209118785264533823896568610555711575854192944536266330714967100611360624738995194581459406070820894872744466524729935157031492175464468567870881582761271097372624220434628657735130065084550092388586761683200773265886960960452490687027022830049586277869226263630175237158843534292291003883133850812783183100571495765339152432314167957221029138565573829899302195290825772526183743964173790228611192501654082144891830346172659991051381408141257105960177336986084842925975783181859299822502665565744896999350400858755053409643775663357955071862663255836966922465364032900847592329183798408398517577465125941098264076255091992180073626578203277086816138537028294667401704649912771028983643381623990666129099900254845625598466469369682697049039433896514622229694939511660434043154654341126565779759367902111555908911005947707963951247660462106373039251507912255600650920348835192689776594379488819932909742973567973593682776666511083338402742981058837811878150559799568134485601106754399153655680390181079011143615717606599353069113138221769583848263405849978711261082149814528219311655215231477674291680352723643693723563267709046427605981346289180013778059340540079409045640365842128981588669726980929890449590897770770717662756557321818635408920540448197962358293946973145169436334222382843495671076759497044546060643800127428205900283277440700839560328910569409904424449283012770825521878522632024245620547645717447254379107155964792664126225184844373849325631505412119004097493480791410583383081107888281419099235779383229680188384017779292617921370922372983282503298791017021921784715440301789087148507824536335557675207298935023348409468791607206887572163473596233634095514588426193776677103790030103697798488340857651485831498976810338247798891274171430792711417218119018685594870181189724154993802014008520621181498724733019671519274815607394471144930910973953871874677234320837673786173747996926108182160592819930285028243565270434019143599764939825434835631361977378834574498476196067276279197970185482513387075992762031284719426518736333645560539947459083154992047508021177432253410186114503046573992891136350397906727213151063042796603505508078503029848207956861976168707326309643927627932082478629958930389043300695953852245762426688198844500968552103443945388825434581952086254624804849323094655174896563225863492656231228848145999054507558064876783575233406881642671081875445728176973719623510405841272435458186174137551447332986198005631148179254729286590093654809867706726135218368269085682415849010927074017886271791094281967768009321122158979102288222564043650174535214025103753469650857266570607612767932187496888032409095242429364768509011462430863422253155131799344313616840024345057582809274140558256227759257581371536142332899517951052968071988191897884803413540626817984476492395370547098850219684882276641367409472540871594231816700092552991708816738672526158318251399000404719419039203630576102697834973314012448002803604296275826739467016237569391742822931453251705873513636865215811264417093048041562413771425101516307271586711402176333163244449446241366835142172999167198149195445076785771746105830099899755240514179074130483590748328925726169836229219135059115543674794729764757528954732301547753091360598364488144583854075666742799233901477793810708349408436623037613251688464857600837871310874599660539329826527399852230164943162201693782771653469751274562245118306884929923560792884211974942868001005426031939457512370244462812148016201342630473074456267159549293867053767659038056779949088426976254034728077254088135636860477186686146460626899902745613278153691400038339669537740544826562443805626535786384898572485701425917432386986347545005288812481364181536338248364278398726496016692123724237943548545828896728213046892088065007581346307309209881633136251506534455849280057342437035243462095729482589560053307406095527385109856353586250293946996179453801457868107800325660554532815889874967288747905456479104063078963446408392211991919068709916650366427193521435598108874243805361630829273485118140255826064152007353462362585456695582483253258528935582247912293014030259075488692057966145622502275707411579967571940743724826280576348051831482225559303226913313273222907950041784172300547498749060305878597291391606248972363355290948450836366255126157308403661054075454235785998143321284840030323563674035582184135793969720132762184242168341237392013032814153508891929231249031814578555987148412261004467680021274080915281269245527358835933371407227532308886439039983468705220620776921285207515612726428375426237913651622946234427409596825985581043754174115704264121004641271992679265413033893641001624386885626557671648182297944501373983864934057502341197478541199763789436638185843621570691204086149963373213056836154420869373597108314030426861451170412906079361626709359071741472975878756611036628962564131510773383998510774234687088992540536801810312009857409980694442074071368789046025521655489144964103881538946439359229988944312506134360805262745863808061869660883874870254525608385737401649750056276841658403694887805329366370830594546417565156055684539618472323821222897413937507741026226089596583549804469233405511618762392692059158528940278631113978465479265717747579601226777431147475637428062537631976626723681685522162724527759014616906930247421641947237717892852919071511473334229604683532898578628709926886572101867418845888405030606641737680827364610079316942421258233285125320063076534522312971471190655386105932096367520442927148501744391319945868134556799101897247505920799352053517687463088862122452649397230334908938410526023688356915746631269692332001052996469934456965145092274742595090221896958122113128807070503152302237929958117399858228931530449344428061096653254595757996596012868178203613096503557726524712340939850503491212011915661283110007772667503178059477499819303182705335332834624459158622179543934574194844832941235410788824896970294171227029654839529716920953122839133725722885792046979734701368899651860091368672457694068705142153704665956590116443066776198119837317198038690756679423778649983031717953241414565639804415349200132200388959885387334859365611381421757473594124140300845948165657326321402045526457877175261783902945741916463141522561420203700933323680476307717876485388538676825388861848354773776158304137581932840046496698754994538681513128446619105733675593860631122275044806365964738480695283198893795471985032076312138217279280685956908551225895651949636997717323872407213019526947214106014685651896720810620041619457350403927319816530507040458205468686881230845683976768482406242102360072859068637840237080897680414672874457279137290351731285361826730747132309723457291984363054662169783469965067810677272716989229549869544997643420048951962117330583406227256546424931564492817317988500941141515774213641259043678844901192292384108515150131680045281832808388783271580422344334093295411984846535779091842904018189972599953261108377814593515723506074528068379258018331670636324449650928795940284933846400055459917356112116335784979086949945956369581741604812238482252014218364035269595199869272652197509591599816699129577988601552450772600803111730257689434740396645678128683234080110444791146574502596759538726267567009665497064869837428440984372682405795705294960282556025175630442242188965858646033509764922752662123652688977422399818270845289060360558386646605078985503263150878101365939532848349218710579326324704979570885404956464093057902572550952611083546856831967686482879514544641366849189646088116922576717467199925666186734857012684711404619122222064933395604978601744611743951113455953556328610156977263958739929187328674786548136811449687282949959464723918992516804733474011918958194431485725908061897509325645763342150537353562047224435251469859024539544189504439300849183351131681465155500713348848128795541773814600838142333161455411590379382669821711558360682069527214815090496728243251582786643214565620855793063391148893746148386079869990725018691105346934009990519445508612266631423508661251265674502497598756950398610432628407748730127550466119774356165205370842865986184667867735553498989258556008873856154427543324162434290854221385621825103918209962411496521118503100393801218804498094335898100551174651127818634061508921345797071094228891630661197651503176297804083407503387958738779823231728054874323709008933134448624438426846944206222892217386031225046088111368006652541888421175452254177582653499369929651138600800741027340620230487986645086949202737931216665994821930610870313709126952399737132540385309975814913154995423990139861558072123394602975459760316483377007587771825828734693080155411845165392580769408122778403721414643069282531176939619244341314801506617973949652070744757191107303628412599066986095533824720205929364949877803945229268870501245351146940626053304178852435521047034575113667734617754500661963818241921208808397380702506120671386228596514804976192096364433057894515026542453389519706976703667448822190555676718700117911969937613026278777664685898739837320198293385475856981545160467595781051059780865926310684871742256366073970371133315571897122174711575709464736881167901286125630981315652760228531501360562481714702756523436424625827221912993808147277963411976521259544076749554395312420787932593342283316285195016299514530112793605661009694234819494848120085316782419587272850426169597578713913838119633794226240972136103757985813472492983733417625435292871433706976344722792941015783853475353343652708407894358944520772289898872674742740484848339023165449701135009722248795133268731580400777616995446938112267988973386493287027448125279191613549280379125833943633785510826843274216751522821192213364520504701441736524853373673052775993304466331746228693662454820127855966813344427298724428725099997883815935895069759266742277754452785223198225395420126605324413921784656592350591352564504974300115154753203724700562601048897858864627332306107639009429847348705213685734646779666270739036757264798706366717082817778569182345581632626889029804301732837440846709600095468860501877676107363490475302176894215736152697335549229452050423251959642216005712351909883737110650640462571917763261363644073123974043524360604898099425172889556529695558739041335141026988248048451686410941948124137851414856210522426849851233491932732885967027530009056057402771477463563238426347491158563391282193749698317202444556006834819749453954930404948709142513769790815924782193134271436422848089193949751296635731423357305077059680607286683946238768086916583204287837660863511834993728933593808937204730088504695966202855914649160950495261084680473425111737346349089985911777231516870873939177555617687920936211839656465933603741490983524784059822082904379182908646050311226555221525131353718590197929076527523296879814974636095717173139423128292926745910753622348037564706386621357860725673799893777383372393100111289659123976786185291639121811380109387605587417307703776842374480742015933414250423785034404998958032376121677351175947202529445445936401420825684528930433252944659624845238478412682964290794197831339041628289280961253295881492994833187677795657247184627306823031754751592427656240090519326492351411153855659203497653462770140468613285037394262078538365518225127559150816567130846249692140367467726431422359675640846252299768341260198868569774664974070091355790173618477171135158031965745221288778483338621173773028791022498552695770080528271231903603215854033182673677732390815788923291201535547863632447795360680745410104801549274631814955304414156023001230861971851434410767058331813577376627313754621707570235149793939169583495718558280422601398926136081916186955960444642957309945276924310364925382102688860755193232624742167899507748620875816486118194585172223522356546049903369154893081468084918202273499880423009423734442043442694934267899815854723901445461547805887439744897656866467087013666776411222956145372700199126267175839336354697272954222295918286846413156648851519834374935146754481915258661178319472647102971415994832283713206319621947821269223645603105450532514841665948015197296250963551144435401390468397855102373334213221118521208171197843587891059348455545037263508688267131949763073780308342035220698921760014114069597372773230214821135322470353203957525649770669877565941375280100373163475862528264915280311167525218394152080634184302889791962473579970683141581471367167366398823859033794514373537111820368570242834580684092034921486224811443675327825350442872215580087814400790012284032893430901019879204063101926784770326535783846811529051794156407477187456890340466432830589923960026722742149184270686318060077977380394275787685722401626576051886422849376510886640359204410603860752477917290151466704245358220930544452648689125784308911759593267785772940089830329201292694811210391594173316339596562858769040282000587564934571203658346546405901077095655346497964058797249584413213202466300584026658522430836645691796402536511023785188368038263793065285747473834067395416528863125144331209051730445172788920025966144945622750727071769079507716188347244949699706258134052274553137262087312709718464178196050537438923956944269088448615730140394291854648304518460320125944437200877090952384451980339029248077677303351618474563787853633449012806063571691919714073305893533618678943338276923320031837250014518352089679990940060604580188868126181823515089965208831121909774681600755207102403082769222517881229388340462909419478821493296594574233267938694393658576591717632521049235386262891417365005921683706006284478099570816690996105865157573451865316909883613381642675289627644828615531318743459872161460363137442976038994898964975630432955663939378214779188148425633156064943513557006413191010833856272339131999107769951621083465515007

素数であることが分かりました. この数字は10進数で

Prelude> length $ show $ 2^110503 - 1
33265

33265桁の数字となっています. 次, 132049はあきらめました.

まとめ

私のパソコンでは132049らへんが時間的に限界のようです. 何時間がかりで計算させたら出来るのかもしれませんが, 1983年の発見にすら届かないとは少し悲しい気持ちになります...


でも, メルセンヌ素数のココロは分かっていただけたかと思います. Lucas-Lehmer testが素晴らしい判定アルゴリズムであること, 見つかっている素数がどれだけ大きいこと... 今現在, わかってる最大の素数は, M_{43112609}で, その桁数は10進数で

Prelude> ceiling $ 43112609 * (log 2 / log 10)
12978189

12978189桁となります. 私が諦めたM_{132049}

Prelude> ceiling $ 132049 * (log 2 / log 10)
39751

39751桁の数字ですので, 桁数だけで326倍も違います... おそらくmodの計算とか色々と工夫してるのだろうなぁと思います. メルセンヌ素数を2進数で表すととても特殊なので, mod計算も高速に計算できるのかと...いや, 想像に過ぎません. 一千万桁の素数... 頭がクラクラしてきますよね... 巨大素数の世界には魅力がいっぱいです.

*1:A000225 - OEIS

*2:A000043 - OEIS, A000668 - OEIS

*3:Largest known prime number - Wikipedia, the free encyclopedia

*4:Lucas–Lehmer primality test - Wikipedia, the free encyclopedia

*5:A003010 - OEIS

*6:理解できなかったとも言えず... そのうち分かりたい

*7:http://en.wikipedia.org/wiki/%C3%89douard_Lucas

*8:これからはnを見つけるというよりも, 既存の結果を確かめるという方向にシフトしないと, 計算時間が.