← Research

The Simplest Impossible Problem

A computational exploration of the Collatz conjecture

Pick any positive integer. If it's even, halve it. If it's odd, triple it and add one. Repeat.

The Collatz conjecture says that no matter what number you start with, you'll always eventually reach 1. It has been verified computationally for all numbers up to roughly 2.95 × 10²⁰, yet nobody has been able to prove it.

Paul Erdős famously said, "Mathematics may not be ready for such problems." It has resisted every proof technique thrown at it for over 85 years. The map is trivially simple. The dynamics are not.

This is a computational exploration of what those dynamics look like, what patterns emerge, and why this deceptively simple problem remains one of the great open questions in mathematics.

The Shape of a Trajectory

Let's start by watching the map in action. Enter any number below, or click "Random" to pick one. The trajectory rises and falls like hailstones in a thundercloud — climbing when odd steps multiply by 3, plunging when consecutive even steps divide by 2.

The number 27 is a famous example. It takes 111 steps to reach 1, peaking at 9,232 — over 341 times its starting value. For such a small number, it's a surprisingly wild ride.

Some numbers fall almost immediately. Others soar to enormous heights before tumbling down. The trajectory of 77,671 peaks at over 1.57 billion — twenty thousand times its starting value — before gravity eventually wins.

Hailstone numbers

Collatz trajectories are sometimes called hailstone sequences because they behave like hailstones in a storm: rising on updrafts (the 3n+1 step), falling when the air calms (the n/2 step), rising again, and eventually crashing to the ground. The analogy is apt — the dynamics feel genuinely meteorological, chaotic yet bounded.

The Landscape of Stopping Times

The stopping time of a number is how many steps it takes to reach 1. Plotting stopping times for the first 10,000 numbers reveals something unexpected: the points don't scatter randomly. They arrange themselves into distinct horizontal bands, creating a fractal-like texture.

The banding is real structure, not an artifact. Numbers that are close in value often have very different stopping times, while numbers far apart can have the same stopping time. The bands correspond to how many "odd steps" a trajectory takes — each odd step multiplies by roughly 3/2, while each even step divides by 2, so trajectories with the same number of odd steps tend to cluster at similar total step counts.

Record holders

As we scan through the integers, most numbers have modest stopping times. But occasionally, a number takes spectacularly long to reach 1. These record holders grow slowly:

The Orbit Portrait

What if we draw every trajectory at once? Below, each number from 1 to N has its Collatz sequence rendered as a branching path, with angle determined by whether each step is even (turn slightly left) or odd (turn slightly right). The result is an organic, tree-like form — the orbit portrait of the Collatz map.

Every trajectory merges into paths already traveled. The thick trunk at the bottom is the final descent: 8 → 4 → 2 → 1, where almost every trajectory converges. The branches above are the divergent early steps, where numbers wander through wildly different routes before eventually finding their way down. The structure is self-similar — zoom in on any branch and you'll find the same tree-like shape repeated at a smaller scale.

The Inverse Tree

Instead of asking "where does n go?", we can ask "where does n come from?" For any number n, its predecessors in the Collatz map are:

• 2n — always (since 2n is even and 2n/2 = n)
• (n-1)/3 — only when n ≡ 1 (mod 3) and (n-1)/3 is odd

Starting from 1 and growing outward, this builds the Collatz tree — the complete graph of all paths to 1. If the conjecture is true, every positive integer appears somewhere in this tree. Click to grow it deeper.

The tree is highly asymmetric. The "multiply by 2" branch always exists, creating a spine of powers of 2 along one side (1, 2, 4, 8, 16, ...). The "divide by 3" branches appear less frequently, but when they do, they open up entirely new regions of the number line. This asymmetry is why the conjecture is hard: the tree's growth is governed by a mix of arithmetic (mod 3 conditions) and multiplicative structure that defies simple analysis.

The Shortcut Map

The even steps in Collatz are mechanical — just keep dividing by 2 until you hit an odd number. The real dynamics happen at the odd steps. The shortcut map (or Syracuse function) skips straight from one odd number to the next:

