2進数表現で見る完全数

1.完全数とは

完全数（かんぜんすう、英: perfect number）とは、自分自身が自分自身を除く正の約数の和に等しくなる自然数のことである。
Wikipedia

完全数は、 6(=1+2+3)､28(=1+2+4+7+14)､496(=1+2+4+8+16+31+62+124+248)...などがある。

2.2進数表現とは

普段使用している数字は10進数表現の数字(0,1,2,3,4,5,6,7,8,9)である。2進数表現では、数字は0,1のみを使用する。以下が10進数で1-20の数を2進数で表現したものになる。

10進数表現	2進数表現	10進数表現	2進数表現
1	1	11	1011
2	10	12	1100
3	11	13	1101
4	100	14	1110
5	101	15	1111
6	110	16	10000
7	111	17	10001
8	1000	18	10010
9	1001	19	10011
10	1010	20	10100

完全数をそれぞれ2進数表現すると以下のようになる。

10進数表現	2進数表現
6	110
28	11100
120	1111000
496	111110000

6を基準にすると、それぞれ1の塊に1が追加されて、0の塊に0が追加されている。
だが、120(自身以外の約数の和=1+2+3+4+5+6+8+10+12+15+20+24+30+40+60=240 )となるため、120は完全数ではない。

3.約数の2進数表現

6の約数の2進数表現は以下のようになる。

10進数表現	2進数表現
1	1
2	10
3	11
6	110

ここで、3 × 2は2進数で表すと、11 × 10 のようになる。2進数でも掛け算は10進数と同様にできるため、
11 × 10
= 110（11の後ろに0を増やす）

6（2進数表現で110）は0を除く、11の部分に注目すると、
11 = 1 × 11
11 = 11 × 1
のように分解できるため、6を2進数表現すると
110 = 1 × 110
110 = 11 * 10
になるため、上の表のような約数になる。

7(2進数表現で111)、15(2進数表現で1111)を同様に考えると、以下のようになる。
111 = 1 × 111
111 = 111 × 1

1111 = 1 × 1111
1111 = 11 × 101
1111 = 1111 × 1
そのため、28(2進数表現で11100)、120(2進数表現で1111000)の約数を2進数表現すると以下のようになる。

28(2進数表現で11100)の約数

10進数表現	2進数表現	10進数表現	2進数表現
1	1	28	11100
2	10	14	1110
4	100	7	111

120(2進数表現で1111000)の約数

10進数表現	2進数表現	10進数表現	2進数表現	10進数表現	2進数表現	10進数表現	2進数表現
1	1	120	1111000	3	11	40	101000
2	10	60	111100	6	110	20	10100
4	100	30	11110	12	1100	10	1010
8	1000	15	1111	24	11000	5	101

4.完全数約数の2進数表現での計算

では完全数の定義である自身を除く約数の足し算を2進数表現で見てみる。
6について考える。

10進数表現	2進数表現
1	1
2	10
3	11
6	110

$2^n$(nは自然数)の部分を足すと、11となる。
11 + 11
= 11 × 2(10進数表現) = 11 × 10 (2進数の場合、2倍するとき末尾に0を付ける)
= 110
になるため、2進数表現の6になっている。

次に28について考える。

10進数表現	2進数表現	10進数表現	2進数表現
1	1	28	11100
2	10	14	1110
4	100	7	111

$2^n$(nは自然数)の部分を足すと、1 + 10 + 100 = 111 となる。
1 + 10 + 100 + 111 + 1110
= 111 + 111 + 1110
= 1110 + 1110
= 11100
になるため、2進数表現の28になっている。

最後に、120について考える。

10進数表現	2進数表現	10進数表現	2進数表現	10進数表現	2進数表現	10進数表現	2進数表現
1	1	120	1111000	3	11	40	101000
2	10	60	111100	6	110	20	10100
4	100	30	11110	12	1100	10	1010
8	1000	15	1111	24	11000	5	101

1 + 10 + 100 + 1000 + 1111 + 11110 + 111100 + 11 +　...
= 1111 + 1111 + 11110 + 111100 + 11 +　...
= 11110 + 11110 + 111100 + 11 +　...
= 111100 + 111100 + 11 +　...
= 1111000 + 11 +　... (> 1111000)
となっているため、120は完全数ではない。

以上より、完全数になるには以下の条件がある。
①.2進数表現した場合、(1がN桁)(0がN-1桁)の形をしている。
(例：N=2の場合、110となる。)
②.Nが素数。⇔Nは1とNしか約数を持たない。
(例：N=4の場合、約数は、1,2,4となる。この時、2進数1111の約数を2で表現すると、1,11,101,1111となる。)

①の場合、
$2^n$(nは自然数)の部分を足すと、(1がN桁)となる。そのため、約数の和の計算は以下のようになる。
(1がN桁) + (1がN桁) + (1がN桁)0 + (1がN桁)00 + ... + (1がN桁)(0がN-2桁)
=(1がN桁)(0がN-1桁)

②の場合、Nが1とN以外の約数Mを持ってしまうと、約数の和の計算は以下のようになる。
(1がN桁) + (1がN桁) + (1がN桁)0 + (1がN桁)00 + ... + (1がN桁)(0がN-2桁) + (1がM桁) + ...
=(1がN桁)(0がN-1桁) + (1がM桁) + ...
となるため、完全数にはならない。

5.メルセンヌ素数と完全数

偶数の完全数には定理があります。

定理
$2^N-1$ が素数であるような正の整数 Nに対して，
$n = 2^{N-1}(2^N - 1)$は完全数である。

完全数の一覧と性質

$2^N-1$という形の数をメルセンヌ数といい，素数のメルセンヌ数をメルセンヌ素数といいます。

$2^N - 1$は2進数表現では1(0がN桁)から1を引くので、(1がN桁)となる。
100...0 - 1 = 11...1
$2^{N-1}$は2をN-1回かけることなので、2進数表現では$2^N - 1$の右に0をN-1回追加することである。
つまり、2進数表現では以下のようになる。

10進数表現	2進数表現
(2^N - 1)	(1がN桁)
$2^{N-1}$	(0がN-1桁)

4.完全数約数の2進数表現での計算でみていた通り、定理を満たしている場合、完全数である。