collatz_sequence.py

#!/usr/bin/env python3

"""
Returns the total stopping time of positive number n in the Collatz sequence.
"""
def collatz(n: int) -> bool:
    def get_next(n: int) -> int:
        return n % 2 == 0 and n//2 or (3*n + 1)//2
        """
        Shortcut: 3n + 1 is even if n is odd, so we can divide it by 2;
        this implies smaller stopping times, hence a faster convergence.
        """

    if n <= 2:
        return n == 2 and 1 or 0

    steps = 2 # Count n and 1 in the sequence, which are ignored by the following loop

    # Tortoise & Hare algorithm for detecting a cycle in the sequence
    slow_runner = n
    fast_runner = get_next(n)
    while fast_runner != 1 and slow_runner != fast_runner:
        slow_runner = get_next(slow_runner)
        fast_runner = get_next(get_next(fast_runner))
        steps += 1

    return steps

if __name__ == '__main__':
    steps_dict = {
        2     : 1,
        2e16  : 179,
        2e32  : 359,
        2e64  : 451,
        2e128 : 643,
        2e256 : 1065
    }

    for n, steps in steps_dict.items():
        assert(collatz(n) == steps)

    print("All tests passed")