Problem71 順序分数

問題

nとdを正の整数として, 分数 n/d を考えよう.
n<d かつ HCF(n,d) = 1のとき、真既約分数と呼ぶ.

d <= 8 について真既約分数を大きさ順に並べると, 以下を得る:
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2,
4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

3/7のすぐ左の分数は2/5である.
d <= 100万について真既約分数を大きさ順に並べたとき,
3/7のすぐ左の分数の分子を求めよ.

ソース

using System;

class Program
{
    //const int MaxD = 8;
    const int MaxD = 1000000;

    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();

        int AnswerBunsi = 0;
        int AnswerBunbo = 1;

        for (int D = 1; D <= MaxD; D++) {
            for (int N = DeriveMaxSeisuuKai(D); N >= 1; N--) {
                //分子と分母が互いに素なら既約分数
                if (DeriveGCD(D, N) == 1) {
                    //    AnswerBunsi/AnswerBunbo < N/D
                    // ⇔ AnswerBunsi*D < AnswerBunbo*N
                    ulong wkProd1 = (ulong)AnswerBunsi * (ulong)D;
                    ulong wkProd2 = (ulong)AnswerBunbo * (ulong)N;
                    if (wkProd1 < wkProd2) {
                        Console.WriteLine("解候補{0}/{1}を発見。経過時間={2}",
                            N, D, sw.Elapsed);
                        AnswerBunsi = N;
                        AnswerBunbo = D;
                    }
                    break;
                }
            }
        }
    }

    //分母を引数として、不等式 分子/分母 < 3/7 の最大の整数解を求める
    static int DeriveMaxSeisuuKai(int pBunbo)
    {
        bool NeedKurisage = ((3 * pBunbo) % 7 == 0);
        int WillReturn = 3 * pBunbo / 7;
        return (NeedKurisage ? WillReturn - 1 : WillReturn);
    }

    //ユークリッドの互除法で2数の最大公約数を求める
    static int DeriveGCD(int pVal1, int pVal2)
    {
        int WarareruKazu = Math.Max(pVal1, pVal2);
        int WaruKazu = Math.Min(pVal1, pVal2);

        while (true) {
            int Amari = WarareruKazu % WaruKazu;
            if (Amari == 0) return WaruKazu;
            WarareruKazu = WaruKazu;
            WaruKazu = Amari;
        }
    }
}

実行結果

省略
解候補428531/999906を発見。経過時間=00:00:10.7868586
解候補428534/999913を発見。経過時間=00:00:10.7868949
解候補428537/999920を発見。経過時間=00:00:10.7869312
解候補428540/999927を発見。経過時間=00:00:10.7869678
解候補428543/999934を発見。経過時間=00:00:10.7870050
解候補428546/999941を発見。経過時間=00:00:10.7870413
解候補428549/999948を発見。経過時間=00:00:10.7870776
解候補428552/999955を発見。経過時間=00:00:10.7871290
解候補428555/999962を発見。経過時間=00:00:10.7871659
解候補428558/999969を発見。経過時間=00:00:10.7872020
解候補428561/999976を発見。経過時間=00:00:10.7872391
解候補428564/999983を発見。経過時間=00:00:10.7872760
解候補428567/999990を発見。経過時間=00:00:10.7873126
解候補428570/999997を発見。経過時間=00:00:10.7873486

解説

分母ごとに
不等式 分子/分母 < 3/7
の最大の整数解を求めてます。