Pointer Walk

The Collatz Conjecture

Halve if even, triple and add one if odd. 27 takes 111 steps to reach 1 and climbs past 9,000 on the way.

Maths for ProgrammersBeginner6 min read

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

Starting from 27Interactive
Start at
05k10k055.5111stepsvalue

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:

StartSteps to reach 1Highest value on the way
6816
71652
261040
271119,232
281852
971189,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

python
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)     # 111

Look 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.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    6 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress