友愛数
「完全数」と共に小説『博士の愛した数式』に登場する「友愛数」を求めるプログラムです。
友愛数(Amicable Numbers)とは、2つの異なる自然数の組(ペア)になっていて、自分自身を除いた約数の和が、もう片方の数と等しくなるような数を言います。「親和数」とも呼ばれているようです。
例えば、一番小さな友愛数の組は(220, 284)です。
220の自分自身を除いた約数の和は、1+2+4+5+10+11+20+22+44+55+110 = 284 で、
284の自分自身を除いた約数の和は、1+2+4+71+142 = 220 となります。
ちなみに、今までに見つかった友愛数の組は、すべて偶数同士または奇数同士の組だそうです。
ただ、すべてでそうなるのかは、未解決の問題のようです。
C#のコード
「友愛数」の組を求める何らかの式を使えば求められる、というわけではなさそうなので、このプログラムでは、約数の和を計算することで、友愛数を求めています。
class Program {
public static void Main(string[] args) {
AmicableNumbers an = new AmicableNumbers();
var numbers = an.GetNumbers()
.Take(20);
foreach (var pair in numbers) {
Console.WriteLine("({0} , {1})", pair.Value1, pair.Value2);
}
}
}
public class Pair {
public long Value1 { get; set; }
public long Value2 { get; set; }
}
public class AmicableNumbers {
// long の範囲で、友愛数を列挙する
public IEnumerable<Pair> GetNumbers() {
for (long i = 2; i < long.MaxValue; i++) {
long x = Divisors(i).Sum();
if (i >= x)
continue;
long y = Divisors(x).Sum();
if (i == y)
yield return new Pair { Value1 = i, Value2 = x };
}
}
// 真の約数を求める n は、2以上の整数
private IEnumerable<long> Divisors(long n) {
yield return 1;
long m = (long)Math.Sqrt(n);
if (m * m == n) {
yield return m;
m--;
}
for (long i = 2; i <= m; i++) {
if (n % i == 0) {
yield return i;
yield return n / i;
}
}
}
}
クラス AmicableNumbersが、友愛数を求めるクラスで、GetNumbersメソッドで、友愛数の組を順に取り出せるようにしています。「いくつまで」という制限は設けていないので、GetNumbersメソッドを呼び出す側で、Take(n)とかして、組を取りだす個数を指定します。もちろん取り出せるのは、longで表せる数の範囲です。
ソースコードは、GitHubで公開しています。
実行結果
(220 , 284)
(1184 , 1210)
(2620 , 2924)
(5020 , 5564)
(6232 , 6368)
(10744 , 10856)
(12285 , 14595)
(17296 , 18416)
(63020 , 76084)
(66928 , 66992)
(67095 , 71145)
(69615 , 87633)
(79750 , 88730)
(100485 , 124155)
(122265 , 139815)
(122368 , 123152)
(141664 , 153176)
(142310 , 168730)
(171856 , 176336)
(176272 , 180848)
この記事は、Gushwell's C# Programming Pageで公開したものを加筆・修正したものです。