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

ソース

#include <Windows.h>
#include <stdio.h>

__int64 DeriveNextVal(__int64 pVal);

void main()
{
    bool WillSkipArr[1000000+1] ={false};
    const int UB = sizeof(WillSkipArr)/sizeof(bool)-1;

    __int64 maxStartVal = 1;
    int maxCnt = 0;

    for (__int64 startVal = 1000000; startVal >= 1; startVal--) {
        if (WillSkipArr[startVal]) continue;

        int Cnt = 1;
        __int64 wkVal = startVal;
        while (wkVal != 1) {
            wkVal = DeriveNextVal(wkVal);
            Cnt++;
            if (wkVal <= UB)
                WillSkipArr[wkVal] = true;
        }

        if (Cnt > maxCnt) {
            maxCnt = Cnt;
            maxStartVal = startVal;
            printf("開始値=%7I64d , 数列長さ=%d\n",maxStartVal,maxCnt);
        }
    }
}

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

実行結果

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

解説

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