「メルセンヌ数」の版間の差分
→メルセンヌ素数: オンライン数列を追加 |
|||
41行目: | 41行目: | ||
=== メルセンヌ素数 === |
=== メルセンヌ素数 === |
||
{{#time:Y年n月}}現在、メルセンヌ素数は48個まで知られている。ただし、メルセンヌ素数としての番号が確定しているものは、 |
{{#time:Y年n月}}現在、メルセンヌ素数は48個まで知られている。ただし、メルセンヌ素数としての番号が確定しているものは、46番目までであり、 |
||
:''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({{OEIS|A000043}}) |
:''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({{OEIS|A000043}}) |
||
における ''M{{sub|p}}'' がそうである。さらに |
における ''M{{sub|p}}'' がそうである。さらに47,48番目の候補として ''p'' = 43112609,57885161 が挙がっており、現在間に素数がないかどうか検証中である。 |
||
[[分散コンピューティング]]によるプロジェクト [[GIMPS]] はメルセンヌ素数を発見することを目的としており、近年発見されたものは全てこのプロジェクトによるものである。 |
[[分散コンピューティング]]によるプロジェクト [[GIMPS]] はメルセンヌ素数を発見することを目的としており、近年発見されたものは全てこのプロジェクトによるものである。 |
2015年10月29日 (木) 11:11時点における版
メルセンヌ数(メルセンヌすう、英: 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 の最大の素因数 q は q ≧ c5 p log p(c5 は計算可能な定数)を満足する(Erdős-Shoreyの定理1)[11]。
完全数
Mp = 2p − 1 が素数であるならば、2p−1(2p − 1) は完全数となる[3][12]。この定理はすでに紀元前4世紀のエウクレイデス(ユークリッド)によって証明されていた[13]。およそ二千年の後に、全ての偶数の完全数はこの形の時に限るということが18世紀のレオンハルト・オイラーにより証明された[12]。
メルセンヌ素数
2024年12月現在、メルセンヌ素数は48個まで知られている。ただし、メルセンヌ素数としての番号が確定しているものは、46番目までであり、
- 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(オンライン整数列大辞典の数列 A000043)
における Mp がそうである。さらに47,48番目の候補として p = 43112609,57885161 が挙がっており、現在間に素数がないかどうか検証中である。
分散コンピューティングによるプロジェクト 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) と定義すると、
証明はリュカ・テストの証明を参照。
リュカ-レーマー・テスト
デリック・ヘンリー・レーマー (en) は、エドゥアール・リュカの判定法を改良し、今日ではリュカ-レーマー・テスト (Lucas-Lehmer primality test) と呼ばれる、メルセンヌ数に対する素数判定法を確立した。
- p が奇素数のとき、Mp が素数となるための必要十分条件は、S0 = 4, Sn = Sn−12 − 2 (n ≧ 1) と定義したときに Sp−2 が Mp で割り切れることである[17][18][19]。
リュカ-レーマー・テストは二進計算機用のアルゴリズムに向いており、コンピュータによるメルセンヌ素数の発見には、この判定法が用いられてきた。例えば、2p ≡ 1 (mod Mp) より、A・2p + B ≡ A + B (mod Mp) が成り立つので、Mp で割る割り算の代わりに、二進法で p 桁のシフト演算と足し算だけで計算できる。 現在「最大の」素数がメルセンヌ素数である理由はこの判定法にあると言える。
証明はリュカ-レーマー・テストの証明を参照。
発見されているメルセンヌ素数の表
# | 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 | 618970019642690137449562111 | 27 | 1911年 | R・E・パワーズ |
11 | 107 | 162259276829213363391578010288127 | 33 | 1914年 | R・E・パワーズ[22] |
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日[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] |
未解決問題
- メルセンヌ素数は無限に存在するか?
- 素数 p に対して Mp が合成数であるとき、これをメルセンヌ合成数と呼ぶことにして、それは無限に存在するか?
- 平方因子を持つメルセンヌ数 Mp(p は素数)が存在するか?
- n を奇数とするとき、次の3つの条件のうち2つが満足されれば、残りの1つも満足されると予想されており、n < 100000 に対してこの予想は正しいと確認されている[39]。
- Mn が素数
- n = 2k ± 1 または 4k ± 3
- (2n + 1)/3 が素数
脚注
- ^ Mathworld
- ^ 『岩波数学辞典』第3版 180E ではそのようになっている。一松(2007) p. 73 によれば、これは日本のごく一部での用法であるらしい。『岩波数学辞典』第4版 194D では、メルセンヌ数とメルセンヌ素数を使い分けている。
- ^ a b c d e f g 淡中(1982)、65-67頁
- ^ 中村(2008)、80頁
- ^ 和田(1981)、51頁
- ^ 中村(2008)、83-84頁
- ^ 中村(2008)、87頁
- ^ 中村(2008)、81頁
- ^ 和田(1981)、192頁
- ^ a b 和田(1981)、193頁
- ^ 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 .
- ^ a b 和田(1981)、59-61頁
- ^ 『ユークリッド原論』第9巻、命題36、225-226頁
- ^ 中村(2008)、82-84頁
- ^ Lucas(1878)
- ^ Lucas(1969)
- ^ 中村(2008)、84-85頁
- ^ 和田(1981)、50-52頁、194-199頁
- ^ 和田(1999)、§5 リュカ・テスト
- ^ a b c d e f Landon Curt Noll, Mersenne Prime Digits and Names.
- ^ The Prime Pages, Mersenne Primes: History, Theorems and Lists.
- ^ The Prime Pages, M107: Fauquembergue or Powers?.
- ^ The Prime Pages, The finding of the 32nd Mersenne.
- ^ Chris Caldwell, The Largest Known Primes.
- ^ The Prime Pages, A Prime of Record Size! 21257787 − 1.
- ^ GIMPS Discovers 35th Mersenne Prime.
- ^ GIMPS Discovers 36th Known Mersenne Prime.
- ^ GIMPS Discovers 37th Known Mersenne Prime.
- ^ GIMPS Finds First Million-Digit Prime, Stakes Claim to $50,000 EFF Award.
- ^ GIMPS, Researchers Discover Largest Multi-Million-Digit Prime Using Entropia Distributed Computing Grid.
- ^ GIMPS, Mersenne Project Discovers Largest Known Prime Number on World-Wide Volunteer Computer Grid.
- ^ GIMPS, Mersenne.org Project Discovers New Largest Known Prime Number, 224,036,583 − 1.
- ^ GIMPS, Mersenne.org Project Discovers New Largest Known Prime Number, 225,964,951 − 1.
- ^ GIMPS, Mersenne.org Project Discovers New Largest Known Prime Number, 230,402,457 − 1.
- ^ GIMPS, Mersenne.org Project Discovers Largest Known Prime Number, 232,582,657 − 1.
- ^ a b Titanic Primes Raced to Win $100,000 Research Award. Retrieved on 2008-09-16.
- ^ GIMPS, GIMPS Project Discovers Largest Known Prime Number, 257,885,161-1
- ^ CASEY JOHNSTON (2013年2月7日). “「これまでで最大の素数」を発見”. WIRED (WIRED.jp) 2013年2月10日閲覧。
- ^ P. T. Bateman, J. L. Selfridge, S. S. Wagstaff Jr., "The new Mersenne conjecture", American Mathematical Monthly, 96 (1989), 125-128.
参考文献
- 淡中忠郎 著「メルセンヌ数物語」、数学セミナー編集部編 編『数の世界』日本評論社〈数学セミナー増刊 数学セミナー・リーディングス〉、1982年9月30日、65-67頁。
- 中村滋『フィボナッチ数の小宇宙(ミクロコスモス) フィボナッチ数、リュカ数、黄金分割』日本評論社、2002年9月30日。ISBN 4-535-78281-4。
- 中村滋『フィボナッチ数の小宇宙(ミクロコスモス) フィボナッチ数、リュカ数、黄金分割』(改訂版)日本評論社、2008年1月25日。ISBN 978-4-535-78492-5 。
- ハイベア・メンゲ編 編『ユークリッド原論』中村幸四郎・寺阪英孝・伊東俊太郎・池田美恵訳・解説、共立出版。 - 全13巻の最初の邦訳。
- (ハードカバー)1971年7月。ISBN 4-320-01072-8
- (縮刷版)1996年6月。ISBN 4-320-01513-4
- (追補版)2011年5月。ISBN 978-4-320-01965-2
- 一松信『数のエッセイ』筑摩書店〈ちくま学芸文庫〉、2007年1月10日。ISBN 978-4-480-09041-6 。
- 和田秀男『数の世界 整数論への道』岩波書店〈科学ライブラリー〉、1981年7月10日。ISBN 4-00-005500-3 。 - 前編は1次式の整数論、後編は2次式の整数論。
- 和田秀男『コンピュータと素因子分解』(改訂版)遊星社(発行) 星雲社(発売)、1999年4月(原著1987年10月20日)。ISBN 4-7952-6858-4 ISBN 4-7952-6889-4 。
- Lucas, Edouard (1878). “Théorie des Fonctions Numériques Simplement Périodiques” (French) (PDF). American Journal of Mathematics (Johns Hopkins University Press) 1 (2): pp. 184-240 et 289-321. doi:10.2307/2369308 .
- Lucas, Edouard (1969) (English) (PDF). The Theory of Simply Periodic Numerical Functions. Translated by Sidney Kravitz. Fibonacci Association. p. 77 - Lucas(1878)の前半の英訳。
関連項目
- 完全数
- フェルマー数
- メルセンヌ・ツイスタ(メルセンヌ素数を用いた擬似乱数発生アルゴリズム)
- レピュニット
- GIMPS
外部リンク
- 世界大百科事典 第2版『メルセンヌ数』 - コトバンク
- リュカテストによるメルセンヌ素数の発見法 (PDF)
- Weisstein, Eric W. "Mersenne number". mathworld.wolfram.com (英語).
- Weisstein, Eric W. "Mersenne prime". mathworld.wolfram.com (英語).
- Mersenne Primes: History, Theorems and Lists(英語)
- The Largest Known Primes(英語)
- GIMPS(英語)