この完全数を出題しなかったのはある意味当然とも言えます。

cover
素数入門
芹沢 正三
rubyco（るびこ）の日記 - 10000までの完全数を列挙せよ
エラトステネスの篩もよいけれど、別の問題もやろうよ。ということで「完全数」です。

なんとこの完全数、32bit整数を全部しらみつぶしに探しても５つしかみつからないんですから。64bitまで足を伸ばしても８つ。しかしオイラーがすでに見つけています。

なんでそう言い切れるかというと、

  • 今まで見つかった完全数は、全て2Mn-1(2Mn-1)という形をしている。ここでMnはn番目のメルセンヌ素数。
  • 偶数の完全数は、すべて上記の形をしていることをオイラーがすでに発見している。
  • 奇数の完全数はまだ見つかっていない。が、10300より大きいことは判明している。

というわけで、電脳で完全数探しというのは、奇数完全数を見つけるか、メルセンヌ素数を見つけるかのどちらかに還元されてしまうわけです。

なお、このオイラーの定理の証明は高校生程度の数学で解けます。私は13歳だか14歳だかの頃にそれを見つけて小躍りしたことを覚えています。

そんなわけなので、今のところ単なるTable Lookupが最も「エレガント」ということになってしまいます。犠牲者を増やさないために、最後にn番目の完全数を表示するスクリプトを添付しておきます。

この手の問題だと、偽素数とか双子素数とかを判定する問題なんかが手頃そうです。

上記の「素数入門」は、まさにこの手の問題が好きな人にはこたえられない一冊。初等整数論のいい教科書にもなっています。例題の全てに回答が付いているのも新書としては良心的。千円をちょっと超えるのが難ですが、お薦めの一冊です。

Dan the Carmichael Blogger

use strict;
use warnings;
use bignum;

my @mersenne =  map { chomp; $_ } <DATA>;

sub mersenne_prime{
    my $n = shift;
    return 2**$mersenne[$n-1]-1;
}

sub perfect_number{
    my $m = mersenne_prime(shift);
    return ($m + 1)/2 * $m;
}

my $n = shift || 1;
print perfect_number($n), "\n";
__DATA__
2
3
5
7
13
17
19
31
61
89
107
127
521
607
1_279
2_203
2_281
3_217
4_253
4_423
9_689
9_941
11_213
19_937
21_701
23_209
44_497
86_243
110_503
132_049
216_091
756_839
859_433
1_257_787
1_398_269
2_976_221
3_021_377
6_972_593