Collatz Problem — Definition, Formula & Examples
The Collatz Problem asks whether repeatedly applying a simple rule — if a number is even, halve it; if odd, triple it and add 1 — will always eventually reach 1, no matter which positive integer you start with.
Define the function on positive integers by if is even and if is odd. The Collatz conjecture states that for every positive integer , there exists some finite such that the -th iterate .
Key Formula
Where:
- = Any positive integer
- = The next value in the Collatz sequence
How It Works
Pick any positive integer. If it is even, divide by 2. If it is odd, multiply by 3 and add 1. Repeat with the result. The sequence you generate is called the Collatz sequence (or hailstone sequence) for that starting number. The conjecture claims every such sequence eventually hits 1, then cycles through 4, 2, 1 forever. Despite its simple statement, no one has proven this is true for all integers — it remains one of the most famous open problems in mathematics.
Worked Example
Problem: Find the Collatz sequence starting at n = 6.
Start: Begin with 6. It is even, so divide by 2.
Step 1: 3 is odd, so compute 3(3) + 1 = 10.
Step 2: 10 is even, so divide by 2. Then continue: 5 is odd, 16 is even, and keep halving.
Answer: The full sequence is 6, 3, 10, 5, 16, 8, 4, 2, 1. It reaches 1 in 8 steps.
Why It Matters
The Collatz Problem is a gateway into number theory and mathematical reasoning because it shows how simple rules can produce wildly unpredictable behavior. It has been verified by computer for all starting values up to at least , yet a general proof remains elusive. Mathematician Paul Erdős famously said that mathematics is "not yet ready" for problems like this one.
Common Mistakes
Mistake: Applying the odd rule to even numbers or vice versa.
Correction: Always check parity first. Divide by 2 only when is even; apply only when is odd.