Project Euler : Problem 44 『Pentagon numbers』

問題

projecteuler.net
日本語訳→Problem 44 - PukiWiki

最小値を求める？

　最初読んだ時、どうやって最小値だと証明したらいいのか謎だった。
一晩考えた結果こうなった。
本当は一度得た差未満を全部調べた方がいいんだろうけど、条件に合うペンタンゴンナンバーがそれほど密集してないので十分な感じ？

コード

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace Problem44
{
    class Program
    {
        static void Main(string[] args)
        {
            P44 p = new P44();
            Debug.WriteLine(p.Solve());
        }
    }

    class P44
    {
        //ペンタゴン数格納リスト
        private List<int> numbers;

        /// <summary>
        /// コンストラクタ
        /// </summary>
        public P44()
        {
            this.numbers = new List<int>();
        }

        /// <summary>
        /// 解く
        /// </summary>
        /// <returns>解を出力する/見つからない場合は-1を返す</returns>
        public int Solve()
        {
            //最初にペンタゴンナンバー1番目を登録する
            numbers.Add(this.CalcPentagonNumber(1));

            for (int max = 2; max != int.MaxValue; max++)
            {
                //numbersの尻側から降順にテストをする
                for (int i = numbers.Count - 2; i >= 0; i--)
                {
                    //i番目のペンタゴンナンバーとmax-1番目のペンタンゴンナンバーを加減算テストする
                    if (this.TestPentagonNumber(i) == true)
                    {
                        //テスト合格なら差を返す
                        return numbers[numbers.Count - 1] - numbers[i];
                    }
                }

                //テスト合格が無ければmax番目のペンタゴンナンバーを加える
                numbers.Add(this.CalcPentagonNumber(max));
            }

            return -1;
        }

        /// <summary>
        /// ペンタゴン数を加減算した場合の検査
        /// </summary>
        /// <param name="si">ペンタゴン数のインデックス</param>
        /// <returns></returns>
        private bool TestPentagonNumber(int si)
        {
            if (this.SubtractionNumbers(si) == true)
            {
                if (this.AdditionNumbers(si) == true)
                {
                    return true;
                }
            }

            return false;
        }

        /// <summary>
        /// 現在の最大ペンタゴン数と引き算の結果ペンタゴン数になるか？
        /// </summary>
        /// <param name="si">ペンタゴン数のインデックス</param>
        /// <returns></returns>
        private bool SubtractionNumbers(int si)
        {
            int sub = this.numbers[this.numbers.Count - 1] - this.numbers[si];

            return this.numbers.Contains(sub);
        }

        /// <summary>
        /// 現在の最大ペンタゴン数と足し算の結果ペンタゴン数になるか？
        /// </summary>
        /// <param name="si">ペンタゴン数のインデックス</param>
        /// <returns></returns>
        private bool AdditionNumbers(int si)
        {
            int sum = this.numbers[this.numbers.Count - 1] + this.numbers[si];

            return this.IsPentagonNumber(sum);
        }

        /// <summary>
        /// ペンタゴン数の計算
        /// </summary>
        /// <param name="n">インデックス値</param>
        /// <returns></returns>
        private int CalcPentagonNumber(int i)
        {
            return (i * (3 * i - 1)) / 2;
        }

        /// <summary>
        /// ペンタゴンナンバー？
        /// </summary>
        /// <param name="n">検査する値</param>
        /// <returns></returns>
        private bool IsPentagonNumber(int n)
        {
            double k = (1 + Math.Sqrt(1 + 24 * n)) / 6;

            if ((int)k == k) return true;
            else return false;
        }
    }
}