Cマガ電脳クラブ(第145回) 素数団

問題

相異なる10個の数がある。このうちの9個を選んで足し合わせたところ素数となった。
さらにほかのどの9個を選んでもやはり素数となった。

これを満足する10個の数の組み合わせはたくさんあるが，
その中で「10個の数の総和がもっとも小さい組み合わせ」(同じ総和で複数ある場合はすべて)
をお答えいただきたい。

なお、10個の数の総和は素数である必要はない。ここで扱う数はすべて正の整数とする。

ソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    const int SumJyougen = 250;

    static int[] SosuuArr;

    //エラトステネスの篩で上限以下の素数の配列を作成
    static void Eratosthenes()
    {
        var IsSosuuArr = new System.Collections.BitArray(SumJyougen + 1);
        for (int I = 2; I <= IsSosuuArr.Count - 1; I++) {
            IsSosuuArr[I] = true;
        }
        for (int I = 2; I * I <= IsSosuuArr.Count - 1; I++) {
            if (IsSosuuArr[I] == false) continue;
            for (int J = I * 2; J <= IsSosuuArr.Count - 1; J += I) {
                IsSosuuArr[J] = false;
            }
        }
        var SosuuList = new List<int>();
        for (int I = 2; I <= IsSosuuArr.Count - 1; I++) {
            if (IsSosuuArr[I]) SosuuList.Add(I);
        }
        SosuuArr = SosuuList.ToArray();
    }

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

    static void Main()
    {
        Eratosthenes();

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

        for (int I = 1; I <= SumJyougen; I += 2) {
            WillPush.CurrVal = I;
            WillPush.ValList = new List<int>() { I };
            bool CanBreak;
            if (IsValid(WillPush, out CanBreak))
                stk.Push(WillPush);
            else if (CanBreak) break;
        }

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

            //クリア判定
            if (Popped.ValList.Count == 10) {
                int wkSum = Popped.ValList.Sum();
                if (wkSum <= AnswerSum) {
                    AnswerSum = wkSum;
                    Console.WriteLine("総和が{0}の解候補を発見", wkSum);
                    Popped.ValList.ForEach(X => Console.Write("{0},", X));
                    Console.WriteLine();
                }
            }

            for (int I = Popped.CurrVal + 2; I <= SumJyougen; I += 2) {
                WillPush.CurrVal = I;
                WillPush.ValList = new List<int>(Popped.ValList) { I };
                bool CanBreak;
                if (IsValid(WillPush, out CanBreak))
                    stk.Push(WillPush);
                else if (CanBreak) break;
            }
        }
    }

    //有効な状態かを返す
    static bool IsValid(JyoutaiDef pJyoutaiDef, out bool pCanBreak)
    {
        pCanBreak = false;

        int CurrCnt = pJyoutaiDef.ValList.Count;
        int CurrSum = pJyoutaiDef.ValList.Sum();

        int RestCnt = 10 - CurrCnt;
        int MinRest = 0;
        for (int I = 1; I <= RestCnt; I++) {
            MinRest += pJyoutaiDef.CurrVal + 2 * I;
        }
        if (CurrSum + MinRest > SumJyougen) {
            pCanBreak = true;
            return false;
        }

        if (CurrCnt == 9) {
            if (Array.BinarySearch(SosuuArr, CurrSum) < 0) return false;
        }

        if (CurrCnt == 10) {
            for (int I = 0; I <= pJyoutaiDef.ValList.Count - 1; I++) {
                if (Array.BinarySearch(SosuuArr, CurrSum - pJyoutaiDef.ValList[I]) < 0)
                    return false;
            }
        }
        return true;
    }
}

実行結果

総和が242の解候補を発見
1,3,9,13,15,19,31,43,45,63,
総和が200の解候補を発見
1,3,7,9,19,21,27,33,37,43,

解説

下記の必要条件をふまえて、
総和が250以下となる、10個の数を、深さ優先探索で列挙してます。

■■■必要条件1■■■
10個の数の総和が偶数であること

10個の数の総和が奇数と仮定すると
10個の数の中に、少なくとも1つの奇数と含むことになり
その奇数以外の総和が、2より大きい偶数になるから矛盾

■■■必要条件2■■■
10個の数の中に偶数を含まないこと

必要条件1により、10個の数の総和が偶数なので、
10個の数の中に偶数を含んだら
その偶数以外の総和が、2より大きい偶数になるから不適