メルセンヌ数

メルセンヌ数の最新ニュースをまとめて検索！

メルセンヌ数（めるせんぬすう、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 は合成数である。 余談であるが、M67の誤りは1903年10月、ニューヨークで開かれたアメリカ数学会で、F.D.コールが193707721×761838257287を黒板に計算し、M67と一致することを証明した。この間一言もしゃべらず、席に戻った後、少し間を置いて感動の拍手が沸き起こったと伝えられている。

1957年にリーゼル数の発見者でもあるスウェーデンの数学者であるハンス・リーゼルがコンピュータを使用して18番目のメルセンヌ素数を発見して以降、発見にはコンピュータが使用されており、コンピュータの進歩と共に新たなメルセンヌ素数が発見されつつある。

[編集] 数学的性質

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世紀のオイラーにより証明された。

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

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

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

分散コンピューティングによるプロジェクト 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によって発見された中では、発見順序と桁数が逆転した初めてのケースである。

[編集] 素数判定法

メルセンヌ数が素数かどうかを調べるための判定法としてリュカテストがある。

  • p が奇素数のとき、Mp が素数となるための必要十分条件は、S0 = 4, Sk = Sk−12 − 2 (k > 1) と定義したときに Sp − 2 が Mp で割り切れることである。

[編集] 発見されているメルセンヌ素数と対応する完全数の表

オンライン整数列大辞典の数列 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年 パワーズ
11 107 162259276…010288127 33 1914年 パワーズ[6]
12 127 170141183…884105727 39 1876年 リュカ
13 521 686479766…115057151 157 1952年1月30日 ロビンソン, 使用:SWAC
14 607 531137992…031728127 183 1952年1月30日 ロビンソン
15 1,279 104079321…168729087 386 1952年6月25日 ロビンソン
16 2,203 147597991…697771007 664 1952年10月7日 ロビンソン
17 2,281 446087557…132836351 687 1952年10月9日 ロビンソン
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 / Curtis Cooper & Steven Boone[18]
44[*] 32,582,657 124575026…053967871 9,808,358 2006年9月4日 GIMPS / Curtis Cooper & 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]

 * 39-47番目は未確定の順番。過去には29番目のメルセンヌ素数は30, 31番目が発見された後に発見されている。また47番目の後に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. ^ い ろ は に ほ へ 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. ^ い ろ 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://wkp.fresheye.com/wikipedia/%E3%83%A1%E3%83%AB%E3%82%BB%E3%83%B3%E3%83%8C%E6%95%B0" より作成
フリー百科事典『ウィキペディア（Wikipedia）』 Text is available under GNU Free Documentation License.

最終更新 2009年10月30日 (金) 15:17 （日時は個人設定で未設定ならばUTC）。
【メルセンヌ数】変更履歴

ご利用上の注意

もっと調べる！

メルセンヌ数　まとめて検索