絶対にメルセンヌ素数が好きになる話

2017.01.25
数学

素数は数字の中でもかっこよくて特別だけれども、その中でも際立ってかっこいい素数がある。メルセンヌ素数だ。
今日は魅力いっぱいのメルセンヌ素数について語る。

1. メルセンヌ素数とは
- 1.1. 2の累乗
- 1.2. 二進数表記
2. 素数発見の歴史
- 2.1. 最大の素数
- 2.2. これからの展望
3. 完全数とメルセンヌ素数
- 3.1. 完全数とは
- 3.2. メルセンヌ素数との関係
4. 最後に

メルセンヌ素数とは

メルセンヌ数というのは\(2^n – 1\)で表される自然数のことだ。
メルセンヌ数の中でも、特にそれが素数のものをメルセンヌ素数と呼ぶ。
例えば \(2^2 – 1=3, 2^3 – 1=7, 2^5 – 1=31\) はそれぞれ素数となっているのでメルセンヌ素数である。

2の累乗

メルセンヌ数の大きさをイメージするために、\(2^n\) を計算してみるのが良い。
\(n=1, 2, 3, 4, 5, 6,…\)という風に代入していくと、2, 4, 8, 16, 32, 64, 128, 256, 512, 1024,…となっていく。このあたりの数字は見覚えがあるのではないだろうか。そして\(2^{10} = 1024\)というのは覚えておくと便利なこともある。つまり\(2^{10} ≒ 10^3\)が頭に入っていると良い。

\(n=20\)の時、\(2^n=1048576\)となる。
大きい数だ。
\(2^n\) グラフは下のようになっていて、すごいスピードで増加していくのだ。

二進数表記

二進数というのは0と1のみが存在する世界の数である。現在一般的に用いられているのは0から9の10個の数字を使った10進数表記である。
ただ、コンピューターの世界では二進数が多く用いられることもあり、二進数は馴染み深い人もいるかもしれない。
例えば二進数で111というのは10進数の7に対応している。
また、1101は13、10001は17といった具合である。

10進数では下から、一の位、十の位、百の位、… と数えるが、
二進数では下から、一の位、二の位、四の位、八の位、… と数える。

そしてメルセンヌ数だが、二進数表記をすると111111111111111のように、全ての位が1になる。
そして\(2^n – 1\) がメルセンヌ数であったが、二進数表記をした時の1の数は\(n\)となる。

これは二進数の世界では \(1111111111+1=10000000000\) となることからわかる。\(2^n\)は1000…0000のように、1のあとに0が\(n\)個並ぶ数字で表されるのである。

素数発見の歴史

「大きい数を言った方が勝ち」
そんな勝負を、小学生の頃の通学路でしたことを覚えている。
「9999億9999万9999」や「無量大数」など大きい数を言い合うが、結局「お前の数字に1を足した数字」と片方がいうと「その数字に1を足した数字」という風にもう片方が言って、この勝負は勝ちか負けかも分からない状態によく陥っていた。

大きい数はいくらでも見つかる。
大きい数、というのは人々を魅了するが、簡単に見つかる数に人々は魅了されない。

どれだけ大きな素数を知っているのか。
これはどうでもいいことに思えるかもしれないが、人類が挑戦してきた終わりなき夢でもある。
そして、人類が知り得た最大の素数の歴史というのはメルセンヌ素数の発見の歴史でもあるのだ。

最大の素数

2016年1月25日現在、人類が知っている最大の素数は \(2^{74207281} – 1\) である。
これはメルセンヌ素数だ。

（2018年1月6日追記）
2017年12月26日に、50番目のメルセンヌ素数が発見された。\(2^{77232917} – 1\)である。
（追記終了）

素数の判定法にはさまざなものがあり、確率的に素数かどうかを判定するものもある。
確率的に素数かどうかを判定するというのは、「確信はないけど多分素数」という数を見つけるということである。
巨大な素数になると、コンピューターを使ったとしても、その数が素数かどうかの判断に時間がかかるので、このように計算時間を短くして「多分素数」という数を見つけるのである。

またメルセンヌ数の素数判定法にはリュカ-レーマー・テストというものが考案されており、メルセンヌ数でない数の素数判定よりも早く素数であるかどうかを判定できる。

リュカ-レーマー・テストでは、随所でメルセンヌ数で割り算をするという行為が行われるのだが、コンピューターで割り算をするとなると計算時間がかかるところを、シフト演算と足し算という計算時間がかからない操作のみで割り算と同等の操作をすることができるので早く素数判定ができるようになっている。

先ほど述べたメルセンヌ数の二進数表記が、二進数を扱うコンピューターの世界で威力を発揮していると言えよう。

以上が、大きな素数の発見とメルセンヌ素数が関連している理由である。

これからの展望

これから最大の素数の記録が塗り替わるとすれば、
・現在の手法のまま新たなメルセンヌ素数が見つかる
ということが一番期待されるだろう。また、
・メルセンヌ素数に関するもっと効率の良い方法が見つかる。
ということも考えられる。

ただ、いつまでもメルセンヌ素数が最大の素数であり続けるかどうかは分からない。
・違う形式の素数で最大の素数が見つかる
こんなことが起こったら、それは衝撃的だろう。
これは別にあり得ないことではない。むしろ大いに起こりうるのではないだろうか。

メルセンヌ素数という形にとらわれずに最大の素数を見つけようとすることは、険しい道のりになるかもしれないが、もしも発見することができたらそれは革命的なことだ。

完全数とメルセンヌ素数

完全数とメルセンヌ素数には興味深い関係性がある。
そしてこれこそが、メルセンヌ素数を美しいものにしている最大の要因ではないかと僕は思っている。

完全数とは

自分自身を除く約数の総和が自分自身であるときに、その数を完全数という。
最小の完全数は6である。6の約数は1, 2, 3, 6 となっているのだが、自分自身を除いた約数1, 2, 3 の総和は6である。
自分自身を除く約数の総和というのは、自分よりも大きくなったり、小さくなったりして、ちょうど自分自身になるのは珍しい。
その意味でそのような数は完全であると呼ばれるのだ。

6の次に現れる完全数は28、その次は496である。