Simple rules, chaotic paths, and an unsolved 90-year mystery
The 3n+1 Problem
Pick any positive integer. Apply these rules:
If EVEN: n → n/2
If ODD: n → 3n + 1
Does every number eventually reach 1?
Try Famous Numbers:
0
Steps to reach 1
0
Peak value
0
Peak / Start
Trajectory Visualization
Why Can't We Prove It?
Despite being stated in 1937, no one has proven that ALL numbers reach 1.
Computers have verified it for all numbers up to 268 (≈ 295 quintillion),
yet the proof remains elusive.
Stopping Time Distribution (n = 1 to 10,000)
How many steps does each number take to reach 1? Notice the chaotic distribution!
The Paradox Explained
"Mathematics may not be ready for such problems."
— Paul Erdős, legendary mathematician
The Setup
Lothar Collatz proposed this conjecture in 1937. The rules are absurdly simple:
The Collatz Function:
f(n) = n/2 if n is even
f(n) = 3n+1 if n is odd
The Conjecture: For ALL positive integers n,
repeated application of f eventually reaches 1.
Why Is It So Hard?
The problem looks trivial but is deceptively complex:
Unpredictable behavior — The sequence for 27 takes 111 steps and peaks at 9,232!
No pattern — Nearby numbers have wildly different trajectories
Exponential growth — The 3n+1 rule can make numbers explode before they collapse
Mixing dynamics — The sequence alternates between growth (odd) and shrinkage (even) chaotically
The Numbers
Verified range: All n ≤ 268 ≈ 2.95 × 1020
Record holders (stopping time for n < 108):
• 63,728,127 takes 949 steps
• 3,732,423 takes 597 steps
• 837,799 takes 524 steps
Record holder (maximum value):
• Starting from 27, reaches peak of 9,232 (342× starting value!)
The Paradox
The "paradox" is the disconnect between simplicity and difficulty:
A child can understand the rules
A computer can verify billions of cases
Yet the world's best mathematicians cannot prove it works for ALL numbers
There might be a counter-example — a number that grows forever — but we haven't found one
Attempts at Proof
Mathematicians have tried many approaches:
Probabilistic arguments — On average, numbers should decrease (3/4 factor), but this doesn't guarantee convergence
Algebraic approaches — Studying the problem in different number systems
Dynamical systems — Treating it as a discrete dynamical system
Computational verification — Checking ever-larger ranges (but can't prove the general case)
Connection to Chaos
The Collatz sequence exhibits chaotic behavior:
Sensitive to initial conditions (small changes → big differences)
No closed-form formula for the n-th term
Mixing of growth and decay phases
Statistical properties resemble random walks
"The Collatz conjecture is a notorious open problem in mathematics. It is easy to state but seems completely intractable... It has been said that professional mathematicians should not waste time on it."
— Jeffrey Lagarias, mathematician
Prize
Paul Erdős offered $500 for a proof — and said it was beyond current mathematics. Decades later, it remains unsolved. The Clay Mathematics Institute has not added it to their Millennium Problems, perhaps because it might be undecidable!