Cマガ電脳クラブ(第035回) 2

問題

2を、分子が1の分数 (以下単位分数と呼ぶ) の和で表すことを考える。分母が同じものは2個以上使えないとすると、
12個以上の単位分数が必要になる。 12個の和で表した例をひとつあげる。

    1   1   1   1   1   1   1    1    1    1    1    1
2 = - + - + - + - + - + - + - + -- + -- + -- + -- + --
    2   3   4   5   6   8   9   10   12   15   20   72

このように「2を、分母の異なる12個の単位分数の和で表す」例はこのほかにもたくさんある。
そこで、12個の単位分数の分母のうちで一番大きなもの (例では72) に注目する。
この"最大の分母"がなるべく小さくなる例を探してほしい。
答えは例と同じように式の形でお願いする。
ただし、分母になれるのは2以上の整数で、負の数は認めない。

ソース

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();
        for (int MaxBunbo = 2 + 12 - 1; MaxBunbo < int.MaxValue; MaxBunbo++) {
            Console.WriteLine("分母の最大値={0,2}で解を調査中。経過時間={1}",
                MaxBunbo, sw.Elapsed);
            List<int[]> BunboArrList = DeriveBunboArrList(MaxBunbo);
            if (BunboArrList.Count > 0) {
                Console.WriteLine("分母の最大値={0,2}で解を発見。経過時間={1}",
                    MaxBunbo, sw.Elapsed);
                foreach (int[] AnyArr in BunboArrList) {
                    Array.Sort(AnyArr);
                    for (int I = 0; I <= AnyArr.GetUpperBound(0); I++) {
                        Console.Write("1/{0}", AnyArr[I]);
                        Console.Write(I != AnyArr.GetUpperBound(0) ? " + " : " = 2");
                    }
                    Console.WriteLine();
                }
                return;
            }
        }
    }

    struct JyoutaiDef
    {
        internal int CurrVal;
        internal List<int> BunboList;
    }

    //分母の最大値を引数として、単位分数の和が2になる分母の組み合わせを返す
    static List<int[]> DeriveBunboArrList(int pMaxBunbo)
    {
        var AnswerBunboArrList = new List<int[]>();

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrVal = pMaxBunbo;
        WillPush.BunboList = new List<int>() { pMaxBunbo };
        stk.Push(WillPush);

        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();

            int Cnt = Popped.BunboList.Count;

            if (Cnt == 12) {
                int CompareResult = TaniBunsuuSumCompare2(Popped.BunboList);
                if (CompareResult == 0) {
                    AnswerBunboArrList.Add(Popped.BunboList.ToArray());
                }
                continue;
            }

            for (int I = Popped.CurrVal - 1; 2 <= I; I--) {
                WillPush.CurrVal = I;
                WillPush.BunboList = new List<int>(Popped.BunboList) { I };

                //2を超えたら枝切り
                if (TaniBunsuuSumCompare2(WillPush.BunboList) == 1) break;
                stk.Push(WillPush);
            }
        }
        return AnswerBunboArrList;
    }

    //単位分数の和が
    //2未満なら-1を返し
    //2なら0を返し
    //2超えなら1を返す
    static int TaniBunsuuSumCompare2(List<int> pBunboList)
    {
        long Bunsi = 1;
        long Bunbo = pBunboList[0];

        for (int I = 1; I <= pBunboList.Count - 1; I++) {
            Bunsi = Bunsi * pBunboList[I] + Bunbo;
            Bunbo *= pBunboList[I];

            //約分しておく
            long GCD;
            while ((GCD = DeriveGCD(Bunsi, Bunbo)) != 1) {
                Bunsi /= GCD;
                Bunbo /= GCD;
            }
        }
        if (Bunbo * 2 < Bunsi) return 1;
        if (Bunbo * 2 == Bunsi) return 0;
        return -1;
    }

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

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

実行結果

分母の最大値=13で解を調査中。経過時間=00:00:00.0000022
分母の最大値=14で解を調査中。経過時間=00:00:00.0584775
分母の最大値=15で解を調査中。経過時間=00:00:00.0722496
分母の最大値=16で解を調査中。経過時間=00:00:00.0986656
分母の最大値=17で解を調査中。経過時間=00:00:00.1700269
分母の最大値=18で解を調査中。経過時間=00:00:00.3296547
分母の最大値=19で解を調査中。経過時間=00:00:00.6479627
分母の最大値=20で解を調査中。経過時間=00:00:01.3534502
分母の最大値=21で解を調査中。経過時間=00:00:02.7726870
分母の最大値=22で解を調査中。経過時間=00:00:05.6304477
分母の最大値=23で解を調査中。経過時間=00:00:11.4483178
分母の最大値=24で解を調査中。経過時間=00:00:21.8081091
分母の最大値=24で解を発見。経過時間=00:00:41.2632560
1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/8 + 1/9 + 1/10 + 1/15 + 1/18 + 1/20 + 1/24 = 2

解説

分母の最大値を増やしながら、順に解の有無を調査してます。