The maths meme that has been distracting mathematicians for a century

Almost a century ago, a mathematician came up with a puzzle that was so seemingly simple and yet so fiendishly difficult that it has been distracting other mathematicians ever since. It has become a meme that jumps from brain to brain, with many people claiming to have solved it, only to have their hopes dashed as the proof unravels. And be warned – once I explain the rules, you will immediately want to start playing around with it yourself, and I take no responsibility for how much of your time you waste.

It starts a bit like a magic trick. Pick a number, any number – well, at least any positive whole number; don’t try to get clever with something like pi. If it is an even number, divide it by 2. If it is an odd number, multiply it by 3 and add 1. Next, apply the same rules to the resulting number. Do this long enough, and you will always end up at 1.

Or at least, mathematicians think you will. Whether this is true for every possible positive whole number is an open question called the Collatz conjecture, named after Lothar Collatz, who first investigated the question in the 1930s. And, surprisingly, it is a really hard question to answer. Indeed, Paul Erdős, one of the most prolific mathematicians of the 20th century, once said that “mathematics may not be ready for such problems”.

So why is the Collatz conjecture so difficult to prove? If you are anything like me, when you first hear about the problem, you will immediately reach for your calculator and start crunching numbers to see if you end up at 1. Indeed, mathematicians have used computers to check every number up to 2⁷¹. Unfortunately, this leaves an infinitely large amount of numbers left to check, so it doesn’t really help us in the quest to find a proof.

One problem is that numbers don’t behave in an orderly way. If we start with 1, we’re done. For 2, we halve it and we’re done. But for 3, the chain of numbers goes: 10, 5, 16, 8, 4, 2, 1. For 7, it goes: 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. You might notice that the chain for 7 contains the chain for 3, and that’s an interesting aspect of Collatz – once you land on a number that has previously been checked, you don’t need to check it again, because you already know where the chain ends up.

All of this makes the problem catnip to mathematicians. I’m reminded of a quote from the excellent xkcd webcomic: “There’s a certain type of brain that’s easily disabled. If you show it an interesting problem, it involuntarily drops everything else to work on it.” And indeed, as the Collatz meme has spread, that is exactly what has happened.

Defining the unknown

Pinning down the origin of the Collatz conjecture is surprisingly difficult, though not as difficult as finding a proof. In a 1980 letter, Collatz wrote that he began investigating it “almost 50 years ago”. It seems he kept the conjecture to himself for many years, presumably seeing it as nothing more than an idle curiosity. It didn’t begin spreading more widely until 1950, when Collatz went to the International Congress of Mathematicians – the largest meeting in the field – and informally chatted about the problem with other attendees.

From there it spread through mathematical networks and even appears to have been rediscovered and rebadged by other mathematicians, going by many names, such as the Syracuse problem, Hasse’s algorithm or even just the 3x+1 problem. According to Jeffery Lagarias, who has extensively surveyed the conjecture, it didn’t appear in print until 1971, when it was described as “a piece of mathematical gossip”, but it really hit the big leagues a year later, when Martin Gardner wrote about it in his Mathematical Games column for Scientific American. If you’ve not come across him before, Gardner is a legendary figure in the field of “recreational mathematics” – essentially stuff that serious research mathematicians slightly look down on, while secretly enjoying along with other maths fans.

The Collatz conjecture continued to straddle the line between recreational and research mathematics for a while yet. I was amused to find a 1983 article titled “Don’t Try To Solve These Problems”, which lists the conjecture, along with others, warning mathematicians away while knowing that they will inevitably succumb to temptation.

One of the first big results came in 1976, when Riho Terras proved an important result. You’ll notice that if you start with an even number, your Collatz chain always drops below this starting number because your first step is to halve it. If you start with an odd number, however, your first stop goes above your starting number – so the question becomes, how long until you come back down again below your starting point, hopefully on your way to 1? Terras called this the “stopping time” for a number, and proved that in almost all cases, the stopping time is finite – meaning that the numbers do eventually go down, rather than blowing up forever.

This isn’t enough to prove the Collatz conjecture, as just one counterexample of an unimaginably large number that never reaches 1 would be enough to disprove it. It is also unsatisfyingly imprecise – what does “almost all” mean when dealing with infinite possibilities? More precision would come in 2002, when Ilia Krasikov and Lagarias proved that for a given number x, at least x^0.84 numbers below it will eventually reach 1. This is a little confusing – for example, if we take x as 100, that means at least 47 numbers below 100 will reach 1. In fact, we know that every number below 100 reaches 1, but what the proof does is to place an explicit cap on the unknowns of Collatz.

The biggest breakthrough came in 2019, when Terrence Tao, arguably the world’s greatest living mathematician, decided to have a crack at this notorious problem. He proved a much stronger version of Terras’s result, showing that not only do “almost all” numbers eventually go below their starting point, but that, effectively, you could get them as low as you want. This feels pretty close to a proof of the Collatz conjecture – except that, in a sense, it isn’t any closer, because there is always the possibility of a counterexample lurking in the far reaches of the number line.

So, what is next for the Collatz conjecture? As I was writing this column, the news broke that OpenAI had used a large language model to solve a major problem that had stumped mathematicians for 80 years. It did this not by proving it correct, but by finding an unexpected counterexample. Could the same thing happen for Collatz? I wouldn’t dare to predict at this point, but it would certainly be ironic if a problem that has infected so many human minds ended up being solved by an AI.