What it is

Every so often, one comes across a teacher who is Properly Evil. I’ll spare names here, but I have a clear, strong memory of being introduced to the Collatz conjecture on a school trip. “Take a number, let’s say 3. If it’s odd, you treble it and add 1.”

“Ten.”

“And if it’s even, you halve it.”

“Five. Then I treble and add 1?”

“That’s right.”

“So 16. Then halve it, 8. Then halve it, 4. Halve it, 2. Halve it, 1. Treble and add 1, 4… and we’re in a loop. Does that always work?”

“Why not try 9?”

“9… 28… 14, 7, … 22, 11. 34, 17. 52, 26, 13. 40, 20, 10, 5 - then we get into the loop we had before again. Maybe I should keep checking. I’ve done 3 and 9, why not 27?”

At least the journey passed quickly.

What Mr [Redacted] had introduced me to was the Collatz conjecture, proposed in 1937 by Lothar Collatz more formally:

Let ${a_1, a_2, a_3,…}$ be the sequence defined by the relationship $a_k = \frac{1}{2}a_{k-1}$ if $k$ is even and $a_k = 3a_{k-1} + 1$ if $k$ is odd, with $a_1$ any positive integer. Conjecture: 1 is a member of the sequence for any choice of $a_1$.

In other words, Collatz claimed that whatever number you started with, you’d always end up back in the 4-2-1 loop. Try a few! Then try to prove it.

Why it’s interesting

Well, if it was easy to prove, it wouldn’t be a conjecture, would it?

For me, the Collatz conjecture has something of Fermat’s Last Theorem about it: it’s really simple to state, really easy to play around with, and looks like it ought to have a simple, obvious proof.

It doesn’t have a simple, obvious proof.

The great 20th century mathematician Paul Erdos, a Mathematical Ninja if ever there was one, had a habit of offering monetary prizes for the proof of difficult problems. A very simple one might win you a dollar. Something more interesting, ten bucks.

The Collatz conjecture is a \$500 problem. (That might not sound like a lot of money. It doesn’t matter; the tradition is not to cash the cheque, but to frame it. Any clown can make $500. Very few can earn an Erdos cheque.) Indeed, Erdos said “mathematics may not be ready for such problems.”

To prove the Collatz conjecture, you would need to show that every starting number eventually drops to 1. To disprove it, you’d need to find a counterexample: a number that either gives a loop, or that increases without bound. (If there is a counterexample, it’s at least $87 \times 2^{60}$, about $10^{20}$; if it gives a cycle, the cycle must have at least 35,400 terms.)

It’s also an interesting example of how strict mathematical proof is: all of the evidence and all of the heuristics point to the conjecture being true, including checks up to an enormous number. However, we don’t have a proof, so it remains a conjecture. (If you prove it, maybe it’ll become a theorem named after you!)

Who was Collatz?

Lothar Collatz was born in Arnsberg in western Germany, in 1910. In a sense, it’s a pity that the thing he’s most remembered for is his conjecture (which is the kind of thing any muppet could stumble on); he was also a pretty bad-ass numerical analyst.

His dissertation was on difference methods, and he literally wrote the book on numerical methods for solving differential equations. Later in his career, he wrote with Wetterling on optimisation problems - using linear, quadratic and convex programming.

He died aged 80 at a computer arithmetic conference in Bulgaria.

* Updated 2019-03-04 to correct a couple of typos. Thanks, @peterrowlett