Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

婚約数(Betrothed Numbers)とは

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

例えば、一番小さな友愛数の組は(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で公開したものを加筆・修正したものです。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした