完全数

| コメント(2) | トラックバック(0)

完全数というのは、自身の約数の和と、自身が等しいという自然数で、ギリシャのユークリッドの頃から興味が持たれていた。

例えば、6 = 1+2+3というのは分かりやすい例である。手計算で探すのは大変なので、Perlで、ナイーブに、完全数を探すプログラムを書くと次のとおりある。

# プログラムの始まり
for ( $i = 2; $i < 100000000; $i++ )   {
CompN($i);
}

sub CompN  {

my $n = shift;
my $i = 1;
my $s = 0;
my $z = 0;
my @nums = ();


while ( $i <= $n/2 )  {

 if (($n % $i) == 0 )   {
   $s += $i;
   push @nums, $i;
 }
 $i++;
}

 if ( $s == $n )  {
  printf "%d = ",$n;

  foreach $x (@nums)   {
   if ( $z == 0 )   {
     printf "%d",$x;
   } else           {
     printf "+%d",$x;
   }
 $z = 1;
 }
 printf "\n";
 }
 return 0;
}
# プログラムの終わり

これを走らせると、

6 = 1+2+3
28 = 1+2+4+7+14
496 = 1+2+4+8+16+31+62+124+248
8128 = 1+2+4+8+16+32+64+127+254+508+1016+2032+4064

までは、あっという間に出る。ところが、そこからが長い。ずっと後の方になって、
33550336 = 1+2+4+8+16+32+64+128+256+512+1024+2048+4096+8191+16382+32764+65528+131056

+262112+524224+1048448+2096896+4193792+8387584+16775168
がやっと求まる。

実はユークリッド自身は、2**n-1が素数なら、2**($n-1)*(2**$n - 1)は完全数である、という証明を与えていた。ここで、2**nは、2のn乗を意味する。

ところが、これだけでは、完全数を枚挙して求めるのにあまり役に立たない。2**n-1の式のnに数字を入れて素数かどうか確認して完全数が求まったとしても、そうでない完全数があるかもしれないからである。

そこで完全数に関する、偉大なるオイラーの定理があって、偶数の完全数は、2**n-1が素数である場合の、2**($n-1)*(2**$n - 1)という形に限る、というものである。

ところで、2**n-1の形の素数は、メルセンヌ素数と呼ばれる。メルセンヌは、2**n-1が素数になるのは、n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257の場合だけ、と予想したが、n = 67, 257のときは素数にならないことが、後にコンピュータ計算で確かめられた。上記の6, 28, 496, 8128, 33550336はまさに、n = 2, 3, 5, 7, 13に対応する。さらに、33550336の次の完全数は、33550336のほぼ256倍の数であることも分かる。

そこで完全数の未解決問題として次がある。
(1) 完全数は、無限に存在するか。これは、メルセンヌ素数が無限に存在するか、とも等価であって、一般には正しいだろうと信じられているが、証明は進んでいない。
(2) 奇数の完全数は、存在するか。これも意外にも、全く分かっていない。もし存在するとしても、それは、300桁以上の自然数だろうと予想されている程度である。

トラックバック(0)

トラックバックURL: http://commutative.world.coocan.jp/mt/mt-tb.cgi/1415

コメント(2)

「奇数の完全数であれば、その数は2以外の素数Pと奇数の平方数Sとの積PSである。」ということは証明されていますね。あと少しというところでしょうか。
http://web2.incl.ne.jp/yaoki/kanzensu.htm

ISSEIさん

>「奇数の完全数であれば、その数は2以外の素数Pと奇数の平方数Sとの積PSである。」

そんな定理があるのですか。でも、ここからが長いのです。フェルマーの定理、然り

コメントする

このブログ記事について

このページは、あやたろうが2009年8月16日 08:42に書いたブログ記事です。

ひとつ前のブログ記事は「シュメール文明」です。

次のブログ記事は「仕事と趣味」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。