完全数入門! 数の面白シリーズ!

今回は「完全数」という数についてお話をしたいと思います。
完全数の定義からプログラムで完全数を判定するものも作ってみたいと思います。

完全数とは

完全数 (Perfect Number)

自身以外の正の約数の和が、ちょうど自分自身に等しい数のこと

完全数は「万物は数なり」と考えたピタゴラスが名付けた数になります。
完全数は例えば、6,28,496,8128などがあります。

ここでは6と496が完全数であることを確かめてみましょう!
(1) 6が完全数であること

6の自分自身を除く正の約数は1,2,3です。
これらの和をとると1+2+3=6なので、完全数になります。

(2)496が完全数であること

496の自分自身を除く正の約数は1,2,4,8,16,31,62,124,248です。
これらの和をとると1+2+4+8+16+31+62+124+248=496なので、完全数になります。

完全数の性質

紀元前3世紀、ユークリッドは完全数について次の性質を発見しました。

命題1

$2^n-1$ が素数ならば、 $2^{n-1}(2^n-1)$ は完全数である。

ちなみに、 $2^n-1$ で表される数をメルセンヌ数といい、それが素数である場合はメルセンヌ素数といいます。

例えば、次のように完全数を計算することができます。
(1) $n=2$ の時
$2^2-1=3$ なので命題1が使えて、
$2^1(2^2-1) = 2 \times 3 = 6$ は完全数。

(2) $n=7$ の時
$2^7-1 = 128-1=127$ は素数なので命題1が使えて、
$2^6 (2^7-1) = 64 \times 127 = 8128$ は完全数。

命題1の証明

$2^n-1$ が素数なので、 $2^{n-1}(2^n-1)$ の自分自身を除く約数は $1,2,\cdots,2^{n-1},(2^n-1),2(2^n-1),\cdots,2^{n-2}(2^n-1)$ になります。

これらの和を取ると
$1+2+\cdots+2^{n-1} + (2^n-1) + 2(2^n-1) \cdots + 2^{n-2}(2^n-1) = (1+2+\cdots+2^{n-1}) + (1+2+\cdots+2^{n-2}) (2^n-1)$ となります。

式の中にある $1+2+\cdots+2^{n-1}$ と $1+2+\cdots+2^{n-2}$ は初項、公比2の等比数列の和なので、上の式の計算結果は以下になります。

$(2^n-1) + (2^{n-1}-1)(2^n-1) = (2^n-1)(1+2^{n-1}-1) = 2^{n-1}(2^n-1)$ となります。

よって、自分自身を除く約数の総和が自分自身と等しくなったので完全数であることが証明できました。