Pick any integer you like. Got an integer? OK, now apply this simple rule: if the integer is even, divide by two; otherwise, multiply by three and add one. For example, if you started with 10, you would get 5; if you started with 13, you would get 40. Pretty simple, right? You can pretty much do it in your head for small numbers. (Actually, if you’re willing to concentrate you can probably do it in your head for big numbers too! Quick, what would you get if you start with 217?)
You might not think there’s anything very interesting to be said about this rule… but you would be wrong.
The fun starts when we consider iterating this rule. I’ve talked about iteration before: it just means repeating the rule. So, for example, if we start with 10, we get 5; applying the rule again to 5, we get 16; applying it to 16 gives 8, and so on. What happens if you keep going? Try it before reading on!
Continuing past 8, we get 4, 2, 1, 4, 2, 1, 4… obviously, once we reach 1, we’ll keep cycling through 1, 4, 2 forever: one more than thrice 1 is 4; half of 4 is 2; and half of 2 is 1 again. Hmm… let’s try some other starting numbers and see what happens. What about 3?
3, 10, 5, …
But of course we already know what happens after 5. Starting with 6 goes right to 3. How about starting with 7?
7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, …
It takes a bit longer, but we eventually reach 1. The obvious question presents itself: will we always reach 1 when we iterate this rule, no matter what positive integer we start from? Is there some other loop we could get stuck in? Or is it even possible that there are some starting numbers from which the successive numbers will just keep getting bigger and bigger and never loop at all? If you think that last option isn’t possible, try starting with a number like 27:
27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132…
Having reached as high as 1780, with no end in sight, we start to question whether we’ll ever get back to 1. Well, in this case, it turns out we do, eventually — after going as high as 9232 and repeating the rule 111 times! — but there are lots of other positive integers we still haven’t tried (infinitely many, in fact).
As you might have guessed from the title of this post, no one knows the answer! The Collatz conjecture (put forward by German mathematician Lothar Collatz in 1937) guesses that all starting numbers eventually do reach 1. This is true for all the starting numbers anyone has ever tried (computer programs have been used to try all the integers up to ), but no one has been able to prove that every number will. Incredible, isn’t it? Part of what makes this problem so hard is that the rule sometimes makes numbers smaller, and sometimes bigger, so the path from any starting number to 1 is a zig-zagging path that seems to go up and down at random. And there don’t appear to be any patterns in the number of times the rule has to be applied to reach 1: as we saw, 27 takes 111 steps to reach 1; the numbers on either side of it, 26 and 28, take only 10 and 18 steps, respectively. What is it about 27 that makes it take so long to reach 1? It’s hard to say. It has less to do with 27 in particular than it does with all the integers considered as a whole. If you want to know how many steps it will take to reach 1 from a particular starting number, no one knows a better way to figure it out than just trying it.
As a parting challenge for you, suppose we modified the rule so that if you have an odd number, you multiply by two and add one, instead of multiplying by three and adding one. Even numbers should still be divided by two. What can you say about iterating this new rule?