すべてのチャレンジ
中級 0件解決済み 正答率0%

最長のコラッツ数列

上限以下の開始値のうち、コラッツ数列が最も長くなるものを求めます。

このチャレンジで学べること

  • コラッツ数列を生成できる
  • 結果をキャッシュして同じ計算の繰り返しを避けられる
  • 同点のときは最小の値を選べる

問題

原文(英語)を表示

正の整数 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

例

例 1
入力:
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 です。

例 2
入力:
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用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

まだ合格した解答はありません。解いて 1 位になりましょう。

他の人の解答から学ぶ

コミュニティの解答

まだ公開された解答がありません。この課題を解いて最初の解答を共有しましょう。