メルセンヌ数

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

メルセンヌ数(メルセンヌすう、: Mersenne number)とは、2の冪よりも 1 小さい自然数、すなわち 2n − 1(n は自然数)の形の自然数のことである。これを Mn で表すことが多い。2進数で表記すると、n 桁の 11…11 である。特に、素数であるメルセンヌ数をメルセンヌ素数(メルセンヌそすう、: Mersenne prime)という。Mn が素数ならば n は素数であるが、逆に n が素数であっても Mn は素数とは限らない (M11 = 23 × 89)。後述するように、効率的な素数判定法によって、巨大な素数の実例としてメルセンヌ素数を発見することが特に興味の対象となっている。このため近年では、分散コンピューティングによるプロジェクト GIMPS (Great Internet Mersenne Prime Search) によるメルセンヌ素数の発見が進められている。

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

歴史[編集]

1644年マラン・メルセンヌは、 2n − 1 が素数になるのは、n ≤ 257 では、n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 だけであると主張した。しかしその主張の一部は誤っていた。リストに含まれていない M61, M89, M107 が素数であり、リストに含まれている M67, M257合成数である[3][4]

M31 は1772年、 レオンハルト・オイラー によって素数であると証明された[3][5]

M127 は1876年、 エドゥアール・リュカ によって素数であると証明された[3][6]

M61 が素数であることは、1883年にイヴァン・パヴシン英語版によって示された[3]

M67 が素数でないことは、1903年10月、フランク・ネルソン・コール英語版により示された。彼はニューヨークで開かれたアメリカ数学会で 193707721 × 761838257287 を黒板に計算し、M67 と一致することを証明した。この間一言もしゃべらず、席に戻った後、少し間を置いて拍手が沸き起こったと伝えられている[7]

1952年、ラファエル・M・ロビンソンSWAC を利用して M521 から M2281 まで、5つのメルセンヌ素数を発見[3]して以降、発見にはコンピュータが使用されており、コンピュータの進歩と共に新たなメルセンヌ素数が発見されつつある。

数学的性質[編集]

Mn が素数ならば n は素数であるが、n が素数であっても Mn は素数とは限らない。前者の対偶である命題「n が合成数ならば Mn は合成数である」は次の式から示される[3][8]

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

素因数[編集]

p が素数の時、Mp の素因数は 2p を法として 1 と合同[9]、かつ 8 を法として 1 または −1 と合同である[10]。また、p が 4 を法として 3 と合同なとき、Mp が 2p + 1 で割れることと、2p + 1 が素数であることは同値である[10]。また、Mp の最大の素因数 qqc5 p log pc5 は計算可能な定数)を満足する(Erdős-Shoreyの定理1)[11]

完全数[編集]

Mp = 2p − 1 が素数であるならば、2p−1(2p − 1) は完全数となる[3][12]。この定理はすでに紀元前4世紀エウクレイデス(ユークリッド)によって証明されていた[13]。およそ二千年の後に、全ての偶数の完全数はこの形の時に限るということが18世紀のレオンハルト・オイラーにより証明された[12]

メルセンヌ素数[編集]

2014年4月現在、メルセンヌ素数は48個まで知られている。ただし、メルセンヌ素数としての番号が確定しているものは、42番目までであり、

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

における Mp がそうである。さらに43番目の候補として p = 30,402,457 が挙がっており、現在間に素数がないかどうか検証中である。

分散コンピューティングによるプロジェクト GIMPS はメルセンヌ素数を発見することを目的としており、近年発見されたものは全てこのプロジェクトによるものである。

  • 2004年5月15日、GIMPS は41番目の素数候補が発見されたことを発表した。検証後723万5733桁の数、224036583 − 1 が素数であることが確認された。
  • 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 によって発見された中では、発見順序と桁数が逆転した初めてのケースである。

素数判定法[編集]

メルセンヌ数が素数かどうかを調べるための判定法としてリュカ・テスト (Lucas test) とリュカ-レーマー・テスト (Lucas-Lehmer primality test) がある。

リュカ・テスト[編集]

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

M_p \not | S_k \ \ (0 \leqq k \leqq p-2) ならば、Mp は合成数である。
M_p \mid  S_{p-2} ならば、Mp は素数である[14][15][16]

証明はリュカ・テストの証明を参照。

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

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

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

