C#:婚約数(準友愛数)を求める

婚約数(Betrothed Numbers)とは

婚約数(Betrothed Numbers)とは、２つの異なる自然数の組(ペア)になっていて、１と自分自身を除いた約数の和が、もう片方の数と等しくなるような数を言います。
「準友愛数」とも呼ばれているようです。友愛数の定義ととても良く似ていますからね。

例えば、一番小さな友愛数の組は(48,75)で、
48 → 2 + 3 + 4 + 6 + 8 + 12 + 16 + 24 = 75
75 → 3 + 5 + 15 + 25 = 48
となります。

C#のコード

以下、作成したC#のプログラムです。最初の30個のペアを求めています。

BetrothedNumber.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace Gushwell.Etude {
    class Program {
        static void Main(string[] args) {
            var numbers = BetrothedNumbers.GetNumbers().Take(20);
            foreach (var p in numbers)
                Console.WriteLine(p);
        }
    }

    public class Pair {
        public long Value1 { get; set; }
        public long Value2 { get; set; }
        public override string ToString() {
            return string.Format("({0}, {1})", Value1, Value2);
        }
    }
    public class BetrothedNumbers {
        public static IEnumerable<Pair> GetNumbers() {
            for (long i = 1; 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 };
            }
        }

        public static IEnumerable<long> Divisors(long n) {
            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;
                }
            }
        }
    }

}

プログラムコードは、友愛数を求めるプログラムとほとんど同じです。

このプログラムでは30個のペアを求めていますが、 40個のペアを求めようとすると、結構時間がかかります。
速くするにはさらなる工夫が必要ですが、思いつきません...

ソースコードは、GitHubで公開しています。

実行結果

(48, 75)
(140, 195)
(1050, 1925)
(1575, 1648)
(2024, 2295)
(5775, 6128)
(8892, 16587)
(9504, 20735)
(62744, 75495)
(186615, 206504)
(196664, 219975)
(199760, 309135)
(266000, 507759)
(312620, 549219)
(526575, 544784)
(573560, 817479)
(587460, 1057595)
(1000824, 1902215)
(1081184, 1331967)
(1139144, 1159095)

---

この記事は、Gushwell's C# Programming Pageで公開したものを加筆・修正したものです。