メルセンヌ数

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

メルセンヌ数（メルセンヌすう、Mersenne number）とは、2の冪よりも 1 小さい自然数、すなわち 2n − 1 の形の自然数である。これを Mn で表すことが多い。2進数で表記すると n 桁の 1111…1 である。また、素数であるメルセンヌ数をメルセンヌ素数という。後述するように、完全数との関連によって、メルセンヌ素数が特に興味の対象となっている。Mn がメルセンヌ素数であるためには n が素数であることが必要である。メルセンヌ数という語で、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 は合成数である。

M31 は1772年、 レオンハルト・オイラー によって、 M127 は1876年、 エドゥアール・リュカ によって、それぞれ素数であると証明された。

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

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

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

[編集] 数学的性質

n が素数でなければ Mn は素数とならないが、n が素数であっても Mn が素数になるとは限らない。前者は次の式から示される；

(2^a-1)(1+2^a+2^{2a}+2^{3a}+\cdots+2^{(b-1)a})=2^{ab}-1.

p が素数の時、Mp の素因数は 2p を法として 1 と合同、かつ 8 を法として 1 または −1 と合同である。また、p が 4 を法として 3 と合同なとき、Mp が 2p + 1 で割れることと、2p + 1 が素数であることは同値である。また、Mp の最大の素因数 q は q ≥ Cn log p（C は計算可能な定数）を満足することが知られている[3]。

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

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

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

としたときの Mp がそうである。さらに41番目の候補として p = 24036583 が挙がっており、現在間に素数がないかどうか検証中である。

分散コンピューティングによるプロジェクト 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)がある。

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

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

# p Mp Mp の桁数 発見日 発見者
1 2 3 1 紀元前5世紀[4] 古代ギリシャの数学者
2 3 7 1 紀元前5世紀[4] 古代ギリシャの数学者
3 5 31 2 紀元前3世紀[4] 古代ギリシャの数学者
4 7 127 3 紀元前3世紀[4] 古代ギリシャの数学者
5 13 8191 4 1456年 不明 [5]
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・パワーズ[6]
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日[4] デイヴィッド・スローウィンスキー
31 216,091 746093103…815528447 65,050 1985年9月1日[4] デイヴィッド・スローウィンスキー
32 756,839 174135906…544677887 227,832 1992年2月19日 デイヴィッド・スローウィンスキー & ポール・ゲイジ（英語版） 使用:Harwell Lab Cray-2[7]
33 859,433 129498125…500142591 258,716 1994年1月4日[8] デイヴィッド・スローウィンスキー & ポール・ゲイジ
34 1,257,787 412245773…089366527 378,632 1996年9月3日 デイヴィッド・スローウィンスキー & ポール・ゲイジ[9]
35 1,398,269 814717564…451315711 420,921 1996年11月13日 GIMPS / Joel Armengaud[10]
36 2,976,221 623340076…729201151 895,932 1997年8月24日 GIMPS / Gordon Spence[11]
37 3,021,377 127411683…024694271 909,526 1998年1月27日 GIMPS / Roland Clarkson[12]
38 6,972,593 437075744…924193791 2,098,960 1999年6月1日 GIMPS / Nayan Hajratwala[13]
39 13,466,917 924947738…256259071 4,053,946 2001年11月14日 GIMPS / Michael Cameron[14]
40 20,996,011 125976895…855682047 6,320,430 2003年11月17日 GIMPS / Michael Shafer[15]
41[*] 24,036,583 299410429…733969407 7,235,733 2004年5月15日 GIMPS / Josh Findley[16]
42[*] 25,964,951 122164630…577077247 7,816,230 2005年2月18日 GIMPS / Martin Nowak[17]
43[*] 30,402,457 315416475…652943871 9,152,052 2005年12月15日 GIMPS / カーティス・クーパー（英語版） & Steven Boone[18]
44[*] 32,582,657 124575026…053967871 9,808,358 2006年9月4日 GIMPS / カーティス・クーパー & Steven Boone[19]
45[*] 37,156,667 202254406…308220927 11,185,272 2008年9月6日 GIMPS / Hans-Michael Elvenich[20]
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 / エドソン・スミス[20]

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

[編集] 未解決問題

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

[編集] 脚注

[ヘルプ]
  1. ^ MathWorld
  2. ^ 『岩波数学辞典』第3版 180E ではそのようになっている。一松信（『数のエッセイ』ISBN 978-4480090416 p. 73）によれば、これは日本のごく一部での用法であるらしい。『岩波数学辞典』第4版 194D では、メルセンヌ数とメルセンヌ素数を使い分けている。
  3. ^ Erdős and Shorey, On the greatest prime factor of 2p − 1 for a prime p, and other expressions, Acta Arith. 30 (1976), 257-265.
  4. ^ a b c d e f Landon Curt Noll, Mersenne Prime Digits and Names.
  5. ^ The Prime Pages, Mersenne Primes: History, Theorems and Lists.
  6. ^ The Prime Pages, M107: Fauquembergue or Powers?.
  7. ^ The Prime Pages, The finding of the 32nd Mersenne.
  8. ^ Chris Caldwell, The Largest Known Primes.
  9. ^ The Prime Pages, A Prime of Record Size! 21257787-1.
  10. ^ GIMPS Discovers 35th Mersenne Prime.
  11. ^ GIMPS Discovers 36th Known Mersenne Prime.
  12. ^ GIMPS Discovers 37th Known Mersenne Prime.
  13. ^ GIMPS Finds First Million-Digit Prime, Stakes Claim to $50,000 EFF Award.
  14. ^ GIMPS, Researchers Discover Largest Multi-Million-Digit Prime Using Entropia Distributed Computing Grid.
  15. ^ GIMPS, Mersenne Project Discovers Largest Known Prime Number on World-Wide Volunteer Computer Grid.
  16. ^ GIMPS, Mersenne.org Project Discovers New Largest Known Prime Number, 224,036,583-1.
  17. ^ GIMPS, Mersenne.org Project Discovers New Largest Known Prime Number, 225,964,951-1.
  18. ^ GIMPS, Mersenne.org Project Discovers New Largest Known Prime Number, 230,402,457-1.
  19. ^ GIMPS, Mersenne.org Project Discovers Largest Known Prime Number, 232,582,657-1.
  20. ^ a b Titanic Primes Raced to Win $100,000 Research Award. Retrieved on 2008-09-16.
  21. ^ P. T. Bateman, J. L. Selfridge, S. S. Wagstaff Jr., "The new Mersenne conjecture", American Mathematical Monthly, 96 (1989), 125-128.

[編集] 関連項目

[編集] 外部リンク

「http://ja.wikipedia.org/w/index.php?title=%E3%83%A1%E3%83%AB%E3%82%BB%E3%83%B3%E3%83%8C%E6%95%B0&oldid=41105787」より作成
個人用ツール
名前空間
変種
操作
案内
ヘルプ
ツールボックス
他の言語