メルセンヌ数

出典: フリー百科事典『ウィキペディア(Wikipedia)』
メルセンヌ素数から転送)
移動先: 案内検索

メルセンヌ数(メルセンヌすう、: Mersenne number)とは、2の冪よりも 1 小さい自然数、すなわち 2n − 1n は自然数)の形の自然数のことである。これを Mn で表すことが多い。2進数表記では、n 桁の 11⋯11 となる。

1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, …オンライン整数列大辞典の数列 A000225から初項 0 を除いたもの。太字素数、素数を除いたメルセンヌ数はオンライン整数列大辞典の数列 A135972を参照)

歴史的には紀元前3世紀頃のユークリッド原論において知られる完全数の生成式で見出されている[1]。そこから素数であるメルセンヌ数を見つけることこそが完全数を見つけることとなった。

Mn = 2n − 1 が素数ならば n は素数である。古代ギリシア数学者は p = 57 のとき Mp が素数であることを見つけた。しかし p が素数であっても Mp は素数とは限らない(M11 = 2047 = 23 × 89)。そのため完全数の探索は困難をきわめた。

その後17世紀までに p = 13, 17, 19 のとき Mp が素数であることが分かるが、1644年マラン・メルセンヌは「素数 p2p − 1 が素数になるのは、19 < p ≤ 257 では p = 31, 67, 127, 257 の4つの場合だけである」という大胆不敵な予想を公表した。しかしメルセンヌ自身はその予想を証明することができず、しかもその予想の一部は誤っていた。成果を見るのはメルセンヌが予想を公表してから128年後のオイラーp = 31 では素数、1772年[2][3]、その次の成果はさらに104年後のリュカ(効率的な素数判定法リュカ・テスト (Lucas test) を考案、p = 67 では素数でない、p = 127 では素数、1876年[2][4])であった。1903年10月、アメリカの数学者コールp = 67 のときの素因数分解を直接示し驚愕と喝采を浴びたという逸話も残されている(詳細は下記を参照)。

リュカ・テストはその後改良が加えられ、メルセンヌが予想した範囲にない3個が付け加えられた(p = 611883年)、p = 891911年)、p = 1071914年))。メルセンヌが予想した最後の数 p = 257 について決着がついたのは1922年のことであった。残念ながらこれも合成数だった[2][5]

結局メルセンヌの4つの予想のうち2つが当たり、2つははずれ。なおかつ、間に予想できなかった3つが含まれていたことを考えれば予想は五分以上の確率とはいえないが、その後の歴史を見ても大きな原動力となり先駆的であったことに敬意を表し、素数であるメルセンヌ数をメルセンヌ素数(メルセンヌそすう、: Mersenne prime)という。

p = 127 の次の13番目に来るメルセンヌ素数は多くの数学者の予想を超え p = 521ラファエル・M・ロビンソン英語版1952年。コンピュータシステムSWACを使用)だった。桁数にすると 157 であり(M127 は 39)、人の手に負える大きさではなかった。ここから計算機を駆使し、コンピュータの発達とともに巨大なメルセンヌ素数ひいては素数の探索の時代を迎えることとなる。メルセンヌ素数列の最初の方は以下の通りである。

3, 7, 31, 127, 8191, 131071, 524287, 2147483647, …オンライン整数列大辞典の数列 A000668、詳細は#発見されているメルセンヌ素数の表を参照)

近年では、分散コンピューティングによるプロジェクト GIMPS (Great Internet Mersenne Prime Search) によるメルセンヌ素数の発見が進められている。2017年9月現在[いつ?]知られている最大のメルセンヌ素数は、2016年1月に発見された、それまでに分かっている中で49番目のメルセンヌ素数 274207281 − 1 であり、十進法で表記したときの桁数は2233万8618桁[6](新聞紙に印刷するとほぼ691ページ)に及ぶ。

なお、「メルセンヌ数」という語で、n が素数であるもののみを指したり[7]、さらに狭くメルセンヌ素数を指す場合もある[注釈 1]

又、素数問題とは無関係に、ハノイの塔の必要最小限手数の計算式もこの数の定義式[注釈 2]となっている(後述)。

