Collatz Conjecture

Source: Dec 2023, Task 6 (DTU 02002/02003). Study solution — not an official answer key.

Problem

One Collatz step: if n is even, replace with n / 2; if odd, replace with 3n + 1.

Write collatz_conjecture(n) returning how many steps are needed to reach 1 (positive int n).

>>> collatz_conjecture(3)
7

Approach

Loop until n == 1, applying the even/odd rule and counting steps. Use integer division n // 2.

Solution

def collatz_conjecture(n):
    steps = 0
    while n != 1:
        if n % 2 == 0:
            n = n // 2
        else:
            n = 3 * n + 1
        steps += 1
    return steps