Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
0
Help us understand the problem. What is going on with this article?
@gushwell

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

0
Help us understand the problem. What is going on with this article?
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
gushwell
株式会社ジード / Microsoft MVP for Developer Technologies 2005-2020 / 著書『実戦で役立つ C#プログラミングのイディオム/定石&パターン』『新・標準プログラマーズライブラリ なるほどなっとく C#入門』『C#プログラミング入門―オブジェクト指向のプログラミング手法を基礎から解説』

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
0
Help us understand the problem. What is going on with this article?