メルセンヌ数(Mersenne Number)と完全数(Perfect Number)

乱数生成によく用いられるアルゴリズムのメルセンヌ・ツイスタ法ではメルセンヌ数(Mersenne Number)という概念が用いられます。当記事ではWikipediaなどを参考にメルセンヌ数、メルセンヌ素数、完全数に関して簡単に取りまとめを行いました。

・メルセンヌツイスタ法
https://www.hello-statisticians.com/explain-terms-cat/mersenne_twister1.html

メルセンヌ数・メルセンヌ素数

定義

$$
\large
\begin{align}
M_n = 2^{n}-1, \quad n \in \mathbb{N}
\end{align}
$$

上記のように自然数$n$を用いて$M_n=2^{n}-1$のように表される数をメルセンヌ数という。メルセンヌ数は下記のように具体的に考えることができる。
$$
\large
\begin{align}
2^{1}-1 &= 1 \\
2^{2}-1 &= 3 \\
2^{3}-1 &= 7 \\
2^{4}-1 &= 15 \\
2^{5}-1 &= 31 \\
2^{6}-1 &= 63 \\
2^{7}-1 &= 127 \\
2^{8}-1 &= 255 \\
2^{9}-1 &= 511 \\
2^{10}-1 &= 1023 \\
2^{11}-1 &= 2047
& \vdots
\end{align}
$$

上記に基づいて$M_n$に素数が出てくる場合をメルセンヌ素数(Mersenne prime)という。$M_n$が素数である場合、$n$は素数であるが、逆の「$n$が素数 $\implies$ $M_n$が素数」は成立しない。具体的には下記のように考えられる。

$n=2, M_n=3$	$n$と$M_n$のどちらも素数
$n=3, M_n=7$	$n$と$M_n$のどちらも素数
$n=5, M_n=31$	$n$と$M_n$のどちらも素数
$n=7, M_n=127$	$n$と$M_n$のどちらも素数
$n=11, M_n=2047$	$n$は素数だが$M_n=2047=23 \times 89$

判定法

桁が小さい数に関しては計算した$M_n$を割り切る数があるかを探せば良いが、「リュカ-レーマー・テスト」を用いることなどによって効率化できる。

メルセンヌ素数の一覧

「Wikipedia：メルセンヌ素数の一覧」が詳しいが、$51$個発見されている。

$n \leq 10,000$では$n=2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941$が挙げられる。

完全数

メルセンヌ数$M_n = 2^{n}-1$が素数であるとき、$2^{n-1}(2^{n}-1)$は完全数である。完全数は「正の約数の和に等しい自然数」を定めた数である。前節で確認したメルセンヌ素数$M_n = 2^{n}-1$に関して以下、$2^{n-1}(2^{n}-1)$が完全数であることを確かめる。

$n=2, M_n=3$

$$
\large
\begin{align}
2^{n-1}(2^{n}-1) &= 2^{2-1}(2^{2}-1) \\
&= 2 \times 3 = 6 \\
1 + 2 + 3 &= 6
\end{align}
$$

$n=3, M_n=7$

$$
\large
\begin{align}
2^{n-1}(2^{n}-1) &= 2^{3-1}(2^{3}-1) \\
&= 2^2 \times 7 = 28 \\
1 + 2 + 4 + 7 + 14 &= 28
\end{align}
$$

参考

・Wikipedia：メルセンヌ数
・Wikipedia：完全数
・Wikipedia：メルセンヌ・ツイスタ