where 2^v is the largest power of 2 dividing 3n+1. This compressed map reveals the true structure: each step either shrinks or grows the number, and the conjecture reduces to showing that this map always eventually produces 1.

In the shortcut map, trajectories are shorter and the dynamics are clearer. The number 27 takes only 41 odd steps (compared to 111 total steps), and you can see exactly where the trajectory grows (steps where T(n) > n) versus shrinks (steps where T(n) < n).

Why Trajectories Shrink (Probably)

There's a beautiful heuristic argument for why the conjecture should be true, even though we can't prove it.

When n is odd, the shortcut map computes (3n+1) and divides out all factors of 2. Since 3n+1 is always even, we divide by at least 2. The key question: how many factors of 2 does 3n+1 typically have?

If we treat 3n+1 as a "random" even number, the probability that it's divisible by exactly 2^k is 1/2^k. So on average, the shortcut map multiplies by 3 (from 3n+1) and divides by the geometric mean of the powers of 2:

Since 3/4 < 1, trajectories should shrink on average. This is the 3/4 heuristic, and it matches computation well — the measured average factor across millions of steps is close to 3/4.

But "on average" is not "always." The conjecture says every trajectory reaches 1, and averages tell us nothing about worst cases. A single counterexample — one number whose trajectory grows without bound — would disprove the conjecture. None has been found, but absence of evidence is not evidence of absence.

Benford's Law

One of the more surprising discoveries in Collatz dynamics: the values visited by trajectories follow Benford's law, the empirical rule that leading digits in naturally-occurring datasets aren't uniformly distributed — the digit 1 appears about 30% of the time, while 9 appears only about 5%.

The match is remarkably close. This isn't coincidence — it follows from the multiplicative structure of the Collatz map. The distribution of log₁₀(n) modulo 1 tends toward uniformity for sequences generated by multiplicative processes, and Benford's law is a direct consequence of that uniformity. In a sense, the Collatz map acts like a random multiplicative process — which is exactly what makes it so hard to analyze deterministically.

The Binary Perspective

The Collatz map has a clean interpretation in binary. Dividing by 2 is a right-shift: we drop the trailing 0. The 3n+1 operation is more interesting: in binary, 3n = 2n + n (left-shift plus original), so 3n+1 shifts left, adds the original, and adds 1.

This means the Collatz map is really a binary string rewriting system. And numbers with specific binary patterns have predictable behavior:

Numbers of the form 2^k−1 (all 1s in binary) are maximally "odd" — every bit is set, so the first step can't simplify anything by shifting. Their stopping times show no clear pattern: 16, 17, 106, 107, 46, 47, 61, 62. Consecutive pairs often differ by exactly 1 (because 2^k+1−1 = 2×(2^k−1) + 1, so after one step it reaches the previous case). But across pairs, the stopping times jump unpredictably. This is the essence of Collatz: local structure is clear, global structure is opaque.

Why Can't We Prove It?

The Collatz conjecture sits at the intersection of additive and multiplicative number theory — and that intersection is notoriously difficult territory.

The 3n+1 operation mixes multiplication (by 3) with addition (+1). The n/2 operation is pure division. Individually, these are trivial. But their composition creates dynamics that encode information about the full factorization of every number the trajectory visits. Proving that no trajectory can grow forever requires controlling this interplay for all possible starting points — an infinite family of arguments, each depending on number-theoretic properties we don't have tools to handle uniformly.

In 2019, Terence Tao proved the strongest result to date: almost all Collatz orbits attain almost bounded values. Specifically, for any function f(n) that grows to infinity (however slowly), the set of numbers whose trajectory stays above f(n) has logarithmic density zero. This is remarkable progress, but it still doesn't prove the conjecture for every number — the "almost all" qualifier hides a potentially infinite set of exceptions.

The conjecture may well be true but unprovable — an independent statement in the formal sense. Or it may yield to some technique not yet invented. Either way, it remains what it has been for 85 years: the simplest impossible problem.