基本的な性質[編集]

Mn が素数ならば n は素数であることは、次の式から分かる[2][8]

2ab − 1 = (2a − 1)(1 + 2a + 22a + ⋯ + 2(b−1)a).

対偶命題n が合成数ならば Mn は合成数である」が示される。また、この等式より、mn のとき MmMn である。

しかし、逆に p が素数でも Mp が素数とは限らない(最小の反例:M11 = 2047 = 23 × 89)。そのため、数が大きくなるにつれ直接素因数分解を試みるのでなく、間接的に素数であるかないかを判定する素数判定法が考案された。これが後述するエドゥアール・リュカによる判定法(リュカ・テスト (Lucas test))と、それを改良し今日使われているデリック・ヘンリー・レーマー英語版による判定法(リュカ–レーマー・テスト (Lucas–Lehmer primality test))である。

完全数[編集]

Mp = 2p − 1 が素数ならば、2p−1(2p − 1)完全数である[2][9]。この定理はすでに紀元前3世紀頃のユークリッド原論で証明されていた[1]。したがって、完全数の探索はメルセンヌ素数の探索に終始された。

2p−1(2p − 1) は明らかに偶数であるが、偶数の完全数でこの生成式から得られるもの以外はないのか2000年間にわたって未解決であったが、18世紀オイラーによりこの形に限ることが証明された[9]

メルセンヌ数の素因数[編集]

p を素数とする。

  • Mp の素因数は 2p を法として 1 と合同[10]、かつ 8 を法として 1 または −1 と合同である[11]
  • p ≡ 3 (mod 4) のとき、Mp2p + 1 で割れることと、2p + 1 が素数であることは同値である[11]
  • Mp の最大素因数を q とすると、qc5 p log pc5 は計算可能な定数)(Erdős–Shoreyの定理1)[12]

メルセンヌ素数の発見の歴史[編集]

1876年エドゥアール・リュカは効率的な素数判定法を考案し(リュカ・テスト (Lucas test))、M67 が素数でないことを間接的に証明した[2][4]。アメリカの数学者フランク・ネルソン・コールは実際の素因数分解を探し求め、彼は1903年10月、ニューヨークで開かれたアメリカ数学会の会議で 193707721 × 761838257287 を黒板に計算し、M67 と一致することを証明した。この間一言もしゃべらず、席に戻った後、少し間を置いて拍手が沸き起こったと伝えられている[13]

デリック・ヘンリー・レーマー英語版は、リュカの判定法を改良し、今日ではリュカ–レーマー・テスト (Lucas–Lehmer primality test) と呼ばれる、メルセンヌ数に対する素数判定法を確立した。

現在[いつ?]「最大の」素数がメルセンヌ素数である理由はこの判定法にあると言える。1952年ラファエル・M・ロビンソンSWAC を利用して M521 から M2281 まで、5つのメルセンヌ素数を発見[2]して以降、発見にはコンピュータが使用されており、コンピュータの進歩と共に新たなメルセンヌ素数が発見されつつある。

1996年、メルセンヌ素数を発見することを目的として作られた分散コンピューティングによるプロジェクト GIMPS が発足し、35番目のメルセンヌ素数 M1,398,269(1996年11月13日、Joel Armengaud[14])以来、GIMPSによるメルセンヌ素数の発見が相次いでいる。

素数判定法[編集]

リュカ・テスト[編集]

p(4j + 3) 型の素数のとき、S0 = 3, Sn = Sn−12 − 2 (n ≥ 1){Sn} を定義すると、

ならば、Mp は合成数である。
ならば、Mp は素数である[15][16][17]

リュカ–レーマー・テスト[編集]

p が奇素数のとき、Mp が素数となるための必要十分条件は、S0 = 4, Sn = Sn−12 − 2 (n ≥ 1){Sn} を定義したとき Sp−2Mp で割り切れることである[18][19][20]

リュカ–レーマー・テストは二進計算機用のアルゴリズムに向いており、コンピュータによるメルセンヌ素数の発見には、この判定法が用いられてきた。例えば、2p ≡ 1 (mod Mp) より、A·2p + BA + B (mod Mp) が成り立つので、Mp で割る割り算の代わりに、二進法で p 桁のシフト演算と足し算だけで計算できる。

