Loading AI tools
nが0以外の自然数であるとき、Mn = 2n − 1になる自然数 ウィキペディアから
メルセンヌ数(メルセンヌすう、英: Mersenne number)とは、2の冪よりも 1 小さい自然数、すなわち 2n − 1(n は自然数)の形の自然数のことである。これを Mn で表すことが多い。メルセンヌ数を小さい順に列挙すると
となる。メルセンヌ数は2進法表記で n 桁の 11⋯11、すなわちレピュニットとなる。
Mn = 2n − 1 が素数ならば n もまた素数であるが、逆は成立しない (M11 = 2047 = 23 × 89)。素数であるメルセンヌ数をメルセンヌ素数(メルセンヌそすう、英: Mersenne prime)という。なお、「メルセンヌ数」という語で、n が素数であるもののみを指したり[1]、さらに狭義の意味でメルセンヌ素数を指す場合もある[注釈 1]。
Mn が素数ならば n もまた素数であることは、次の式から分かる[2][3]:
対偶命題「n が合成数ならば Mn は合成数である」が示される。また、この等式より、m | n のとき Mm | Mn である。一方、 p が素数でも Mp が素数とは限らない。最小の反例は p = 11 の場合であり、M11 = 2047 = 23 × 89 が成り立つ。
(奇)素数 p に対して Mp が素数であるかどうかは、リュカ-レーマー・テストによって判定できる (#素数判定法節を参照)。
Mp = 2p − 1 が素数ならば、2p−1(2p − 1) は完全数である[2][4]。この定理はすでに紀元前3世紀頃のユークリッド原論で証明されていた[5]。したがって、完全数の探索はメルセンヌ素数の探索に終始された。
2p−1(2p − 1) は明らかに偶数であるが、偶数の完全数でこの生成式から得られるもの以外はないのか2000年間にわたって未解決であったが、18世紀にオイラーによりこの形に限ることが証明された[4]。
p を素数とする。
メルセンヌ素数(メルセンヌそすう、Mersenne prime)とは、素数であるメルセンヌ数のことである。
2022年2月現在知られている最大のメルセンヌ素数は、2018年12月に発見された、それまでに分かっている中で51番目のメルセンヌ素数 282589933 − 1 であり、十進法で表記したときの桁数は2486万2048桁に及ぶ[GIMPS 1]。
メルセンヌ素数の探求は紀元前3世紀ごろに端を発する。古代エジプトの数学者エウクレイデスは『原論』の中で、「2n − 1 が素数ならば、2n − 1(2n − 1) は完全数である」ことを証明した[9]。ここから、メルセンヌ素数の探索は完全数の探索にも繋がることとなる[10][注釈 2]。
小さいメルセンヌ素数がいつから知られているかは定かではないが、少なくとも最初の4つの完全数はゲラサのニコマコスの『算術入門』ですでに言及されている[11][12]。5番目から7番目の完全数は、13世紀イスラムの数学者イブン・ファッルース (fr:Ibn Fallus) が論文に記している[13]。ヨーロッパでは、5番目の完全数が1456年と1461年の日付が付された古い写本に記されて[14][15]おり、6番目と7番目のメルセンヌ素数および完全数も1603年にピエトロ・カタルディ(英: Pietro Cataldi)によって発見されている[13]。
〇:Mpが素数の場合/×:Mpが合成数の場合 水色が正解、ピンク色が間違いを示す[16]。 | ||||||||
p | 2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 |
Mp | 〇 | 〇 | 〇 | 〇 | × | 〇 | 〇 | 〇 |
p | 23 | 29 | 31 | 37 | 41 | 43 | 47 | 53 |
Mp | × | × | 〇 | × | × | × | × | × |
p | 59 | 61 | 67 | 71 | 73 | 79 | 83 | 89 |
Mp | × | 〇 | × | × | × | × | × | 〇 |
p | 97 | 101 | 103 | 107 | 109 | 113 | 127 | 131 |
Mp | × | × | × | 〇 | × | × | 〇 | × |
p | 137 | 139 | 149 | 151 | 157 | 163 | 167 | 173 |
Mp | × | × | × | × | × | × | × | × |
p | 179 | 181 | 191 | 193 | 197 | 199 | 211 | 223 |
Mp | × | × | × | × | × | × | × | × |
p | 227 | 229 | 233 | 239 | 241 | 251 | 257 | 263 |
Mp | × | × | × | × | × | × | × | × |
1644年、マラン・メルセンヌは「素数 p で 2p − 1 が素数になるのは、p ≦ 257 では p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 の11個の場合だけである」という予想を公表した[13][17]。しかしメルセンヌ自身はその予想を証明することができず、しかもその予想の一部は誤っていた。
成果を見るのはメルセンヌが予想を公表してから128年後、1772年、オイラー(p = 31 では素数)[2][18]。その次の成果はさらに104年後、1876年、リュカ(効率的な素数判定法リュカ・テストを考案、p = 67 では素数でない、p = 127 では素数[2][19])であった。その後リュカ・テストは改良が加えられ、メルセンヌが予想した範囲にない3個が付け加えられた(p = 61(1883年)、p = 89(1911年)、p = 107(1914年))。メルセンヌが予想した最後の数 p = 257 について決着がついたのは1922年のことであり、 p = 257 も合成数だった[2][20]。
結局メルセンヌの11個の予想のうち2つは外れた。なおかつ、間に予想できなかった3つが含まれていたことを考えれば予想は正しかったとはいえないが、その後の歴史を見ても大きな原動力となり先駆的であったことに敬意を表し、素数であるメルセンヌ数をメルセンヌ素数という[要出典]。
1903年10月、アメリカの数学者フランク・ネルソン・コールは実際の素因数分解を探し求め、ニューヨークで開かれたアメリカ数学会の会議で 193707721 × 761838257287 を黒板に計算し、M67 と一致することを証明した。この間一言もしゃべらず、席に戻った後、少し間を置いて拍手が沸き起こったと伝えられている[21]。
1952年、ラファエル・M・ロビンソンが SWAC を利用して M521 から M2281 まで、5つのメルセンヌ素数を発見[2]して以降、発見にはコンピュータが使用されており、コンピュータの進歩と共に新たなメルセンヌ素数が発見されつつある。
1996年、メルセンヌ素数を発見することを目的として作られた分散コンピューティングによるプロジェクト GIMPS が発足し、35番目のメルセンヌ素数 M1,398,269(1996年11月13日、Joel Armengaud[GIMPS 2])以来、GIMPSによるメルセンヌ素数の発見が続いている。
2008年8月23日、GIMPS は46番目の素数候補が、カリフォルニア大学ロサンゼルス校の数学部のコンピュータによって発見されたと報じた[要出典]。この素数は電子フロンティア財団が賞金を懸けた1000万桁以上の最初の素数となるため、GIMPS によって同校数学部に50,000ドル、慈善事業に25,000ドル、残りを前の6つのメルセンヌ素数の発見者へ分配することになった[GIMPS 3]。
2008年9月6日、GIMPS は45番目の素数候補が、ドイツで発見されたと報じた[要出典]。これは、GIMPS によって発見された中では、発見順序と桁数が逆転した初めてのケースである。
知られている素数の中で最大のものが1876年以降ほぼ一貫してメルセンヌ素数である理由は、この判定法にある[要出典]。
p が (4j + 3) 型の素数のとき、S0 = 3, Sn = Sn−12 − 2 (n ≥ 1) で {Sn} を定義すると、
アルゴリズムは以下の擬似コードで表される。
入力: p: (4j + 3) 型の素数であるテスト対象の整数 出力: PRIME:素数の場合, COMPOSIT:合成数の場合 Lucas_Test(p): var s = 3 var MP = (1 << p) − 1 for n in range(2, p): s = (s2 − 2) % MP if s == 0 then: return PRIME else: return COMPOSIT
p が奇素数のとき、S0 = 4, Sn = Sn−12 − 2 (n ≥ 1) で{Sn} を定義すると、
リュカ–レーマー・テストは二進計算機用のアルゴリズムに向いており、コンピュータによるメルセンヌ素数の発見には、この判定法が用いられてきた。例えば、2p ≡ 1 (mod Mp) より、A·2p + B ≡ A + B (mod Mp) が成り立つので、Mp で割る割り算の代わりに、二進法で p 桁のシフト演算と足し算だけで計算できる。
アルゴリズムは以下の擬似コードで表される。
入力: p:奇素数であるテスト対象の整数 出力: PRIME:素数の場合, COMPOSIT:合成数の場合 Lucas_Lehmer_Test(p): var s = 4 var MP = (1 << p) − 1 for n in range(2, p): s = (s2 − 2) % MP if s == 0 then: return PRIME else: return COMPOSIT
入力: p:奇素数であるテスト対象の整数 出力: PRIME:素数の場合, COMPOSIT:合成数の場合 Lucas_Lehmer_Test_FAST(p): var s = 4 var m = 2p − 1 for n in range(2, p): var s2 = s × s s = (s2 & m) + (s2 >> p) if s >= m then s = s − m s = s − 2 if s == 0 then return PRIME else return COMPOSIT
2021年10月現在、メルセンヌ素数は51個まで知られている。ただし、メルセンヌ素数としての番号が確定しているものは48番目までであり、
における Mp がそうである。さらに49, 50, 51番目の候補として p = 74207281, 77232917, 82589933 が挙がっており、間に素数がないかどうか検証中である。
メルセンヌ素数は小さい順番から並べると
となる。
# | p | Mp の 桁数 |
発見日 | 発見者 |
---|---|---|---|---|
1 | 2 | 1 | 紀元前500年?[28] | |
2 | 3 | 1 | 紀元前500年?[28] | |
3 | 5 | 2 | 紀元前275年?[28] | |
4 | 7 | 3 | 紀元前275年?[28] | |
5 | 13 | 4 | 1456年[10] | 不明[10] |
6 | 17 | 6 | 1603年[13] | ピエトロ・カタルディ |
7 | 19 | 6 | 1603年[13] | ピエトロ・カタルディ |
8 | 31 | 10 | 1772年 | レオンハルト・オイラー |
9 | 61 | 19 | 1883年 | イヴァン・パヴシン |
10 | 89 | 27 | 1911年 | R・E・パワーズ |
11 | 107 | 33 | 1914年 | R・E・パワーズ[29] |
12 | 127 | 39 | 1876年 | エドゥアール・リュカ |
13 | 521 | 157 | 1952年1月30日 | ラファエル・M・ロビンソン, 使用:SWAC |
14 | 607 | 183 | 1952年1月30日 | ラファエル・M・ロビンソン |
15 | 1,279 | 386 | 1952年6月25日 | ラファエル・M・ロビンソン |
16 | 2,203 | 664 | 1952年10月7日 | ラファエル・M・ロビンソン |
17 | 2,281 | 687 | 1952年10月9日 | ラファエル・M・ロビンソン |
18 | 3,217 | 969 | 1957年9月8日 | ハンス・リーゼル, 使用:BESK |
19 | 4,253 | 1,281 | 1961年11月3日 | アレクサンダー・フルウィッツ, 使用:IBM 7090 |
20 | 4,423 | 1,332 | 1961年11月3日 | アレクサンダー・フルウィッツ |
21 | 9,689 | 2,917 | 1963年5月11日 | ドナルド・ギリース, 使用:ILLIAC II |
22 | 9,941 | 2,993 | 1963年5月16日 | ドナルド・ギリース |
23 | 11,213 | 3,376 | 1963年6月2日 | ドナルド・ギリース |
24 | 19,937 | 6,002 | 1971年3月4日 | ブライアント・タッカーマン, 使用:IBM 360/91 |
25 | 21,701 | 6,533 | 1978年10月30日 | ランドン・カート・ノル & ローラ・ニッケル, 使用:CDC Cyber 174 |
26 | 23,209 | 6,987 | 1979年2月9日 | ランドン・カート・ノル |
27 | 44,497 | 13,395 | 1979年4月8日 | ハリー・ネルソン & デイヴィッド・スローウィンスキー |
28 | 86,243 | 25,962 | 1982年9月25日 | デイヴィッド・スローウィンスキー |
29 | 110,503 | 33,265 | 1988年1月28日 | ウォルター・コルキット & ルーク・ウェルシュ |
30 | 132,049 | 39,751 | 1983年9月19日[28] | デイヴィッド・スローウィンスキー |
31 | 216,091 | 65,050 | 1985年9月1日[28] | デイヴィッド・スローウィンスキー |
32 | 756,839 | 227,832 | 1992年2月19日 | デイヴィッド・スローウィンスキー & ポール・ゲイジ 使用:Harwell Lab Cray-2[30] |
33 | 859,433 | 258,716 | 1994年1月4日[31] | デイヴィッド・スローウィンスキー & ポール・ゲイジ |
34 | 1,257,787 | 378,632 | 1996年9月3日 | デイヴィッド・スローウィンスキー & ポール・ゲイジ[32] |
35 | 1,398,269 | 420,921 | 1996年11月13日 | GIMPS / Joel Armengaud[GIMPS 2] |
36 | 2,976,221 | 895,932 | 1997年8月24日 | GIMPS / Gordon Spence[GIMPS 4] |
37 | 3,021,377 | 909,526 | 1998年1月27日 | GIMPS / Roland Clarkson[GIMPS 5] |
38 | 6,972,593 | 2,098,960 | 1999年6月1日 | GIMPS / Nayan Hajratwala[GIMPS 6] |
39 | 13,466,917 | 4,053,946 | 2001年11月14日 | GIMPS / Michael Cameron[GIMPS 7] |
40 | 20,996,011 | 6,320,430 | 2003年11月17日 | GIMPS / Michael Shafer[GIMPS 8] |
41 | 24,036,583 | 7,235,733 | 2004年5月15日 | GIMPS / Josh Findley[GIMPS 9] |
42 | 25,964,951 | 7,816,230 | 2005年2月18日 | GIMPS / Martin Nowak et al.[GIMPS 10] |
43 | 30,402,457 | 9,152,052 | 2005年12月15日 | GIMPS / カーティス・クーパー, Steven Boone[GIMPS 11] |
44 | 32,582,657 | 9,808,358 | 2006年9月4日 | GIMPS / カーティス・クーパー, Steven Boone[GIMPS 12] |
45 | 37,156,667 | 11,185,272 | 2008年9月6日 | GIMPS / Hans-Michael Elvenich[GIMPS 3] |
46 | 42,643,801 | 12,837,064 | 2009年4月12日 | GIMPS / Odd Magnar Strindmo |
47 | 43,112,609 | 12,978,189 | 2008年8月23日 | GIMPS / エドソン・スミス[GIMPS 3] |
48 | 57,885,161 | 17,425,170 | 2013年1月25日 | GIMPS / カーティス・クーパー[33][GIMPS 13] |
[* 1] | 74,207,281 | 22,338,618 | 2016年1月7日 | GIMPS / カーティス・クーパー[GIMPS 14] |
[* 1] | 77,232,917 | 23,249,425 | 2017年12月26日 | GIMPS / Jonathan Pace[GIMPS 15] |
[* 1] | 82,589,933 | 24,862,048 | 2018年12月7日 | GIMPS / Patrick Laroche[GIMPS 1] |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.