The Collatz conjecture: a question a child can ask and nobody can settle

0:00Your book puts four lists of numbers on the page, and does not tell you where they came from. Twelve, six, three, ten, five, sixteen, eight, four, two, one. Seventeen, fifty-two, twenty-six, thirteen, forty, and on down to one. Twenty-one, sixty-four, thirty-two, sixteen, eight, four, two, one. And a fourth one, starting at twenty-two. Four lists, and one instruction. Work out the rule. Pause here if you like. Look at consecutive pairs and ask what happened between them.

0:36Here is the rule, and it has two branches, depending on the number in front of you. If it is even, halve it. If it is odd, triple it and add one. Then take whatever you got, and do the same thing again. That is all of it. Two branches and a loop. Twelve is even, so halve it. Six. Six is even. Three. Three is odd, so three threes plus one. Ten.

1:04Ten is even, five. Five is odd, so fifteen plus one, sixteen. And then sixteen, eight, four, two, one. Which is the first printed sequence, exactly. Now check the others, because your book chose these four carefully. Seventeen is odd. Fifty-one plus one is fifty-two. Fifty-two halves to twenty-six, and twenty-six to thirteen. Thirteen is odd, so thirty-nine plus one is forty. Then twenty, ten, five. Five is odd, so sixteen. And from sixteen it is halving all the way down.

1:45Twenty-one is odd. Sixty-three plus one is sixty-four. Then thirty-two, sixteen, eight, four, two, one. And the fourth starts at twenty-two, halves to eleven, and eleven is odd, so thirty-four, and then seventeen. Every one of them finishes the same way. Sixteen, eight, four, two, one. And now the thing that makes this hard, which a list of numbers hides from you. Look at twenty-one going to sixty-four. That is not a small step. It is more than triple, in a single move.

2:23Every odd number gets thrown upward. Three times a number, plus one, is always bigger than the number. So this is not a descent. It is a descent with jumps in it. Draw the first sequence as a height chart and you can see it. Twelve, six, three, falling. Then three goes to ten, and it is back above where it was two steps earlier. If the rule only ever went down, there would be nothing here to wonder about. Everything would obviously reach one.

2:57The upward steps are the entire reason nobody can prove this. But here is something you can prove, in one line, and it is worth doing. Two odd numbers can never sit next to each other in one of these sequences. Take any odd number at all. Triple it. An odd number times three is still odd. Now add one. Odd plus one is even. So the odd branch always hands you an even number. Always, with no exceptions.

3:29Which means every odd term is followed immediately by an even one, and every jump upward is followed immediately by a halving. Check it against all four printed sequences. There are no two odds in a row anywhere on the page. Second thing you can settle. Look again at twenty-one going to sixty-four. Sixty-four is a power of two. Two multiplied by itself six times. And the moment you land on a power of two, the rest of the sequence is already decided.

4:06Because a power of two is even. Halve it, and you get the next power of two down. Which is even as well. Sixty-four, thirty-two, sixteen, eight, four, two, one. It walks straight down the doubling table from chapter one. No odd numbers. No jumps. Six halvings, and you are finished. Third observation, and this one is about how the sequences relate to each other. Look at the second list and the fourth. The fourth starts at twenty-two, goes to eleven, then thirty-four, then seventeen.

4:45And the second list starts at seventeen. From that point on, the two are identical. Every single term, all the way to one. And that is not luck. It could not have been otherwise. Because the next term depends only on the current one. Nothing else. Not where you came from, not how long you have been going. So once two sequences share a single number, they are the same sequence from then on. Rivers that meet do not separate again.

5:19So who asked this? A German mathematician called Lothar Collatz, in nineteen thirty-seven. And what he claimed is very simple to say. Take any whole number you like. Run this rule. You will reach one. That is it. That is the entire conjecture. A conjecture, by the way, is not a guess. It is a claim precise enough to be tested, and precise enough to be wrong. This one is so precise that a class of eleven-year-olds can test it on fifty numbers in an afternoon.

5:55And it has stayed open for nearly ninety years. Let's be clear about how much testing has been done. Not fifty numbers. Not five hundred. Every whole number up past a billion billion has been checked by computer. Every single one of them reaches one. Not one exception has ever been found. So why is it not settled? Because there is no last whole number. However far you check, there are infinitely many you have not checked. Testing an enormous number of cases is still testing none of the ones beyond.

6:35And that is the sentence this whole section exists to deliver. Checking cases, however many, never finishes the whole numbers. Which raises the question: what does unsolved actually mean here? It does not mean nobody has tried. It means a great many people have tried, for nearly ninety years, and failed. And it does not mean it is probably false. All the evidence points the other way. What is missing is not evidence. It is an argument.

7:11And here is why an argument is a different kind of thing altogether. Last time we met six one seven four, and that one is settled — because there were only eight thousand nine hundred and ninety-one four-digit numbers to test, and somebody tested them all. Here there is no list you can finish. So checking can never be the method. But there is one family you can settle completely, and your book asks you to.

7:41Start from any power of two. Two, four, eight, sixteen, thirty-two, and onwards for ever. A power of two is even, so the rule halves it. And half of a power of two is the next power of two down. Which is even again. So it halves again. There is never an odd number, never a jump. The sequence walks down the doubling table and lands on one. That is a proof. Not fifty examples — an argument that settles every power of two at once, including ones nobody will ever write down.

8:20Put that beside the pile of checked cases, and you can feel the difference between having seen something work and knowing that it works. So, your turn. Your book asks you to start from a hundred. And a hundred is interesting for a reason you only see if you actually do it. It takes twenty-five steps to come down to one. And on the way it goes up seven separate times.

8:47But it never once gets above a hundred. The highest it reaches after the start is eighty-eight. Now try twenty-seven. A much smaller start, so you would expect a shorter and gentler ride. Twenty-seven takes a hundred and eleven steps, and climbs to nine thousand two hundred and thirty-two on the way. And its neighbours give you no warning at all. Twenty-six takes ten steps. Twenty-eight takes eighteen. Twenty-seven takes a hundred and eleven.

9:21That is exactly what nobody can explain. Run a few in your exercise book, and put your longest one in the comments. Next time, games — and how to win one by working backwards from the end.