Collatz Conjecture

The Function

Consider the function $ f: \mathbb{N} \rightarrow \mathbb{N} $ where

$ f(n) = \begin{cases} n/2 & n \textrm{ is even} \\ 3n+1 & \textrm{ otherwise} \end{cases} $

and $ \mathbb{N} = \{ 1, 2, 3, \ldots \} $.

The Algorithm

Start with any $ n \in \mathbb{N} $.

Repeatedly calculate $f(n)$, replacing $ n $ with the output each time: $ n \leftarrow f(n) $.

The Conjecture

No matter what number you start with, you eventually get caught in a repeating sequence of values.

The repeating sequence is $ (1,4,2) $.

Exercise

Write some code to verify the conjecture is true for the smallest one hundred natural numbers.

Then try to verify it for the smallest one trillion numbers.