Pythonでコラッツ数列の長さを求めるアルゴリズムと実装例

正の整数 n が与えられたとき、そのコラッツ数列(Collatz sequence)の長さを求める問題を考えてみましょう。

コラッツ数列とは、次の規則に従って順次生成される数列です。

• n が偶数の場合:n = n / 2
• n が奇数の場合:n = 3n + 1

そして、n が 1 になった時点で数列は終了します。この規則は「コラッツ予想」として知られる有名な未解決問題に関連しており、任意の正の整数から始めても必ず 1 に到達すると予想されています。

具体例

たとえば入力が n = 13 の場合、出力は 10 になります。これは次の数列が生成されるためです。

[13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

この数列には10個の要素が含まれているため、答えは 10 となります。

解法のアプローチ

この問題を解くための手順は以下の通りです。

• num が 0 の場合は 0 を返す(コラッツ数列は正の整数に対して定義されるため)
• カウンターとして length := 1 を初期化する(最初の数自体も長さに含める)
• num が 1 になるまで以下を繰り返す:
  • num が偶数なら num / 2、奇数なら 3 * num + 1 で更新する
  • length を1増やす
• 最後に length を返す

Pythonでの実装例

それでは、実際のコードを見てみましょう。

class Solution:
    def solve(self, num):
        if num == 0:
            return 0
        length = 1
        while num != 1:
            num = (num // 2) if num % 2 == 0 else (3 * num + 1)
            length += 1
        return length

ob = Solution()
print(ob.solve(13))

入力

13

出力

10

実装のポイント

なお、上記のコードでは整数除算を行うために //(切り捨て除算)を使用しています。元の擬似コードにある /(通常の除算)を使うと結果が浮動小数点数(float)になってしまうため、num == 1 の比較が正しく動作しなくなる可能性があります。Pythonで整数を扱う場合は // を使うのが安全です。

計算量についても触れておくと、コラッツ数列の長さは入力値によって大きく異なりますが、一般的なケースでは非常に高速に動作します。ただし、コラッツ予想が証明されていない以上、すべての正の整数で必ず終了するとは厳密には保証されていない点にも注意が必要です。