Project Euler : Problem 14 『Longest Collatz sequence』

問題

　100万未満において、コラッツ問題を解くと最長チェインになる数は何か。

コラッツ問題って

　そういや昔ネタを書いたなと…
pongeponge.hatenablog.jp

　簡単に言えば、ある数 N₀が
(1)偶数の場合
　N₁ = N₀ / 2
(2)奇数の場合
　N₁ = 3N₀ + 1
という風に計算していくと、どの数字から始めても1に到達するんじゃね？という問題。

じゃあチェインって？

　コンボだドンとか多段ヒットとかそういう話なんだけど(違う)

　例えば、8という数字をコラッツ問題に従って解いていくと
8 → 4 → 2 → 1
となって1になるまでに4つの数字(8, 1を含む)が表れるので、8は「4チェイン」となる。
　もう1つの例として、8より小さい3の場合は
3 ⇒ 10 → 5 ⇒ 16 → 8 → 4 → 2 → 1
で「8チェイン」になって、8の時より長いチェインができてしまう。

　こんな風にチェイン数の厄介な点は、
最初が小さい数字でも大きいチェイン数があらわれる場合がある
というところにある。

最長の見つけ方

　どうしたらええんや…100万まで総当たりでいくかな…と、もやもや考えてたけど、
だいたいこんな感じの方法をとることにした。

　例　5までの数で最長チェインになる数を求める場合
(1) まず5個の番号を振られた箱を用意する
　　[1: ] [2: ] [3: ] [4: ] [5: ]
(2) 箱の中にチェイン数を入れたいが、ここは落ち着いて全部0に初期設定する
　　[1:0] [2:0] [3:0] [4:0] [5:0]

(3) 最大数(5)からコラッツ問題を解いていく
(4) 最初の5はチェイン数1(5:1)なので、5番の箱に1を入れる
　　[1:0] [2:0] [3:0] [4:0] [5:1]
(5) 5は奇数なので、3×5+1で次の数は16(16:2)
(6) 16番の箱は無いので何事も諦めが肝心だと気づいて次を計算する
(7) 16は偶数なので16/2で8(8:3)
(8) 8の箱も無いので諦念する
(9) 次は4(4:4)なので、4の箱にチェイン数4をねじ込む
　　[1:0] [2:0] [3:0] [4:4] [5:1]
(10) あとは2(2:5)、1(1:6)となり、1が出たので終了
　　[1:6] [2:5] [3:0] [4:4] [5:1]
(11) 以上で5から始まるコラッツ問題は終わり
(12) 5はチェイン数6だと判明したのでメモしておく

(13) 次は4のチェイン数を調べる
(14) 4は最初チェイン数1だが、4番の箱には既にチェイン数4が入っている
　　[1:6] [2:5] [3:0] [4:4] [5:1]
(15) つまり4から始めるよりも長いチェイン数を持つ数が既に存在しているので、4は終了する

(16) 次は3
(17) 3の箱はまだチェイン数が入っていないので、チェイン数1を入れる
　　[1:6] [2:5] [3:1] [4:4] [5:1]
(18) コラッツ問題を解いていくと、(3:1)から始まり(10:2), (5:2)となる
(19) 5番の箱はチェイン数1だが、今計算中の(5:2)の方がチェイン数が長いので更新する
　　[1:6] [2:5] [3:1] [4:4] [5:2]
(20) (5:2), (16:3), (8:4), (4:5), (2:6), (1:7)となるので、全てチェイン数が大きい方に更新する
　　[1:7] [2:6] [3:1] [4:5] [5:2]
(21) 結果、3の場合はチェイン数7が得られた
(22) メモには「5 … チェイン数6」と書いてあるので、「3 … チェイン数7」に更新する

(23) 次は2
(24) 2はチェイン数1だけど、既に箱には6が入ってるので2は即終了

(25) 1は出番自体与えられなかった

(26) よって、5までの数で最長チェインになる数は3
(27) 終了

　これと同じことを100万-1に対してすれば速いはず。多分きっとそうなるといいな！

コード

using System;
using System.Diagnostics;

namespace Problem14
{
    class Program
    {
        static Int64 num = 1000000;
        static Int64[] chainNum = new Int64[num + 1];

        static void Main(string[] args)
        {
            Debug.WriteLine(LongestChainNumber());
        }

        /// <summary>
        /// 最長チェインの数を調べる
        /// </summary>
        static Int64 LongestChainNumber()
        {
            Int64 chainNum = 0;
            Int64 maxNum = 0;

            for (Int64 n = num - 1; n >= 2; n--)
            {
                Int64 tmp = CountChain(n);

                if (chainNum < tmp)
                {
                    chainNum = tmp;
                    maxNum = n;
                }
            }

            return maxNum;

        }

        /// <summary>
        /// チェインのカウントとチェイン箱の更新
        /// </summary>
        static Int64 CountChain(Int64 n)
        {
            Int64 count = 1;

            while (n != 1)
            {
                if (n <= num)
                {
                    if (chainNum[n] > count)
                    {
                        return 0;
                    }
                    chainNum[n] = count;
                }

                n = NextCollatzNumber(n);

                count++;
            }

            chainNum[n] = count;

            return count + 1;
        }

        /// <summary>
        /// 次のコラッツ数
        /// </summary>
        static Int64 NextCollatzNumber(Int64 n)
        {
            if (n % 2 == 0)
            {
                return n / 2;
            }
            else
            {
                return 3 * n + 1;
            }
        }
    }
}