Problem44 差が五角数となる、五角数のペア

問題

五角数は Pn = n(3n-1)/2で生成される. 最初の10項は

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...である.

P4 + P7 = 22 + 70 = 92 = P8である. しかし差 70 - 22 = 48は五角数ではない.
五角数のペア PjとPkについて, 差と和が五角数になるものを考える.
差を D = |Pk - Pj| と書く. 差 D の最小値を求めよ.

ソース

using System;
using System.Collections.Generic;

class Program
{
    const long Jyougen = 6000000000000;

    static long[] DeriveGokakusuuArr()
    {
        var GokakusuuList = new List<long>();
        for (long N = 1; true; N++) {
            long Gokakusuu = N * (3 * N - 1) / 2;
            if (Gokakusuu > Jyougen) break;
            GokakusuuList.Add(Gokakusuu);
        }
        return GokakusuuList.ToArray();
    }

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

        int Kensuu = GokakusuuArr.Length;
        long MaxVal = GokakusuuArr[Kensuu - 1];
        long MinDiffOfMaxVal = MaxVal - GokakusuuArr[Kensuu - 2];

        long kariMin = long.MaxValue;
        string AnswerCalc = "";
        for (int SumP = 0; SumP <= GokakusuuArr.GetUpperBound(0); SumP++) {
            if (SumP % 1000 == 1)
                Console.WriteLine("{0}。残りは{1}。差の最小値={2}",
                    sw.Elapsed, Kensuu - SumP, kariMin);
            if (1 <= SumP && GokakusuuArr[SumP] - GokakusuuArr[SumP - 1] > kariMin) break;
            for (int Kp = 0; Kp <= SumP - 1; Kp++) {
                long JVal = GokakusuuArr[SumP] - GokakusuuArr[Kp];
                if (JVal < GokakusuuArr[Kp]) break;
                long DiffVal = JVal - GokakusuuArr[Kp];

                if (DiffVal > kariMin) continue;

                if (Array.BinarySearch(GokakusuuArr, JVal) < 0) continue;
                if (Array.BinarySearch(GokakusuuArr, DiffVal) < 0) continue;

                if (kariMin > DiffVal) {
                    kariMin = DiffVal;
                    AnswerCalc = String.Format("{0}+{1}={2},{0}-{1}={3}",
                        JVal, GokakusuuArr[Kp], GokakusuuArr[SumP], DiffVal);
                    Console.WriteLine(AnswerCalc);
                }
            }
        }
        Console.WriteLine("項数={0},最大値={1}で検証しました。", Kensuu, MaxVal);
        Console.WriteLine("最大値である{0}との最小の差は、{1}です。", MaxVal, MinDiffOfMaxVal);
        Console.WriteLine("差の最小値={0}", kariMin);
        Console.WriteLine("計算式={0}", AnswerCalc);
    }
}

実行結果

計算量が多すぎるので、作り直しが必要です。

解説

メモ  答えは、5482660