C#でプロジェクトオイラーを解く（問題１４「最長のコラッツ数列」）

Tweet

Pocket

どーも、みつおです。

コラッツ問題がまだ証明されていないとか夢があるよね。

問題

正の整数に以下の式で繰り返し生成する数列を定義する.

n → n/2 (n が偶数)

n → 3n + 1 (n が奇数)

13からはじめるとこの数列は以下のようになる.

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

13から1まで10個の項になる. この数列はどのような数字からはじめても最終的には 1 になると考えられているが, まだそのことは証明されていない(コラッツ問題)

さて, 100万未満の数字の中でどの数字からはじめれば最長の数列を生成するか.

注意: 数列の途中で100万以上になってもよい

出典：Problem14

解答

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

namespace Problem14
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(Solve());
            Console.ReadLine();
        }

        private static long Solve()
        {
            long ret = 0;

            //[数、個数]
            Dictionary<long, long> dic = new Dictionary<long, long>();

            List<long> data = new List<long>();
            long n = 0;
            long cnt = 0;

            //100万までループ
            for(int i = 2; i <= 1000000;i++)
            {
                //初期化
                n = i;
                cnt = 0;

                // n が 1 になるまでループ
                while(n != 1)
                {
                    cnt++;

                    // n に対して個数を求めているか判定
                    if(!dic.ContainsKey(n))
                    {
                        //n が 1ならループを抜ける
                        if (n == 1) break;
                        //n が奇数の場合
                        else if (n % 2 != 0) n = n * 3 + 1;
                        //n が偶数の場合
                        else n = n / 2;
                    }
                    else
                    {
                        //現在カウントした数とすでに登録済の個数を足し合わせる
                        cnt = cnt + dic[n];
                        break;
                    }

                    //数に数列の個数を設定
                    dic[i] = cnt;
                }
            }

            //数列の個数の最大値を取得
            var max = dic.Values.Max();

            //最長の列の数値を取得
            ret = dic.First(tmp => tmp.Value == max).Key;

            return ret;
        }
    }
}

出力

626331