友愛数

「完全数」と共に小説『博士の愛した数式』に登場する「友愛数」を求めるプログラムです。

友愛数(Amicable Numbers)とは、２つの異なる自然数の組(ペア)になっていて、自分自身を除いた約数の和が、もう片方の数と等しくなるような数を言います。「親和数」とも呼ばれているようです。

例えば、一番小さな友愛数の組は(220, 284)です。

220の自分自身を除いた約数の和は、1+2+4+5+10+11+20+22+44+55+110 = 284 で、
284の自分自身を除いた約数の和は、1+2+4+71+142 = 220 となります。

ちなみに、今までに見つかった友愛数の組は、すべて偶数同士または奇数同士の組だそうです。
ただ、すべてでそうなるのかは、未解決の問題のようです。

C#のコード

「友愛数」の組を求める何らかの式を使えば求められる、というわけではなさそうなので、このプログラムでは、約数の和を計算することで、友愛数を求めています。

AmicableNumbers.cs

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で公開したものを加筆・修正したものです。