Cマガ電脳クラブ(第120回) 素性のよい整数たち

問題

　ここに相異なる7数がある。そのうちの6数を選んでかけ合わせ，
それに残りの1数を足すと素数になり，これはどの6数を選んでも成立しているという。

このような7数の組み合わせはたくさんあるので，その7数の和が最小のものを見つけていただきたい。
なお，ここに登場する数はすべて正の整数とする。

ソース

using System;
using System.Collections.Generic;

class Program
{
    const int Jyougen = 100; //7数の和の仮の上限

    struct JyoutaiDef
    {
        internal int CurrVal;
        internal int SumVal;
        internal List<int> ValList;
        internal bool HasGuusuu; //偶数は7個の中で1つ
    }

    static void Main()
    {
        Console.WriteLine("7数の和が、{0}以下となる組み合わせを検証します。", Jyougen);

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;

        for (int I = 1; I <= Jyougen; I++) {
            WillPush.CurrVal = I;
            WillPush.SumVal = I;
            WillPush.ValList = new List<int>() { I };
            WillPush.HasGuusuu = (I % 2 == 0);
            stk.Push(WillPush);
        }

        int AnswerSumVal = Jyougen;

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

            if (AnswerSumVal < Popped.SumVal) continue;

            if (Popped.HasGuusuu && Popped.ValList.Count == 7) {
                if (IsOK(Popped.ValList) == false) continue;

                Console.WriteLine("和が{0}の解候補を発見しました。", Popped.SumVal);
                Popped.ValList.ForEach(X => Console.Write("{0},", X));
                Console.WriteLine();

                AnswerSumVal = Popped.SumVal;
                continue;
            }

            for (int I = Popped.CurrVal + 1; I <= Jyougen; I++) {
                //和が上限を超えたら枝切り
                if (AnswerSumVal < Popped.SumVal + I) break;

                //偶数を2つ以上含んだら枝切り
                if (Popped.HasGuusuu && I % 2 == 0) continue;

                //既存の数リストと、互いに素でなかったら枝切り
                if (Popped.ValList.Exists(X => DeriveGCD(X, I) > 1)) continue;

                WillPush.CurrVal = I;
                WillPush.SumVal = Popped.SumVal + I;
                WillPush.ValList = new List<int>(Popped.ValList) { I };
                WillPush.HasGuusuu = Popped.HasGuusuu || (I % 2 == 0);
                stk.Push(WillPush);
            }
        }
    }

    //ユークリッドの互除法で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;
        }
    }

    static bool IsOK(List<int> pValList)
    {
        for (int I = 0; I <= pValList.Count - 1; I++) {
            long wkLongVal = 1;
            for (int J = 0; J <= pValList.Count - 1; J++) {
                if (J == I) continue;
                wkLongVal *= pValList[J];
            }
            wkLongVal += pValList[I];
            if (IsPrime(wkLongVal) == false) return false;
        }
        return true;
    }

    //素数かを判定
    static bool IsPrime(long pTarget)
    {
        for (long I = 2L; I * I <= pTarget; I++) {
            if (pTarget % I == 0L) return false;
        }
        return true;
    }
}

実行結果

7数の和が、100以下となる組み合わせを検証します。
和が80の解候補を発見しました。
1,4,7,11,13,15,29,
和が78の解候補を発見しました。
1,3,8,11,13,17,25,
和が78の解候補を発見しました。
1,3,5,7,17,22,23,

解説

A,B,C,D,E,F,G の中でAとBが偶数だとすると、
B*C*D*E*F*Gは、偶数であり、(偶数に自然数を掛けると偶数のため)
A+B*C*D*E*F*Gも偶数です。 (偶数に偶数を加算すると偶数のため)
よって、偶数が2つ以上でないことを、枝切り条件としてます。

A,B,C,D,E,F,G の中でAとBが互いに素でないとすると、
A+B*C*D*E*F*G は、A+Bの共通の約数の倍数なので素数でないです。
よって、7つの数が互いに素であることを、枝切り条件としてます。

A,B,C,D,E,F,G が全て奇数だとすると
A+B*C*D*E*F*Gが偶数になるため (奇数同士の積は奇数であり、奇数同士の和は偶数のため)
偶数が1つ含むことを、条件としてます。