A rule a child can follow
Pick any whole number greater than zero. Then repeat:
- If it is even, halve it.
- If it is odd, multiply by 3 and add 1.
Keep going until you reach 1.
Example
Starting from 6
6 is even: 3.
3 is odd: 3 × 3 + 1 = 10.
10 is even: 5.
5 is odd: 16.
16 → 8 → 4 → 2 → 1.
Eight steps.
That is the entire game. Here is the question that has resisted every mathematician who has tried it:
Does every starting number eventually reach 1?
Nobody knows.
Try it
Start. Start at 27. The rule: if the number is even, halve it. If it is odd, triple it and add 1.
- Step
- 0 / 111
- Value now
- 27
- Highest so far
- 27
Start with 6 or 7 and it is over quickly. Now try 27.
27 takes 111 steps
Twenty-seven is a small, unremarkable number. Under this rule it wanders for 111 steps before reaching 1, and on the way it climbs to 9,232, more than 340 times where it started.
Its neighbours behave nothing like it:
| Start | Steps to reach 1 | Highest value on the way |
|---|---|---|
| 6 | 8 | 16 |
| 7 | 16 | 52 |
| 26 | 10 | 40 |
| 27 | 111 | 9,232 |
| 28 | 18 | 52 |
| 97 | 118 | 9,232 |
26 takes 10 steps, 27 takes 111, 28 takes 18. There is no visible pattern connecting a number to how long its journey is. That unpredictability, from a rule this simple, is what makes the problem famous.
Why it climbs, and why it falls
The two halves of the rule pull in opposite directions.
- An odd number gets roughly tripled. But 3 × odd + 1 is always even, so the very next step halves it. Together those two steps multiply by about one and a half.
- An even number is halved, and may be halved again and again.
On average, the halvings win slightly, so the numbers drift downward over time. That is the informal reason people believe every start ends at 1. But "on average" is not proof. Nothing rules out some gigantic number that climbs for ever, or one that returns to itself in a loop that never passes through 1.
Once a sequence hits a power of two, such as 16, it is finished: 16, 8, 4, 2, 1, with nothing but halving.
What is known
- Every starting number up to roughly 300 billion billion has been checked by computer. All of them reach 1.
- It has been proved that "almost all" numbers, in a precise technical sense, eventually drop a long way below where they started.
- Nobody has a proof for all numbers, and nobody has a counterexample.
Checking many cases is not a proof. A statement about every number cannot be settled by testing, however far you go, because there are always more numbers.
The claim that every start reaches 1 is the Collatz conjecture. A conjecture is a statement believed to be true that has not been proved. One famous mathematician said of it that mathematics may not be ready for such problems.
The code
def collatz_steps(n):
steps = 0
while n != 1:
n = n // 2 if n % 2 == 0 else 3 * n + 1
steps += 1
return steps
collatz_steps(27) # 111Look at the loop condition: while n != 1. Does this function always return?
If the conjecture is true, yes. If it is false, there is some input for which this loop runs for ever. We have a six-line program, and nobody on Earth can prove that it always finishes.
That is a good thing to remember the next time a simple-looking loop needs a termination argument. Being short is not the same as being easy to reason about.
Key takeaways
- The rule: halve even numbers, triple odd numbers and add one, until you reach 1.
- 27 takes 111 steps and climbs to 9,232 on the way.
- Neighbouring numbers can have wildly different journeys, with no known pattern.
- Every number ever tested reaches 1, but nobody has proved that all of them do.
- A very short program can hide a question nobody can answer.