リュカ-レーマー・テストは二進法を用いたコンピュータの処理に向いており、コンピュータによるメルセンヌ素数の発見には、この判定法が用いられてきた。 例えば、2p ≡ 1 (mod Mp) より、A・2p + BA + B (mod Mp) が成り立つので、Mp で割る割り算の代わりに、二進法で p 桁のシフト演算と足し算だけで計算できる。 現在「最大の」素数がメルセンヌ素数である理由はこの判定法にあると言える。

証明はリュカ-レーマー・テストの証明を参照。

発見されているメルセンヌ素数の表[編集]

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

# p Mp Mp の桁数 発見日 発見者
1 2 3 1 紀元前5世紀[20] 古代ギリシャの数学者
2 3 7 1 紀元前5世紀[20] 古代ギリシャの数学者
3 5 31 2 紀元前3世紀[20] 古代ギリシャの数学者
4 7 127 3 紀元前3世紀[20] 古代ギリシャの数学者
5 13 8191 4 1456年 不明[21]
6 17 131071 6 1588年 ピエトロ・カタルディ英語版
7 19 524287 6 1588年 ピエトロ・カタルディ
8 31 2147483647 10 1772年 レオンハルト・オイラー
9 61 2305843009213693951 19 1883年 イヴァン・パヴシン英語版
10 89 618970019…449562111 27 1911年 R・E・パワーズ英語版
11 107 162259276…010288127 33 1914年 R・E・パワーズ[22]
12 127 170141183…884105727 39 1876年 エドゥアール・リュカ
13 521 686479766…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日[20] デイヴィッド・スローウィンスキー
31 216,091 746093103…815528447 65,050 1985年9月1日[20] デイヴィッド・スローウィンスキー
32 756,839 174135906…544677887 227,832 1992年2月19日 デイヴィッド・スローウィンスキー & ポール・ゲイジ英語版 使用:Harwell Lab Cray-2[23]
33 859,433 129498125…500142591 258,716 1994年1月4日[24] デイヴィッド・スローウィンスキー & ポール・ゲイジ
34 1,257,787 412245773…089366527 378,632 1996年9月3日 デイヴィッド・スローウィンスキー & ポール・ゲイジ[25]
35 1,398,269 814717564…451315711 420,921 1996年11月13日 GIMPS / Joel Armengaud[26]
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]

  •  43-48番目は未確定の順番。過去には29番目のメルセンヌ素数は30, 31番目が発見された後に発見されている。また47番目の後に45, 46番目が発見されている。

未解決問題[編集]

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

脚注[編集]

  1. ^ Mathworld
  2. ^ 『岩波数学辞典』第3版 180E ではそのようになっている。一松(2007) p. 73 によれば、これは日本のごく一部での用法であるらしい。『岩波数学辞典』第4版 194D では、メルセンヌ数とメルセンヌ素数を使い分けている。
  3. ^ a b c d e f g 淡中(1982)、65-67頁
  4. ^ 中村(2008)、80頁
  5. ^ 和田(1981)、51頁
  6. ^ 中村(2008)、83-84頁
  7. ^ 中村(2008)、87頁
  8. ^ 中村(2008)、81頁
  9. ^ 和田(1981)、192頁
  10. ^ a b 和田(1981)、193頁
  11. ^ 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. 
  12. ^ a b 和田(1981)、59-61頁
  13. ^ ユークリッド原論第9巻、命題36、225-226頁
  14. ^ 中村(2008)、82-84頁
  15. ^ Lucas(1878)
  16. ^ Lucas(1969)
  17. ^ 中村(2008)、84-85頁
  18. ^ 和田(1981)、50-52頁、194-199頁
  19. ^ 和田(1999)、§5 リュカ・テスト
  20. ^ a b c d e f Landon Curt Noll, Mersenne Prime Digits and Names.
  21. ^ The Prime Pages, Mersenne Primes: History, Theorems and Lists.
  22. ^ The Prime Pages, M107: Fauquembergue or Powers?.
  23. ^ The Prime Pages, The finding of the 32nd Mersenne.
  24. ^ Chris Caldwell, The Largest Known Primes.
  25. ^ The Prime Pages, A Prime of Record Size! 21257787 − 1.
  26. ^ GIMPS Discovers 35th Mersenne Prime.
  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. ^ P. T. Bateman, J. L. Selfridge, S. S. Wagstaff Jr., "The new Mersenne conjecture", American Mathematical Monthly, 96 (1989), 125-128.

参考文献[編集]

関連項目[編集]

外部リンク[編集]