メルセンヌ数

出典: フリー百科事典『ウィキペディア(Wikipedia)』

メルセンヌ数(メルセンヌすう、: Mersenne number)とは、2の冪よりも 1 小さい自然数、すなわち 2n − 1n は自然数)の形の自然数のことである。これを 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) のとき、Mp2p + 1 で割れることと、2p + 1 が素数であることは同値である[7]
  • ある計算可能な正定数 c が存在して、Mp の最大素因数を q について、qcp log 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]

メルセンヌの予想[編集]

メルセンヌの予想の表: p ≦ 263
〇: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年マラン・メルセンヌは「素数 p2p − 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 = 611883年)、p = 891911年)、p = 1071914年))。メルセンヌが予想した最後の数 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} を定義すると、

  • ならば、Mp は合成数である
  • ならば、Mp は素数である[22][23][24]
アルゴリズム[編集]

アルゴリズムは以下の擬似コードで表される。

入力: 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} を定義すると、

  • ならば、Mp は合成数である
  • ならば、Mp は素数である[25][26][27]

リュカ–レーマー・テストは二進計算機用のアルゴリズムに向いており、コンピュータによるメルセンヌ素数の発見には、この判定法が用いられてきた。例えば、2p ≡ 1 (mod Mp) より、A·2p + BA + 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番目までであり、

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]
  1. ^ a b c 49番目以降はメルセンヌ素数としての順番が確定していない。

未解決問題[編集]

  • メルセンヌ素数は無数に存在するか?
  • 素数 p に対して Mp が合成数であるとき、これをメルセンヌ合成数と呼ぶことにして、それは無数に存在するか?
  • 平方因子を持つメルセンヌ数 Mpp は素数)が存在するか?
  • n を奇数とするとき、次の3つの条件のうち2つが満たされれば、残りの1つも満足されると予想されており、n < 105 に対してこの予想は正しいと確認されている[34]
  1. Mn が素数
  2. n = 2k ± 1 または 4k ± 3
  3. (2n + 1)/3 が素数

脚注[編集]

注釈[編集]

  1. ^ 岩波数学辞典』第3版 180E ではそのようになっている。一松 (2007, p. 73) によれば、これは日本のごく一部での用法であるらしい。『岩波数学辞典』第4版 194D では、メルセンヌ数とメルセンヌ素数を使い分けている。
  2. ^ 2n − 1 (2n− 1) は偶数であるため、この式は奇数の完全数について何も言及しない。また、偶数の完全数がこの形に限られることは18世紀にレオンハルト・オイラーが証明するまで未解決であった。

出典[編集]

  1. ^ Weisstein, Eric W.. “Mersenne Number” (英語). mathworld.wolfram.com. 2022年2月18日閲覧。
  2. ^ a b c d e f 淡中 1982, pp. 65–67.
  3. ^ 中村 2008, p. 81.
  4. ^ a b 和田 1981, pp. 59–61
  5. ^ ユークリッド 1971, pp. 225–226, 第9巻、命題36.
  6. ^ 和田 1981, p. 192.
  7. ^ a b 和田 1981, p. 193
  8. ^ Theorem 1, Erdős & Shoray 1976
  9. ^ 『原論』 第9巻, 命題36. (pp. 225–226, ユークリッド 1971)
  10. ^ a b c 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. https://archive.org/details/NicomachusIntroToArithmetic 
  13. ^ a b c d e O'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. https://archive.org/details/historyoftheoryo01dick/page/n5/mode/2up 
  15. ^ Anonymous (1456), Calendarium ecclesiasticum - BSB Clm 14908 (Anonymous Manuscript), https://iiif.biblissima.fr/collections/manifest/4dca8a1c8b0be3df1ce6954d8d1ba60590cd04cc 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. ^ a b c d e f Landon 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). http://wired.jp/2013/02/07/volunteer-discovers-a-new-17-million-digit-prime-number/ 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[編集]

  1. ^ a b "GIMPS Discovers Largest Known Prime Number: 282,589,933-1" (Press release) (英語). GIMPS. 21 December 2018. 2022年2月19日閲覧
  2. ^ a b "GIMPS Discovers 35th Mersenne Prime, 21,398,269-1 is now the Largest Known Prime" (Press release) (英語). GIMPS. 23 November 1996.
  3. ^ a b c "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日閲覧
  4. ^ "GIMPS Discovers 36th Mersenne Prime, 22,976,221-1 is now the Largest Known Prime" (Press release) (英語). GIMPS. 1 September 1997. 2022年2月19日閲覧
  5. ^ "GIMPS Discovers 37th Mersenne Prime, 23,021,377-1 is now the Largest Known Prime" (Press release) (英語). GIMPS. 2 February 1998.
  6. ^ "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日閲覧
  7. ^ "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日閲覧
  8. ^ "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日閲覧
  9. ^ "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日閲覧
  10. ^ "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日閲覧

参考文献[編集]

関連項目[編集]

外部リンク[編集]