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
1
Help us understand the problem. What is going on with this article?
@gushwell

C#:友愛数を求める

More than 1 year has passed since last update.

友愛数

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

友愛数(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#のコード

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

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

1
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
1
Help us understand the problem. What is going on with this article?