maths.free › Frontiers › The Collatz conjecture

The Collatz conjecture

Halve it if even, triple-and-add-one if odd: does every start reach 1?

The statement. Start with any positive integer. If it is even, halve it; if odd, multiply by 3 and add 1. Repeat. The conjecture says you always reach 1. From 27 it takes 111 steps and climbs to 9,232 on the way.

In plain words. The rule is simple enough for a child, the behaviour looks random, and no one can prove the process never escapes to infinity or loops forever somewhere. Checked for every start below 2⁶⁸.

What you need first. Stage 1 (parity, division), Stage 10 (modular arithmetic, binary representation), Stage 8 (why “on average it shrinks” is a probabilistic statement, not a proof).

The parts. (1) The heuristic: an odd step multiplies by about 3/2 (3n + 1 is even, so it is immediately halved), an even step by 1/2; on average the sequence shrinks by a factor of √3/2 per step — so it “should” fall to 1. (2) Cycles: any loop other than 4 → 2 → 1 would have to be enormous (more than 10¹¹ elements). (3) Density results: almost all starting values eventually dip below any fixed bound (Tao, 2019) — almost all, not all. (4) Why it resists: the problem mixes the additive structure (+1) with the multiplicative (×3, ÷2), and mathematics has few tools for that mix.

What is known. Verified to 2⁶⁸; Tao's almost-all result; no proof, and Erdős's verdict that “mathematics is not yet ripe for such problems”.

Symbols used here

\blacksquare\ \text{or}\ \square
end of proof (halmos)
Marks the point where the statement has been established.
\varphi(n),\ \pi(x)
Euler's totient, prime-counting function
Count of 1..n coprime to n; number of primes up to x.
\zeta(s)
Riemann zeta function
Σ 1/nˢ, continued to the complex plane; its zeros are the Riemann Hypothesis.
O(n^2),\ \Theta,\ \Omega
big-O notation
Grows no faster than n² (up to a constant), for large n.
\frac{\partial u}{\partial t},\ \nabla^2 u
partial derivative in time, Laplacian
Rate of change in time; sum of second partials (the diffusion operator).

Questions people ask

Can I actually work on these?

You can understand them, which is the honest first step and what these pages are for. Working on them means the full path through the stages above and then the research literature — but every person who has made progress started by reading the statement.

Why are they unsolved if so many people have tried?

Usually because the existing tools provably cannot work (the barriers in P vs NP), or because the problem mixes two structures mathematics handles separately (additive and multiplicative in Goldbach and Collatz). A solution needs a genuinely new idea.

Jaribu kufanya mambo yako mwenyewe

Mengi zaidi katika Frontiers

The Riemann HypothesisNavier–Stokes existence and smoothnessP versus NPGoldbach's conjectureThe twin prime conjecture