メルセンヌ素数の一覧[編集]

2017年9月現在[いつ?]、メルセンヌ素数は49個まで知られている。ただし、メルセンヌ素数としての番号が確定しているものは、45番目までであり、

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オンライン整数列大辞典の数列 A000043, オンライン整数列大辞典の数列 A000668

における Mp がそうである。さらに46, 47, 48, 49番目の候補として p = 42643801, 43112609, 57885161, 74207281 が挙がっており、現在[いつ?]、間に素数がないかどうか検証中である。

  • 2005年2月27日、GIMPS は42番目の素数候補がドイツの眼科医によって発見されたことを報告した。781万6230桁の数、225964951 − 1 であり、[1]に掲載されている。
  • 2005年12月15日、GIMPS は43番目の素数候補が米国のセントラル・ミズーリ州立大学(現セントラル・ミズーリ大学英語版)の教授2名によって発見されたと報じた。230402457 − 1、915万2052桁 [2]
  • 2006年9月4日、GIMPS は44番目の素数候補が、43番目の素数候補を発見したのと同じ教授2名によって発見されたと報じた。232582657 − 1、980万8358 桁[3]
  • 2008年8月23日、GIMPS は46番目の素数候補が、カリフォルニア大学ロサンゼルス校の数学部のコンピュータによって発見されたと報じた。243112609 − 1、1297万8189 桁(十進法で表記すると 243112609 − 1 ≒ 3.1647 × 1012978188[4]。発見順では45番目だが、次に発見されたメルセンヌ素数と発見時期が近かったため、46番目の候補として45番目の候補と同時に発表された。この素数は電子フロンティア財団が賞金を懸けた1000万桁以上の最初の素数となるため、GIMPS によって同校数学部に50,000ドル、慈善事業に25,000ドル、残りを前の6つのメルセンヌ素数の発見者へ分配することになった。
  • 2008年9月6日、GIMPS は45番目の素数候補が、ドイツで発見されたと報じた。237156667 − 1、1118万5272 桁[5]。これは、GIMPS によって発見された中では、発見順序と桁数が逆転した初めてのケースである。
  • 2014年11月8日232582657 − 1 が公式に44番目のメルセンヌ素数であると報じた[6]

オンライン整数列大辞典の数列 A000668

# p Mp Mp
桁数
発見日 発見者
1 2 3 1 紀元前5世紀[21] 古代ギリシアの数学者
2 3 7 1 紀元前5世紀[21] 古代ギリシアの数学者
3 5 31 2 紀元前3世紀[21] 古代ギリシアの数学者
4 7 127 3 紀元前3世紀[21] 古代ギリシアの数学者
5 13 8191 4 1456年 不明[22]
6 17 131071 6 1588年 ピエトロ・カタルディ英語版
7 19 524287 6 1588年 ピエトロ・カタルディ
8 31 2147483647 10 1772年 レオンハルト・オイラー
9 61 2305843009213693951 19 1883年 イヴァン・パヴシン英語版
10 89 618970019642690137449562111 27 1911年 R・E・パワーズ英語版
11 107 162259276829213363391578010288127 33 1914年 R・E・パワーズ[23]
12 127 170141183460469231731687303715884105727 39 1876年 エドゥアール・リュカ
13 521 68647976601306097149819007…115057151 157 1952年1月30日 ラファエル・M・ロビンソン英語版, 使用:SWAC
14 607 531137992…031728127 183 1952年1月30日 ラファエル・M・ロビンソン
15 1,279 104079321…168729087 386 1952年6月25日 ラファエル・M・ロビンソン
16 2,203 147597991…697771007 664 1952年10月7日 ラファエル・M・ロビンソン
17 2,281 446087557…132836351 687 1952年10月9日 ラファエル・M・ロビンソン
18 3,217 259117086…909315071 969 1957年9月8日 ハンス・リーゼル, 使用:BESK
19 4,253 190797007…350484991 1,281 1961年11月3日 アレクサンダー・フルウィッツ, 使用:IBM 7090
20 4,423 285542542…608580607 1,332 1961年11月3日 アレクサンダー・フルウィッツ
21 9,689 478220278…225754111 2,917 1963年5月11日 ドナルド・ギリース, 使用:ILLIAC II
22 9,941 346088282…789463551 2,993 1963年5月16日 ドナルド・ギリース
23 11,213 281411201…696392191 3,376 1963年6月2日 ドナルド・ギリース
24 19,937 431542479…968041471 6,002 1971年3月4日 ブライアント・タッカーマン英語版, 使用:IBM 360/91
25 21,701 448679166…511882751 6,533 1978年10月30日 ランドン・カート・ノル英語版 & ローラ・ニッケル, 使用:CDC Cyber 174
26 23,209 402874115…779264511 6,987 1979年2月9日 ランドン・カート・ノル
27 44,497 854509824…011228671 13,395 1979年4月8日 ハリー・ネルソン & デイヴィッド・スローウィンスキー英語版
28 86,243 536927995…433438207 25,962 1982年9月25日 デイヴィッド・スローウィンスキー
29 110,503 521928313…465515007 33,265 1988年1月28日 ウォルター・コルキット & ルーク・ウェルシュ
30 132,049 512740276…730061311 39,751 1983年9月19日[21] デイヴィッド・スローウィンスキー
31 216,091 746093103…815528447 65,050 1985年9月1日[21] デイヴィッド・スローウィンスキー
32 756,839 174135906…544677887 227,832 1992年2月19日 デイヴィッド・スローウィンスキー & ポール・ゲイジ英語版 使用:Harwell Lab Cray-2[24]
33 859,433 129498125…500142591 258,716 1994年1月4日[25] デイヴィッド・スローウィンスキー & ポール・ゲイジ
34 1,257,787 412245773…089366527 378,632 1996年9月3日 デイヴィッド・スローウィンスキー & ポール・ゲイジ[26]
35 1,398,269 814717564…451315711 420,921 1996年11月13日 GIMPS / Joel Armengaud[14]
36 2,976,221 623340076…729201151 895,932 1997年8月24日 GIMPS / Gordon Spence[27]
37 3,021,377 127411683…024694271 909,526 1998年1月27日 GIMPS / Roland Clarkson[28]
38 6,972,593 437075744…924193791 2,098,960 1999年6月1日 GIMPS / Nayan Hajratwala[29]
39 13,466,917 924947738…256259071 4,053,946 2001年11月14日 GIMPS / Michael Cameron[30]
40 20,996,011 125976895…855682047 6,320,430 2003年11月17日 GIMPS / Michael Shafer[31]
41 24,036,583 299410429…733969407 7,235,733 2004年5月15日 GIMPS / Josh Findley[32]
42 25,964,951 122164630…577077247 7,816,230 2005年2月18日 GIMPS / Martin Nowak[33]
43 30,402,457 315416475…652943871 9,152,052 2005年12月15日 GIMPS / カーティス・クーパー英語版 & Steven Boone[34]
44 32,582,657 124575026…053967871 9,808,358 2006年9月4日 GIMPS / カーティス・クーパー & Steven Boone[35]
45 37,156,667 202254406…308220927 11,185,272 2008年9月6日 GIMPS / Hans-Michael Elvenich[36]
46[*] 42,643,801 169873516…562314751 12,837,064 2009年4月12日 GIMPS / Odd Magnar Strindmo
47[*] 43,112,609 316470269…697152511 12,978,189 2008年8月23日 GIMPS / エドソン・スミス[36]
48[*] 57,885,161 581887266…724285951 17,425,170 2013年1月25日 GIMPS / カーティス・クーパー[37][38]
49[*] 74,207,281 300376418084…391086436351 22,338,618 2015年9月17日 GIMPS / カーティス・クーパー[39]

  •  46から49番目は、2016年1月時点でより小さなメルセンヌ素数の個数を検証できていないことによる暫定的な順位である。過去には29番目のメルセンヌ素数は30, 31番目が発見された後に発見されている。また47番目の後に45, 46番目が発見されている。

未解決問題[編集]

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

脚注[編集]

[ヘルプ]

注釈[編集]

  1. ^ 岩波数学辞典』第3版 180E ではそのようになっている。一松 (2007, p. 73) によれば、これは日本のごく一部での用法であるらしい。『岩波数学辞典』第4版 194D では、メルセンヌ数とメルセンヌ素数を使い分けている。
  2. ^ 尚考案者のエドゥアール・リュカは本数の研究者の一人であり、ハノイの塔は彼に因んだ"ルーカスタワー"の名も持っている。

出典[編集]

  1. ^ a b ユークリッド 1971, pp. 225–226, 第9巻、命題36.
  2. ^ a b c d e f g 淡中 1982, pp. 65–67.
  3. ^ 和田 1981, p. 51.
  4. ^ a b 中村 2008, pp. 83f.
  5. ^ 中村 2008, p. 80.
  6. ^ The Prime Pages, The Top Ten Record Primes
  7. ^ Eric W. Weisstein
  8. ^ 中村 2008, p. 81.
  9. ^ a b 和田 1981, pp. 59-61
  10. ^ 和田 1981, p. 192.
  11. ^ a b 和田 1981, p. 193
  12. ^ Erdős, P.; Shorey, T. N. (1976). “On the greatest prime factor of 2p − 1 for a prime p, and other expressions” (PDF). Acta Arithmetica (Institute of Mathematics Polish Academy of Sciences) 30 (3): 257-265. http://www.renyi.hu/~p_erdos/1976-28.pdf. 
  13. ^ 中村 2008, p. 87.
  14. ^ a b GIMPS Discovers 35th Mersenne Prime.
  15. ^ 中村 2008, pp. 82–84.
  16. ^ Lucas 1878.
  17. ^ Lucas 1969.
  18. ^ 中村 2008, pp. 84f.
  19. ^ 和田 1981, pp. 50–52, 194–199.
  20. ^ 和田 1999, §5 リュカ・テスト.
  21. ^ a b c d e f Landon Curt Noll, Mersenne Prime Digits and Names.
  22. ^ The Prime Pages, Mersenne Primes: History, Theorems and Lists.
  23. ^ The Prime Pages, M107: Fauquembergue or Powers?.
  24. ^ The Prime Pages, The finding of the 32nd Mersenne.
  25. ^ Chris Caldwell, The Largest Known Primes.
  26. ^ The Prime Pages, A Prime of Record Size! 21257787 − 1.
  27. ^ GIMPS Discovers 36th Known Mersenne Prime.
  28. ^ GIMPS Discovers 37th Known Mersenne Prime.
  29. ^ GIMPS Finds First Million-Digit Prime, Stakes Claim to $50,000 EFF Award.
  30. ^ GIMPS, Researchers Discover Largest Multi-Million-Digit Prime Using Entropia Distributed Computing Grid.
  31. ^ GIMPS, Mersenne Project Discovers Largest Known Prime Number on World-Wide Volunteer Computer Grid.
  32. ^ GIMPS, Mersenne.org Project Discovers New Largest Known Prime Number, 224,036,583 − 1.
  33. ^ GIMPS, Mersenne.org Project Discovers New Largest Known Prime Number, 225,964,951 − 1.
  34. ^ GIMPS, Mersenne.org Project Discovers New Largest Known Prime Number, 230,402,457 − 1.
  35. ^ GIMPS, Mersenne.org Project Discovers Largest Known Prime Number, 232,582,657 − 1.
  36. ^ a b Titanic Primes Raced to Win $100,000 Research Award. Retrieved on 2008-09-16.
  37. ^ GIMPS, GIMPS Project Discovers Largest Known Prime Number, 257,885,161 − 1
  38. ^ 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日閲覧。 
  39. ^ Largest Known Prime, 49th Known Mersenne Prime Found!!”. Great Internet Mersenne Prime Search. 2016年1月19日閲覧。
  40. ^ P. T. Bateman, J. L. Selfridge, S. S. Wagstaff Jr., "The new Mersenne conjecture", American Mathematical Monthly, 96 (1989), 125–128.

参考文献[編集]

関連項目[編集]

外部リンク[編集]