The Function
\( f: \mathbb{N} \rightarrow \mathbb{N} \)
\( f(n) = \begin{cases} n/2 & n \textrm{ is even} \\ 3n+1 & \textrm{ otherwise} \end{cases} \)
\( \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.