メルセンヌ数
メルセンヌ数︵メルセンヌすう、英: Mersenne number︶とは、2の冪よりも 1小さい自然数、すなわち 2n− 1︵n は自然数︶の形の自然数のことである。これを Mnで表すことが多い。メルセンヌ数を小さい順に列挙すると
1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, ... (オンライン整数列大辞典の数列 A000225)
となる。メルセンヌ数は2進法表記で n桁の 11⋯11、すなわちレピュニットとなる。
Mn = 2n − 1 が素数ならば nもまた素数であるが、逆は成立しない (M11 = 2047 = 23 × 89)。素数であるメルセンヌ数をメルセンヌ素数︵メルセンヌそすう、英: Mersenne prime︶という。なお、﹁メルセンヌ数﹂という語で、n が素数であるもののみを指したり[1]、さらに狭義の意味でメルセンヌ素数を指す場合もある[注釈 1]。
基本的な性質[編集]
Mn が素数ならば nもまた素数であることは、次の式から分かる[2][3]‥ 2ab − 1 = (2a − 1)(1 + 2a + 22a + ⋯ + 2(b−1)a). 対偶命題﹁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 を素数とする。 ●Mp の素因数は 2pを法として 1と合同[6]、かつ 8を法として 1または −1 と合同である[7]。 ●p ≡ 3 (mod 4) のとき、Mp が 2p+ 1 で割れることと、2p + 1 が素数であることは同値である[7]。 ●ある計算可能な正定数 cが存在して、Mp の最大素因数を qについて、q ≥ cplog p[8]。メルセンヌ素数[編集]
メルセンヌ素数︵メルセンヌそすう、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]して以降、発見にはコンピュータが使用されており、コンピュータの進歩と共に新たなメルセンヌ素数が発見されつつある。
GIMPSによる発見[編集]
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 fornin 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 fornin 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番目までであり、 p = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161︵オンライン整数列大辞典の数列 A000043︶ における Mpがそうである。さらに49, 50, 51番目の候補として p= 74207281, 77232917, 82589933 が挙がっており、間に素数がないかどうか検証中である。 メルセンヌ素数は小さい順番から並べると 3, 7, 31, 127, 8191, 131071, 524287, 2147483647, ... (A000668) となる。# | 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] |
未解決問題[編集]
- メルセンヌ素数は無数に存在するか?
- 素数 p に対して Mp が合成数であるとき、これをメルセンヌ合成数と呼ぶことにして、それは無数に存在するか?
- 平方因子を持つメルセンヌ数 Mp(p は素数)が存在するか?
- n を奇数とするとき、次の3つの条件のうち2つが満たされれば、残りの1つも満足されると予想されており、n < 105 に対してこの予想は正しいと確認されている[34]。
- Mn が素数
- n = 2k ± 1 または 4k ± 3
- (2n + 1)/3 が素数
脚注[編集]
注釈[編集]
出典[編集]
(一)^ Weisstein, Eric W.. “Mersenne Number” (英語). mathworld.wolfram.com. 2022年2月18日閲覧。
(二)^ abcdef淡中 1982, pp. 65–67.
(三)^ 中村 2008, p. 81.
(四)^ ab和田 1981, pp. 59–61
(五)^ ユークリッド 1971, pp. 225–226, 第9巻、命題36.
(六)^ 和田 1981, p. 192.
(七)^ ab和田 1981, p. 193
(八)^ Theorem 1, Erdős & Shoray 1976
(九)^ ﹃原論﹄ 第9巻, 命題36. (pp. 225–226, ユークリッド 1971)
(十)^ abc“Mersenne Primes: History, Theorems and Lists” (英語). PrimePages. 2022年2月21日時点のオリジナルよりアーカイブ。2022年2月22日閲覧。
(11)^ Voight, John (1998年5月31日). “PERFECT NUMBERS: AN ELEMENTARY INTRODUCTION” (PDF) (英語). 2021年6月28日時点のオリジナルよりアーカイブ。2022年2月21日閲覧。
(12)^ Nicomachus of Gerasa (1926). Introduction to Arithmetic. Martin Luther D'Ooge (trans). The Macmillan Company. pp. 207–212
(13)^ abcdeO'Conner, John; Edmund F. Robertson. “Perfect numbers” (英語). MacTutor History of Mathematics. 2022年1月11日時点のオリジナルよりアーカイブ。2022年2月22日閲覧。
(14)^ Dickson, Leonard E. (1919) (英語). History of the Theory of Numbers. 1. Carnegie Institution of Washington. p. 6
(15)^ Anonymous (1456), Calendarium ecclesiasticum - BSB Clm 14908 (Anonymous Manuscript) 2022年2月21日閲覧。
(16)^ オンライン整数列大辞典の数列 A000043
(17)^ Mersenne, Marin (1644) (ラテン語). Cogitata Physico Mathematica. Paris: Antonii Bertier. doi:10.3931/e-rara-11036
(18)^ 和田 1981, p. 51.
(19)^ 中村 2008, pp. 83f.
(20)^ 中村 2008, p. 80.
(21)^ 中村 2008, p. 87.
(22)^ 中村 2008, pp. 82–84.
(23)^ Lucas 1878.
(24)^ Lucas 1969.
(25)^ 中村 2008, pp. 84f.
(26)^ 和田 1981, pp. 50–52, 194–199.
(27)^ 和田 1999, §5 リュカ・テスト.
(28)^ abcdefLandon Curt Noll, Mersenne Prime Digits and Names.
(29)^ The Prime Pages, M107: Fauquembergue or Powers?.
(30)^ The Prime Pages, The finding of the 32nd Mersenne.
(31)^ Chris Caldwell, The Largest Known Primes.
(32)^ The Prime Pages, A Prime of Record Size! 21257787 − 1.
(33)^ CASEY JOHNSTON (2013年2月7日). “﹁これまでで最大の素数﹂を発見”. WIRED (WIRED.jp) 2013年2月10日閲覧。
(34)^ P. T. Bateman, J. L. Selfridge, S. S. Wagstaff Jr., "The new Mersenne conjecture", American Mathematical Monthly, 96 (1989), 125–128.
GIMPS[編集]
(一)^ ab"GIMPS Discovers Largest Known Prime Number: 282,589,933-1" (Press release) (英語). GIMPS. 21 December 2018. 2022年2月19日閲覧。
(二)^ ab"GIMPS Discovers 35th Mersenne Prime, 21,398,269-1 is now the Largest Known Prime" (Press release) (英語). GIMPS. 23 November 1996.
(三)^ abc"GIMPS Discovers 45th and 46th Mersenne Primes, 243,112,609-1 is now the Largest Known Prime" (Press release) (英語). GIMPS. 15 September 2008. 2022年2月19日閲覧。
(四)^ "GIMPS Discovers 36th Mersenne Prime, 22,976,221-1 is now the Largest Known Prime" (Press release) (英語). GIMPS. 1 September 1997. 2022年2月19日閲覧。
(五)^ "GIMPS Discovers 37th Mersenne Prime, 23,021,377-1 is now the Largest Known Prime" (Press release) (英語). GIMPS. 2 February 1998.
(六)^ "GIMPS Discovers 38th Mersenne Prime 26,972,593-1 is now the Largest Known Prime. Stakes Claim to $50,000 EFF Award" (Press release) (英語). GIMPS. 30 June 1999. 2022年2月19日閲覧。
(七)^ "GIMPS Discovers 39th Mersenne Prime, 213,466,917-1 is now the Largest Known Prime. Researchers Discover Largest Multi-Million-Digit Prime Using Entropia Distributed Computing Grid" (Press release) (英語). GIMPS. 6 December 2001. 2022年2月19日閲覧。
(八)^ "GIMPS Discovers 40th Mersenne Prime, 220,996,011-1 is now the Largest Known Prime. Mersenne Project Discovers Largest Known Prime Number on World-Wide Volunteer Computer Grid" (Press release) (英語). GIMPS. 2 December 2003. 2022年2月19日閲覧。
(九)^ "GIMPS Discovers 41st Mersenne Prime, 224,036,583-1 is now the Largest Known Prime. Project Leaders Believe $100,000 Award Within Reach" (Press release) (英語). GIMPS. 28 May 2004. 2022年2月19日閲覧。
(十)^ "GIMPS Discovers 42nd Mersenne Prime, 225,964,951-1 is now the Largest Known Prime" (Press release) (英語). GIMPS. 27 February 2005. 2022年2月19日閲覧。
(11)^ "GIMPS Discovers 43rd Mersenne Prime, 230,402,457-1 is now the Largest Known Prime" (Press release) (英語). GIMPS. 24 December 2005. 2022年2月19日閲覧。
(12)^ "GIMPS Discovers 44th Mersenne Prime, 232,582,657-1 is now the Largest Known Prime" (Press release) (英語). GIMPS. 11 September 2006. 2022年2月19日閲覧。
(13)^ "GIMPS Discovers 48th Mersenne Prime, 257,885,161-1 is now the Largest Known Prime" (Press release) (英語). GIMPS. 5 February 2013. 2022年2月19日閲覧。
(14)^ "GIMPS Project Discovers Largest Known Prime Number: 274,207,281-1" (Press release) (英語). GIMPS. 19 January 2016. 2022年3月30日閲覧。
(15)^ "GIMPS Project Discovers Largest Known Prime Number: 277,232,917-1" (Press release) (英語). GIMPS. 3 January 2018. 2022年2月19日閲覧。