完全数とは
小説「博士の愛した数式」で一般の人にも有名になった「完全数」ですが、その完全数を求めるプログラムです。
完全数とは、その数自身を除く約数の和が、その数自身と等しい自然数のことです。
例えば、28 の約数は、1,2,4,7,14ですが、この合計は、1+2+4+7+14 = 28 となりますので、28は完全数ということになります。
どうやって解くか
この問題を普通にプログラミングすると、約数を求め、その和がそれ自身の数と等しいかどうかを調べてゆくことになります。しかしこのやり方だと小さいほうから最初の４つまではすぐに求まりますが、５つ目、6つ目の完全数を求めようとすると、答えが出るまでかなりの時間待たされることになります。
そのためこのプログラムでは、
「完全数はメルセンヌ素数から導き出される」
という性質を利用することにしました。
2^n-1が素数(メルセンヌ素数)ならば、偶数の完全数は、2^(n-1)・(2^n-1) で求められることが証明されているそうです。
奇数の完全数はまだ発見されていません。奇数の完全数が存在しないことはまだ証明がされていないそうです。
C#のコード
public class PerfectNumber {
public static IEnumerable<long> Take(int maxcount) {
int count = 0;
long n = 2;
while (count < maxcount) {
long mp = (long)Math.Pow(2, n) - 1;
if (PrimeNumber.IsPrime(mp)) {
long pn = (long)(Math.Pow(2, n - 1) * mp);
count++;
yield return pn;
}
n++;
}
}
}
PrimeNumber.IsPrime()は、「ミラー・ラビン素数判定法」による素数判定メソッドで示したメソッドをそのまま利用しています。
このクラスを使い、完全数を小さい順から８つ求めてみます。
public static void Main(string[] args) {
var q = PerfectNumber.Take(8);
foreach (var n in q) {
Console.WriteLine(n);
}
}
実行結果
結果です。
6
28
496
8128
33550336
8589869056
137438691328
2305843008139952128
8番目までの完全数ならば、すぐに求まります。
しかし、9番目の完全数は、2658455991569831744654692615953842176 なので、long型では無理みたいです。
ところで、1の位が6か8なのは、単なる偶然なんでしょうか？
Webで調べたところ、見つかっている完全数の1の位はどれも、6か8みたいです。面白いですね。
この記事は、Gushwell's C# Programming Pageで公開したものを加筆・修正したものです。