メルセンヌ数・完全数

メルセンヌ数

2005/05/20

メルセンヌ数(メルセンヌ素数)とは2ⁿ-1の形で表すことのできる素数のことだ。 Wikipediaで調べると現在43種類が発見されているようだ。今回これらの数を可能な限り計算してみた。

メルセンヌ数リスト

No	n	桁数
1	2	1
2	3	1
3	5	2
4	7	3
5	13	4
6	17	6
7	19	6
8	31	10
9	61	19
10	89	27
11	107	33
12	127	39
13	521	157
14	607	183
15	1,279	386
16	2,203	664
17	2,281	687
18	3,217	969
19	4,253	1,281
20	4,423	1,332
21	9,689	2,917
22	9,941	2,993
23	11,213	3,376
24	19,937	6,002
25	21,701	6,533
26	23,209	6,987
27	44,497	13,395
28	86,243	25,962
29	110,503	33,265
30	132,049	39,751
31	216,091	65,050
32	756,839	227,832
33	859,433	258,716
34	1,257,787	378,632
35	1,398,269	420,921
36	2,976,221	895,932
37	3,021,377	909,526
38	6,972,593	2,098,960
39?	13,466,917	4,053,946
40?	20,996,011	6,320,430
41?	24,036,583	7,235,733
42?	25,964,951	7,816,230
43?	30,402,457	9,152,052

1〜30までは計算。31は2²¹⁶⁰⁹¹で、とてもじゃないが今の計算能力では不可。

2^1257787まで計算。(2009/12/25)

• 2²-1
• 2³-1
• 2⁵-1
• 2⁷-1
• 2¹³-1
• 2¹⁷-1
• 2¹⁹-1
• 2³¹-1
• 2⁶¹-1
• 2⁸⁹-1
• 2¹⁰⁷-1
• 2¹²⁷-1
• 2⁵²¹-1
• 2⁶⁰⁷-1
• 2¹²⁷⁹-1
• 2²²⁰³-1
• 2²²⁸¹-1
• 2³²¹⁷-1
• 2⁴²⁵³-1
• 2⁴⁴²³-1
• 2⁹⁶⁸⁹-1
• 2⁹⁹⁴¹-1
• 2¹¹²¹³-1
• 2¹⁹⁹³⁷-1
• 2²¹⁷⁰¹-1
• 2²³²⁰⁹-1
• 2⁴⁴⁴⁹⁷-1
• 2⁸⁶²⁴³-1
• 2¹¹⁰⁵⁰³-1
• 2¹³²⁰⁴⁹-1
• 2²¹⁶⁰⁹¹-1
• 2⁷⁵⁶⁸³⁹-1
• 2⁸⁵⁹⁴³³-1
• 2^1257787-1

完全数

2005/05/20

メルセンヌ数と関係の深い完全数。 まずは完全数について。 完全数とは自身を除く約数の総和が自身である数。 例えば28。 約数を並べてみると[1　2　4　7　14]で、これらを全て足すと1+2+4+7+14=28となり28に戻る。 逆に、約数の和が自分以下のものを不足数、自分以上のものを過剰数という。

10000以下の自然数を根こそぎチェックしたところ、

不足数:7507
過剰数:2488
完全数4

となり不足数が圧倒的に多い。

• 出力結果(266KB)
• 出力に使ったJavaScript

メルセンヌ数との関連性だが、ユークリッドとオイラーによって、2ⁿ-1が素数なら偶数の完全数は(2^n-1)(2ⁿ-1)であることが証明されている。 従ってメルセンヌ素数を発見できれば完全数も発見したことになる。 現在42個の完全数(メルセンヌ数)が知られている。 n=13程度なら電卓等で計算できるので試してみるのも面白い。 その他完全数の性質としては

• 2進表記にすると1と0がきれいに分かれる
• 三角数
• 六角数
• 9で割ると1余る(6以外)
• 1の位が必ず6か8
• 逆数和が2

などが挙げられる。

リュカ・テスト

2005/11/01

メルセンヌ数の桁数は現在発見されている最大のもので7816230桁ある。これを正攻法で素数判定するのはスーパーコンピュータでも骨の折れる作業になる。メルセンヌ数の場合、P問題である極めて単純・高速な素数判定法がある。この方法をリュカ・テストと呼ぶ。1891年にリュカによって発見された。

リュカ・テストはいたって簡単にできる。初期値はa₁=4。a₁ ²-2を計算し判定したいメルセンヌ数で割った余りをa₂とおく。そしたら今度はa₂ ²-2をメルセンヌ数で割った余りをa₃とおく。これを指数の数だけ続け、a_指数-1のときに割り切れて余りが0になればその指数は素数である。

例えば2¹⁷-1=131071のときは次のようになる。 ※A≡B(mod C)はAをCで割った余りがBになることを示す。

1. a1 = 4
2. a2 = 4^2-2≡ 14(mod 2^17-1)
3. a3 = 14^2-2≡ 194(mod 2^17-1)
4. a4 = 194^2-2≡ 37634(mod 2^17-1)
5. a5 = 37634^2-2≡ 95799(mod 2^17-1)
6. a6 = 95799^2-2≡ 119121(mod 2^17-1)
7. a7 = 119121^2-2≡ 66179(mod 2^17-1)
8. a8 = 66179^2-2≡ 53645(mod 2^17-1)
9. a9 = 53645^2-2≡ 122218(mod 2^17-1)
10. a10 = 122218^2-2≡ 126220(mod 2^17-1)
11. a11 = 126220^2-2≡ 70490(mod 2^17-1)
12. a12 = 70490^2-2≡ 69559(mod 2^17-1)
13. a13 = 69559^2-2≡ 99585(mod 2^17-1)
14. a14 = 99585^2-2≡ 78221(mod 2^17-1)
15. a15 = 78221^2-2≡ 130559(mod 2^17-1)
16. a16 = 130559^2-2≡ 0(mod 2^17-1)

この計算結果は以下のプログラムによって求めたものだ。好きなnについてリュカ・テストを実行できる。なお、JavaScriptの精度限界を超える計算には巨大数演算Ver.0.3alpha9ライブラリを用いている。

リュカ・テスト実行プログラム(JavaScript)

判定する指数n[2ⁿ-1]

n =

Debug

　

OutPut

Progress