「メルセンヌ数」の版間の差分
ja>B08061810 細 (→外部リンク: cat) |
細 (1版 をインポートしました) |
(相違点なし)
|
2018/8/19/ (日) 17:44時点における最新版
メルセンヌ数(メルセンヌすう、英: Mersenne number)とは、2の冪よりも 1 小さい自然数、すなわち 2n − 1(n は自然数)の形の自然数のことである。これを Mn で表すことが多い。2進数表記では、n 桁の 11⋯11 となる。
- 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, …(オンライン整数列大辞典の数列 A000225から初項 0 を除いたもの。太字は素数、素数を除いたメルセンヌ数はオンライン整数列大辞典の数列 A135972を参照)
Mn = 2n − 1 が素数ならば n もまた素数であるが、逆は成立しない (M11 = 2047 = 23 × 89)。素数であるメルセンヌ数をメルセンヌ素数(メルセンヌそすう、英: Mersenne prime)という。
なお、「メルセンヌ数」という語で、n が素数であるもののみを指したり[1]、さらに狭くメルセンヌ素数を指す場合もある[注釈 1]。
Contents
基本的な性質
Mn が素数ならば n もまた素数であることは、次の式から分かる[2][3]:
- 2ab − 1 = (2a − 1)(1 + 2a + 22a + ⋯ + 2(b−1)a).
対偶命題「n が合成数ならば Mn は合成数である」が示される。また、この等式より、m | n のとき Mm | Mn である。
しかし、逆に p が素数でも Mp が素数とは限らない(最小の反例:M11 = 2047 = 23 × 89)。そのため、数が大きくなるにつれ直接素因数分解を試みるのでなく、間接的に素数であるかないかを判定する素数判定法が考案された。これが後述するエドゥアール・リュカによる判定法(リュカ・テスト)と、それを改良し今日使われているデリック・ヘンリー・レーマーによる判定法(リュカ–レーマー・テスト)である。
完全数
Mp = 2p − 1 が素数ならば、2p−1(2p − 1) は完全数である[2][4]。この定理はすでに紀元前3世紀頃のユークリッド原論で証明されていた[5]。したがって、完全数の探索はメルセンヌ素数の探索に終始された。
2p−1(2p − 1) は明らかに偶数であるが、偶数の完全数でこの生成式から得られるもの以外はないのか2000年間にわたって未解決であったが、18世紀にオイラーによりこの形に限ることが証明された[4]。
メルセンヌ数の素因数
p を素数とする。
- Mp の素因数は 2p を法として 1 と合同[6]、かつ 8 を法として 1 または −1 と合同である[7]。
- p ≡ 3 (mod 4) のとき、Mp が 2p + 1 で割れることと、2p + 1 が素数であることは同値である[7]。
- Mp の最大素因数を q とすると、q ≥ c5 p log p(c5 は計算可能な定数)(Erdős–Shoreyの定理1)[8]
メルセンヌ素数
メルセンヌ素数(メルセンヌそすう、Mersenne prime)とは、素数であるメルセンヌ数のことである。
2018年1月現在知られている最大のメルセンヌ素数は、2017年12月に発見された、それまでに分かっている中で50番目のメルセンヌ素数 277232917 − 1 であり、十進法で表記したときの桁数は2324万9425桁[9]に及ぶ。
メルセンヌ素数の発見の歴史
紀元前3世紀頃のユークリッド原論において知られる完全数の生成式で見出されている[5]。そこから素数であるメルセンヌ数を見つけることこそが完全数を見つけることとなった。Mn = 2n − 1 が素数ならば n もまた素数である。古代ギリシア数学者は p = 5 と 7 のとき Mp が素数であることを見つけた。しかし p が素数であってもMp は素数とは限らない(例:M11 = 2047 = 23 × 89)。そのため完全数の探索は困難をきわめた。
17世紀までに p = 13, 17, 19 のとき Mp が素数であることが分かるが、1644年、マラン・メルセンヌは「素数 p で 2p − 1 が素数になるのは、19 < p ≤ 257 では p = 31, 67, 127, 257 の4つの場合だけである」という大胆不敵な予想を公表した。しかしメルセンヌ自身はその予想を証明することができず、しかもその予想の一部は誤っていた。
成果を見るのはメルセンヌが予想を公表してから128年後、1772年、オイラー(p = 31 では素数)[2][10]。その次の成果はさらに104年後、1876年、リュカ(効率的な素数判定法リュカ・テストを考案、p = 67 では素数でない、p = 127 では素数[2][11])であった。その後リュカ・テストは改良が加えられ、メルセンヌが予想した範囲にない3個が付け加えられた(p = 61(1883年)、p = 89(1911年)、p = 107(1914年))。メルセンヌが予想した最後の数 p = 257 について決着がついたのは1922年のことであった。残念ながらこれも合成数だった[2][12]。
結局メルセンヌの4つの予想のうち2つが当たり、2つは外れた。なおかつ、間に予想できなかった3つが含まれていたことを考えれば予想は五分以上の確率とはいえないが、その後の歴史を見ても大きな原動力となり先駆的であったことに敬意を表し、素数であるメルセンヌ数をメルセンヌ素数という。
1903年10月、アメリカの数学者フランク・ネルソン・コールは実際の素因数分解を探し求め、ニューヨークで開かれたアメリカ数学会の会議で 193707721 × 761838257287 を黒板に計算し、M67 と一致することを証明した。この間一言もしゃべらず、席に戻った後、少し間を置いて拍手が沸き起こったと伝えられている[13]。
1952年、ラファエル・M・ロビンソンが SWAC を利用して M521 から M2281 まで、5つのメルセンヌ素数を発見[2]して以降、発見にはコンピュータが使用されており、コンピュータの進歩と共に新たなメルセンヌ素数が発見されつつある。
1996年、メルセンヌ素数を発見することを目的として作られた分散コンピューティングによるプロジェクト GIMPS が発足し、35番目のメルセンヌ素数 M1,398,269(1996年11月13日、Joel Armengaud[14])以来、GIMPSによるメルセンヌ素数の発見が相次いでいる。
2008年8月23日、GIMPS は46番目の素数候補が、カリフォルニア大学ロサンゼルス校の数学部のコンピュータによって発見されたと報じた。この素数は電子フロンティア財団が賞金を懸けた1000万桁以上の最初の素数となるため、GIMPS によって同校数学部に50,000ドル、慈善事業に25,000ドル、残りを前の6つのメルセンヌ素数の発見者へ分配することになった。
2008年9月6日、GIMPS は45番目の素数候補が、ドイツで発見されたと報じた。これは、GIMPS によって発見された中では、発見順序と桁数が逆転した初めてのケースである。
素数判定法
知られている中で最大の素数が1876年以降ほぼ一貫してメルセンヌ素数である理由は、この判定法にあると言える。
リュカ・テスト
p が (4j + 3) 型の素数のとき、S0 = 3, Sn = Sn−12 − 2 (n ≥ 1) で {Sn} を定義すると、
- [math]M_p \not \mid S_k \ (0\leqq k\leqq p-2)[/math] ならば、Mp は合成数である
- [math]M_p \mid S_{p-2}[/math] ならば、Mp は素数である[15][16][17]
アルゴリズム
アルゴリズムは以下の擬似コードで表される。
入力: p: (4j + 3) 型の素数であるテスト対象の整数
出力: PRIME:素数の場合, COMPOSIT:合成数の場合
Lucas_Test(p):
var s = 3
var MP = (1 << p) − 1
for n in range(2, p):
s = (s2 − 2) % MP
if s == 0 then:
return PRIME
else:
return COMPOSIT
リュカ–レーマー・テスト
p が奇素数のとき、S0 = 4, Sn = Sn−12 − 2 (n ≥ 1) で{Sn} を定義すると、
- [math]M_p \not \mid S_k \ (0\leqq k\leqq p-2)[/math] ならば、Mp は合成数である
- [math]M_p \mid S_{p-2}[/math] ならば、Mp は素数である[18][19][20]
リュカ–レーマー・テストは二進計算機用のアルゴリズムに向いており、コンピュータによるメルセンヌ素数の発見には、この判定法が用いられてきた。例えば、2p ≡ 1 (mod Mp) より、A·2p + B ≡ A + B (mod Mp) が成り立つので、Mp で割る割り算の代わりに、二進法で p 桁のシフト演算と足し算だけで計算できる。
アルゴリズム
アルゴリズムは以下の擬似コードで表される。
入力: p:奇素数であるテスト対象の整数 出力: PRIME:素数の場合, COMPOSIT:合成数の場合 Lucas_Lehmer_Test(p): var s = 4 var MP = (1 << p) − 1 for n in range(2, p): s = (s2 − 2) % MP if s == 0 then: return PRIME else: return COMPOSIT
入力: p:奇素数であるテスト対象の整数 出力: PRIME:素数の場合, COMPOSIT:合成数の場合 Lucas_Lehmer_Test_FAST(p): var s = 4 var M = 2p − 1 for n in range(2, p): var sqrt = s × s s = (sqrt & m) + (sqrt >> p) if s >= m then s = s − m s = s − 2 if s == 0 then return PRIME else return COMPOSIT
メルセンヌ素数の一覧
2018年1月現在、メルセンヌ素数は50個まで知られている。ただし、メルセンヌ素数としての番号が確定しているものは47番目までであり、
- 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, 43112609(オンライン整数列大辞典の数列 A000043, オンライン整数列大辞典の数列 A000668)
における Mp がそうである。さらに48, 49, 50番目の候補として p = 57885161, 74207281, 77232917 が挙がっており、間に素数がないかどうか検証中である。
# | 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] |
50[*] | 77,232,917 | 467333183359…069762179071 | 23,249,425 | 2017年12月26日 | GIMPS / Jonathan Pace[40] |
- 48から50番目は、2018年4月時点でより小さなメルセンヌ素数の個数を検証できていないことによる暫定的な順位である。過去には29番目のメルセンヌ素数は30, 31番目が発見された後に発見されている。また47番目の後に45, 46番目が発見されている。
未解決問題
- メルセンヌ素数は無数に存在するか?
- 素数 p に対して Mp が合成数であるとき、これをメルセンヌ合成数と呼ぶことにして、それは無数に存在するか?
- 平方因子を持つメルセンヌ数 Mp(p は素数)が存在するか?
- n を奇数とするとき、次の3つの条件のうち2つが満足されれば、残りの1つも満足されると予想されており、n < 105 に対してこの予想は正しいと確認されている[41]。
- Mn が素数
- n = 2k ± 1 または 4k ± 3
- (2n + 1)/3 が素数
脚注
注釈
出典
- ↑ Eric W. Weisstein
- ↑ 2.0 2.1 2.2 2.3 2.4 2.5 淡中 1982, pp. 65–67.
- ↑ 中村 2008, p. 81.
- ↑ 4.0 4.1 和田 1981, pp. 59-61
- ↑ 5.0 5.1 ユークリッド 1971, 第9巻、命題36.
- ↑ 和田 1981, p. 192.
- ↑ 7.0 7.1 和田 1981, p. 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 .
- ↑ The Prime Pages, The Top Ten Record Primes
- ↑ 和田 1981, p. 51.
- ↑ 中村 2008, pp. 83f.
- ↑ 中村 2008, p. 80.
- ↑ 中村 2008, p. 87.
- ↑ 14.0 14.1 GIMPS Discovers 35th Mersenne Prime.
- ↑ 中村 2008, pp. 82–84.
- ↑ Lucas 1878.
- ↑ Lucas 1969.
- ↑ 中村 2008, pp. 84f.
- ↑ 和田 1981, pp. 50–52, 194–199.
- ↑ 和田 1999, §5 リュカ・テスト.
- ↑ 21.0 21.1 21.2 21.3 21.4 21.5 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 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.
- ↑ 36.0 36.1 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閲覧.
- ↑ “Largest Known Prime, 49th Known Mersenne Prime Found!!”. Great Internet Mersenne Prime Search. . 2016閲覧.
- ↑ “GIMPS Project Discovers Largest Known Prime Number: 277,232,917 − 1”. Great Internet Mersenne Prime Search. . 2018閲覧.
- ↑ P. T. Bateman, J. L. Selfridge, S. S. Wagstaff Jr., "The new Mersenne conjecture", American Mathematical Monthly, 96 (1989), 125–128.
参考文献
- 淡中忠郎 「メルセンヌ数物語」『数の世界』 数学セミナー編集部編、日本評論社〈数学セミナー増刊 数学セミナー・リーディングス〉、1982-09-30、65-67。
- 中村滋 『フィボナッチ数の小宇宙(ミクロコスモス) フィボナッチ数、リュカ数、黄金分割』 日本評論社、2002-09-30。ISBN 4-535-78281-4。
- 中村滋 『フィボナッチ数の小宇宙(ミクロコスモス) フィボナッチ数、リュカ数、黄金分割』 日本評論社、2008-01-25、改訂版。ISBN 978-4-535-78492-5。
- 『岩波 数学辞典』 日本数学会 編、岩波書店、1985-12-10、第3版。ISBN 978-4-00-080016-7。
- 『岩波 数学辞典』 日本数学会 編、岩波書店、2007-03-15、第4版。ISBN 978-4-00-080309-0。
- ユークリッド 『ユークリッド原論』 ハイベア・メンゲ編、中村幸四郎・寺阪英孝・伊東俊太郎・池田美恵訳・解説、共立出版。 - 全13巻の最初の邦訳。
- (ハードカバー)1971年7月。ISBN 4-320-01072-8
- (縮刷版)1996年6月。ISBN 4-320-01513-4
- (追補版)2011年5月。ISBN 978-4-320-01965-2
- 一松信 『数のエッセイ』 筑摩書店〈ちくま学芸文庫〉、2007-01-10。ISBN 978-4-480-09041-6。
- 和田秀男 『数の世界 整数論への道』 岩波書店〈科学ライブラリー〉、1981-07-10。ISBN 4-00-005500-3。 - 前編は1次式の整数論、後編は2次式の整数論。
- 和田秀男 『コンピュータと素因子分解』 遊星社(発行)星雲社(発売)、1999-04(原著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
関連項目
- 完全数
- 巨大な素数の一覧
- ハノイの塔 - メルセンヌ素数 2127 − 1 を発見したリュカによって考案されたパズル。解に必要な最短手数とその二進数表記は密接な関係がある。
- フェルマー数
- メルセンヌ・ツイスタ - メルセンヌ素数を用いた擬似乱数発生アルゴリズム。
- メルセンヌ予想
- レピュニット
- GIMPS
外部リンク
- リュカテストによるメルセンヌ素数の発見法 (PDF)
- Weisstein, Eric W. “Mersenne number”. MathWorld(英語). Template:Cite webの呼び出しエラー:引数 accessdate は必須です。
- Weisstein, Eric W. “Mersenne prime”. MathWorld(英語). Template:Cite webの呼び出しエラー:引数 accessdate は必須です。
- Mersenne Primes: History, Theorems and Lists(英語)
- The Largest Known Primes(英語)
- GIMPS(英語)