メルセンヌ数の表及びJavaScriptで実装した簡単なリュカテスト。
2005/05/20
メルセンヌ数(メルセンヌ素数)とは2n-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は2216091で、とてもじゃないが今の計算能力では不可。
21257787まで計算。(2009/12/25)
2005/05/20
メルセンヌ数と関係の深い完全数。 まずは完全数について。 完全数とは自身を除く約数の総和が自身である数。 例えば28。 約数を並べてみると[1 2 4 7 14]で、これらを全て足すと1+2+4+7+14=28となり28に戻る。 逆に、約数の和が自分以下のものを不足数、自分以上のものを過剰数という。
10000以下の自然数を根こそぎチェックしたところ、
不足数:7507 過剰数:2488 完全数4
となり不足数が圧倒的に多い。
メルセンヌ数との関連性だが、ユークリッドとオイラーによって、2n-1が素数なら偶数の完全数は(2n-1)(2n-1)であることが証明されている。 従ってメルセンヌ素数を発見できれば完全数も発見したことになる。 現在42個の完全数(メルセンヌ数)が知られている。 n=13程度なら電卓等で計算できるので試してみるのも面白い。 その他完全数の性質としては
などが挙げられる。
2005/11/01
メルセンヌ数の桁数は現在発見されている最大のもので7816230桁ある。これを正攻法で素数判定するのはスーパーコンピュータでも骨の折れる作業になる。メルセンヌ数の場合、P問題である極めて単純・高速な素数判定法がある。この方法をリュカ・テストと呼ぶ。1891年にリュカによって発見された。
リュカ・テストはいたって簡単にできる。初期値はa1=4。a1 2-2を計算し判定したいメルセンヌ数で割った余りをa2とおく。そしたら今度はa2 2-2をメルセンヌ数で割った余りをa3とおく。これを指数の数だけ続け、a指数-1のときに割り切れて余りが0になればその指数は素数である。
例えば217-1=131071のときは次のようになる。 ※A≡B(mod C)はAをCで割った余りがBになることを示す。
この計算結果は以下のプログラムによって求めたものだ。好きなnについてリュカ・テストを実行できる。なお、JavaScriptの精度限界を超える計算には巨大数演算Ver.0.3alpha9ライブラリを用いている。