Collatz Conjecture

The Collatz conjecture, also known as the 3n+1 problem, is probably the most famous “easy to state, impossible to prove” problem in mathematics.

The rule

Start with any positive integer $n$. Apply the rule:

• If $n$ is even, replace it with $n/2$.
• If $n$ is odd, replace it with $3n + 1$.

Repeat.

For example, starting with 6: $6 \to 3 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1$. Starting with 27, the sequence rises to 9232 before finally descending to 1 — taking 111 steps.

The conjecture is: no matter which positive integer you start with, the sequence always eventually reaches 1.

State of play

• All starting values up to about $2 \times 10^{20}$ have been verified by computer to reach 1.
• Terence Tao proved in 2019 that for “almost all” starting values, the sequence eventually becomes very small. This is one of the strongest partial results, but it does not prove the full conjecture.
• Paul Erdős famously offered $500 for a proof and said: “Mathematics is not yet ready for such problems.”

Why it’s hard

The Collatz iteration is a mix of multiplication, addition, and division that doesn’t respect any obvious algebraic structure. Every standard tool of number theory — modular arithmetic, L-functions, sieve methods — seems to miss. The conjecture is easy to state but eludes every known technique.

It has become a kind of mathematical folk legend: the problem so simple a child can understand it, so hard that no one can solve it.

Related work

• Jeffrey Lagarias has compiled an extensive survey of partial results.
• Gerhard Opfer announced a proof in 2011, but a gap was quickly found.
• Several claimed proofs appear on preprint servers each year. None have stood up to scrutiny.

Unlike the Millennium problems, Collatz carries no formal prize, but its cultural status in mathematics is enormous. A proof would be a career-defining achievement for anyone who achieved it.

Starting value n

27 97 871 6171 77031

Starting

27

Steps to reach 1

111

Maximum value

9232

Odd / even steps

41 / 70

The Collatz rule: if n is even, divide by 2; if n is odd, multiply by 3 and add 1. The conjecture says every positive integer eventually reaches 1. Starting at 27, the sequence peaks at 9232 before descending.

Frequently asked

Has the Collatz conjecture been tested on a lot of numbers?

Yes. Every starting value up to about 2 × 10^20 has been checked by computer. All reach 1. But no proof exists that this holds for every positive integer.

Why is this so hard?

Because the iteration doesn't respect any obvious algebraic structure — it's a mix of multiplication, addition, and division that resists every standard tool. Paul Erdős famously said 'Mathematics is not yet ready for such problems.'

Continue reading

Person

Paul Erdős

Prolific Hungarian mathematician who lived out of a suitcase, collaborated with more mathematicians than anyone else in history, and gave us the 'Erdős number'.

Read →Person

Terence Tao

Australian-American mathematician, Fields Medalist, and one of the most prolific and wide-ranging mathematicians of the 21st century.

Read →Blog

Stirling's Approximation: How Big Is n Factorial, Really?

The factorial n! grows faster than any polynomial but slower than any exponential. A single formula from 1733 pins down its size precisely — and inexplicably involves both π and e.

Read →