The Collatz Conjecture: Unsolved but Useless

Pick any positive integer. If it’s even, halve it. If it’s odd, triple it and add one. Repeat. You’ll always end up at 1.

That’s the Collatz Conjecture. It sounds like something you could prove in an afternoon. Mathematicians have been trying for nearly 90 years. Nobody’s succeeded.

You might also hear it called the 3n+1 problem, Ulam’s conjecture, Kakutani’s problem, Thwaites conjecture, Hasse’s algorithm, or the Syracuse problem. Same puzzle, different names.

The Conjecture

The rules are dead simple:

• Start with any positive integer \( n \).
• If \( n \) is even, divide by 2 to get \( n/2 \).
• If \( n \) is odd, multiply by 3 and add 1 to get \( 3n + 1 \).
• Repeat until you hit 1.

The conjecture claims every positive integer eventually reaches 1. No exceptions.

Quick Examples

Starting with 1: Already there. Done.

Starting with 2 (even): \( 2 \to 1 \). One step.

Starting with 3 (odd): \( 3 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1 \). Seven steps.

Starting with 27: This one’s wild. It takes 111 steps and climbs as high as 9,232 before finally dropping to 1.

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 \( 2^{68} \) (that’s about 295 quintillion). Every single one reaches 1. But verification isn’t proof. There could be a counterexample hiding somewhere larger.

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 2019, Terence Tao proved that “almost all” Collatz sequences reach values close to 1. Specifically, for almost all starting points, the sequence eventually drops below any fixed bound. But “almost all” isn’t “all.” The conjecture remains open.

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.

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. Understanding why they fail might teach us something important.

And there’s always the chance that a solution would require entirely new mathematics. That’s happened before in math history. 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.

Frequently Asked Questions