Problem14 最も長い数列の項数

問題

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

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万以上になってもよい

ソース

using System;

class Program
{
    static void Main()
    {
        var WillSkipArr = new bool[999999 + 1];
        long MaxStartVal = 1;
        int MaxCnt = 0;

        for (long StartVal = 999999; StartVal >= 1; StartVal--) {
            if (WillSkipArr[StartVal]) continue;

            int Cnt = 1;
            long CurrVal = StartVal;
            while (CurrVal != 1) {
                CurrVal = DeriveNextVal(CurrVal);
                Cnt++;
                if (CurrVal <= WillSkipArr.GetUpperBound(0))
                    WillSkipArr[CurrVal] = true;
            }

            if (Cnt > MaxCnt) {
                MaxCnt = Cnt;
                MaxStartVal = StartVal;
                Console.WriteLine("開始値={0},数列長さ={1}", MaxStartVal, MaxCnt);
            }
        }
    }

    //数列の次の項を求める
    static long DeriveNextVal(long pCurrVal)
    {
        if (pCurrVal % 2 == 0) return pCurrVal / 2;
        return 3 * pCurrVal + 1;
    }
}

実行結果

開始値=999999,数列長さ=259
開始値=999667,数列長さ=290
開始値=999295,数列長さ=396
開始値=997823,数列長さ=440
開始値=970599,数列長さ=458
開始値=939497,数列長さ=507
開始値=837799,数列長さ=525

解説

Bool型の配列を用意して、無駄な処理を省いてます。