［ 内容 ］
１と自分自身以外に約数がない正の整数。
たったそれだけの素数の性質から、整数論の世界をひもといていく。
ガウス、フェルマー、オイラー、メルセンヌなど、数学の天才たちをとりこにした素数の魅力とは。
［ 目次 ］
第１章 整数の生い立ち
第２章 整数の周辺
第３章 最大公約数
第４章 素数
第５章 整数の合同
第６章 いろいろな方程式
第７章 整数論で使われる関数
第８章 素数のいろいろ
第９章 フェルマーの小定理・原始根
［ 問題提起 ］
この完全数を出題しなかったのはある意味当然とも言えます。
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
今回はプログラマーにとってもうれしい問題。
問題:1から1000までの番号とスイッチがついた電球があります。まず、1の倍数の電球のスイッチを押し、次に2の倍数のスイッチを押し....これを1000回行った後、点灯している電球の数はいくつあるでしょう？ただし、最初の状態では電球は消灯状態です。
この問題は「1から1000までの数において、1とそれ自身を含む因数の数が奇数のものはいくつあるでしょう？」という問題に還元される。
以下に↓つづく。
http://blogs.yahoo.co.jp/bax36410/60728206.html
［ 読了した日 ］
２０１０年１月１３日