The problem any third grader can understand, but has all the world’s mathematicians completely stumped

Think of any natural number (1, 2, 3, 4…). If your number is even, divide by 2. If your number is odd, multiply by 3 and add 1. Repeat with your new number, over and over again.

For any everyday human-scale number, you will eventually end up in an infinite loop of 4, 2, 1, 4, 2, 1… Sometimes you’ll get there quickly, sometimes it will take hundreds of steps.

Collatz conjecture with 42: 42 -> 21 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1 -> 4 -> 2 -> 1...
The Collatz Conjecture: example calculations for 42 and 99

Here are two examples I tried on the back of a random piece of junk mail: 42 goes into the 4 -> 2 -> 1 loop on the sixth step, while 99 goes on for so long that I ran out of space. Try it yourself with a few numbers to get a feeling for how it works. If you get tired of writing down numbers, this online tool will do the calculations for you.

But of course there are infinitely many numbers… so is that ALWAYS the case, or is there some number that defies the pattern? An exception could either end in a different repeating cycle, or could keep growing forever by multiplying by 3 and adding 1.

This is known as the “3x+1 problem” or the “Collatz Conjecture” (after German mathematician Lothar Collatz). Amazingly enough, this simple problem has never been solved.

Computer calculations show that if there is an exception to the rule, it must be larger than 1,152,921,504,606,846,976. We could keep testing larger and larger numbers on larger and larger supercomputers, and maybe we’d find an exception… but maybe not. Even if we supercompute for ten billion years and still don’t find a counterexample, that’s still not a proof. A proof would require someone to construct a logical argument, starting from things we know to be true, to conclude either that an exception MUST exist or an exception CANNOT exist. (Caveat about this: see below.*) And mathematicians don’t even know where to begin to build that argument (another caveat**).

Probably the world’s top expert on this problem is Jeffrey Lagarias of the University of Michigan, who says: “This is an extraordinarily difficult problem, completely out of reach of present day mathematics.”

Or, put more simply: Math is AWESOME. That is going to be a theme of this blog, I think.

To learn more about the Collatz Conjecture, see this excellent introduction from one of my favorite YouTube channels, Numberphile:

*There is another possibility – it could be “undecidable,” meaning we could prove that the statement could never be proven true or false from the basic assumptions of math. It would be sorta like the statement in simple English, “This statement is a lie.”

**I’m exaggerating a bit, of course, because mumble mumble abstract machine mumble subsemigroup mumble parity sequence mumble mumble matrix something something mumble. But there’s no obvious path forward.

3 thoughts on “The problem any third grader can understand, but has all the world’s mathematicians completely stumped

  1. The statement that the 4-2-1 sequence will be reached is equivalent to saying the function will reach a power of 2.

    1. That’s right! There are several ways of framing the problem. One common way is to say “the sequence will always go to the number 1.”

      I particularly like the “4 -> 2 -> 1 infinite loop” version because it reminds you that the procedure is an iterative, step-by-step process.

  2. It is also true that in any sequence no number will repeat before it reaches the 4-2-1 loop.
    Reason: If it did have a repeat before the 4-2-1 loop the sequence would never reach the 4-2-1 loop.

Leave a Reply