問題
正の整数 n から始め、n が偶数なら n / 2、奇数なら 3n + 1 を次の項とし、1 に達したら終わりにします。これがコラッツの規則です。6 から始めると 6, 3, 10, 5, 16, 8, 4, 2, 1 となり、9項です。1 から limit までのすべての開始値のうち、項数が最も多くなるものを見つけてください。
longest_collatz_chain(limit) を実装してください。
数列は途中から同じ道をたどることが多いので、各数について求めた長さを記録しておくと、計算を大幅に減らせます。途中の項は上限を超えることがあるので、64ビット整数を使ってください。
入力
limit:試す開始値の最大値。
出力
項数(開始値と最後の 1 を含む)が最も多い数列の開始値を返してください。同じ項数のものが複数あれば、その中で最小のものを返します。
制約
1 ≤ limit ≤ 100,000
例
入力:
limit = 6
期待される出力:
expected = 6
入力:
long long limit = 6;
期待される出力:
long long expected = 6;
入力:
long limit = 6;
期待される出力:
long expected = 6;
解説
1 から 6 の数列の長さはそれぞれ 1, 2, 8, 3, 6, 9 項なので、答えは 6 です。
入力:
limit = 10
期待される出力:
expected = 9
入力:
long long limit = 10;
期待される出力:
long long expected = 9;
入力:
long limit = 10;
期待される出力:
long expected = 9;
解説
9 からは 20 項(9, 28, 14, 7, ...)となり、10 以下の他のどの開始値よりも多いので、答えは 9 です。
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
まず1つの数列の項数を、開始値と 1 を含めて数えてみましょう。
ヒント 2
長さがすでにわかっている数に到達したら、そこから先はたどらずに足し算で済ませます。
ヒント 3
最良の開始値を更新するのは、長さが真に大きいときだけです。
目安の計算量
時間 O(limit × average new steps)(新たにたどる平均ステップ数)、追加メモリ O(limit)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。