The Collatz Conjecture: The Simplest Problem Nobody Can Solve

The Formal Definition

Mathematically, we define the Collatz function \( f: \mathbb{Z}^+ \to \mathbb{Z}^+ \) as:

$$f(n) = \begin{cases} n/2 & \text{if } n \equiv 0 \pmod{2} \\ 3n + 1 & \text{if } n \equiv 1 \pmod{2} \end{cases}$$

The conjecture states that for every positive integer \( n \), repeated application of \( f \) eventually yields 1. In other words, the sequence \( n, f(n), f(f(n)), \ldots \) always terminates at 1.

Why It’s So Hard

The problem looks innocent. It’s not.

The 3n+1 step makes odd numbers grow. The n/2 step makes even numbers shrink. But there’s no obvious pattern to how these compete. Sometimes numbers explode upward before crashing down. Sometimes they bounce around for hundreds of steps.

Paul Erdős, one of the greatest mathematicians of the 20th century, said: “Mathematics may not be ready for such problems.”

The conjecture has been verified by computer for all numbers up to approximately \( 2.95 \times 10^{20} \) (Christian Hercher and David Barina’s distributed computing work, 2020). Every single one reaches 1. But verification isn’t proof. There could be a counterexample hiding somewhere larger. This is the same gap between computation and proof that makes prime number formulas so elusive.

The Stopping Time

The stopping time of \( n \) is how many steps it takes to reach 1. Some numbers have surprisingly long stopping times relative to their size.

The number 27 takes 111 steps. The number 9,780,657,630 takes 1,132 steps. There’s no formula to predict stopping time from the starting number.

In September 2019, Terence Tao proved that “almost all” Collatz orbits attain almost bounded values. Published in Forum of Mathematics, Pi (2020), this was the most significant partial result in the conjecture’s history. For any function \( f(n) \) tending to infinity (however slowly), the set of starting values whose orbit minimum exceeds \( f(n) \) has logarithmic density zero. But “almost all” isn’t “all.” The conjecture remains open. Tao himself called it merely a “partial result toward the full conjecture.”

What Could Go Wrong?

If the conjecture is false, there are two possibilities:

First, there might be a number whose sequence goes to infinity. It just keeps growing forever, never coming back down.

Second, there might be a cycle that doesn’t include 1. The sequence could loop forever through a set of numbers without ever reaching 1. The only known cycle is \( 1 \to 4 \to 2 \to 1 \), but others might exist.

Nobody has found either type of counterexample. But nobody has proven they can’t exist.

Is It Useless?

Some mathematicians call the Collatz Conjecture a “dangerous” problem because it’s so easy to state, so tempting to attempt, and so impossible to crack.

The conjecture has no known applications to other areas of mathematics. It doesn’t connect to deep theorems or open doors to new territories. In that sense, it’s isolated. Jeffrey Lagarias compiled an annotated bibliography cataloguing over 500 papers on the conjecture (The Ultimate Challenge: The 3x+1 Problem, AMS, 2010). Five hundred papers on a problem with no applications. That tells you something about its pull.

But here’s the thing. We don’t know why we can’t solve it. The techniques that work on other number theory problems (modular arithmetic, analytic methods, algebraic structures) all fail here. The 3n+1 step scrambles the binary representation of numbers in ways that resist systematic analysis. It connects to dynamical systems (iteration of a piecewise-linear map), ergodic theory (mixing properties modulo powers of 2), and even p-adic analysis. Understanding why standard tools fail might teach us something important.

And there’s always the chance that a solution would require entirely new mathematics. That’s happened before. The Weierstrass function forced mathematicians to rebuild the foundations of analysis. The prime number theorem required complex analysis nobody expected. Sometimes the “useless” problems force breakthroughs.

The Hailstone Analogy

Collatz sequences are sometimes called “hailstone numbers” because they rise and fall like hailstones in a cloud. A hailstone gets pushed up by updrafts, falls a bit, gets pushed up again, and eventually drops to the ground.

The analogy is pretty good. Numbers bounce chaotically before eventually settling at 1 (the ground). But unlike real hailstones, we can’t prove all Collatz sequences eventually land.

The distribution of stopping times is itself interesting. On average, the stopping time of \( n \) grows roughly as \( 6.95 \times \log_2(n) \). But individual numbers deviate wildly from this average. The number 27, which takes 111 steps and climbs to 9,232, is a famous outlier for its size. This unpredictability is part of what makes the conjecture so resistant to systematic problem-solving approaches.

Frequently Asked Questions