The Collatz conjecture is a famous unsolved problem about a very simple rule for positive whole numbers. If a number is even, divide it by 2, and if it is odd, multiply it by 3 and add 1. Repeating this process creates a path of numbers called a hailstone sequence because the values can rise and fall before eventually dropping.
The conjecture matters because it shows how simple arithmetic can produce behavior that is surprisingly hard to prove.
Understanding Math: The Collatz Conjecture
One useful way to study the process is to focus on parity, which means whether a number is odd or even. Every odd value produces an even value after the multiply by three, add one step. That happens because three times an odd number is odd, and adding one makes it even.
So an odd step is always followed by at least one halving step. Sometimes the new even number can be halved many times in a row.
These stretches of halving pull a sequence downward, while odd steps can send it sharply upward. The difficult part is proving that the downward stretches always win in the long run.
A sequence does not need to decrease at every move to eventually reach 1. Starting from a small number can already show this. Beginning with 7 gives 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.
The values rise several times before the sequence settles down. This is why checking only the next step is not enough.
Mathematicians track features such as the largest value reached, the number of steps before reaching 1, and the total number of odd steps. These measurements reveal patterns, yet none of them has led to a full proof.
Computers have tested the conjecture for enormously many starting values. This gives strong evidence that the claim is true, but evidence is not the same as proof. A computer check always covers a finite list, while there are infinitely many positive whole numbers.
One untested number could behave differently. There are several possible kinds of failure. A sequence might grow forever without returning.
It might enter a repeating loop that does not include 1. It might behave in some other unexpected way. No such example has been found, but ruling out every possibility requires reasoning that works for all numbers at once.
Students often meet this topic when learning algorithms, loops, variables, parity, and proof. It is easy to write a short program that starts with a number and repeatedly applies the rule. A careful program should count steps, save the largest value, and stop when it reaches 1.
It should use a number type large enough for temporary growth, since values can become much bigger than the starting value. When working by hand, write each value clearly and check odd or even before choosing the next operation.
The main lesson is deeper than arithmetic. Simple instructions can create complicated patterns, and many successful examples do not automatically establish a mathematical fact.
Key Facts
- Collatz rule: if n is even, the next value is n/2.
- Collatz rule: if n is odd, the next value is 3n + 1.
- A Collatz sequence repeats the rule until it reaches 1, if it reaches 1.
- After reaching 1, the sequence cycles as 1, 4, 2, 1, ...
- For n = 27, the sequence reaches a maximum value of 9232 before falling to 1.
- The conjecture says every positive integer eventually reaches 1, but no proof is known.
Vocabulary
- Collatz conjecture
- The unproven claim that every positive integer eventually reaches 1 when the Collatz rule is repeated.
- 3n + 1 rule
- The step used for odd numbers in the Collatz process, where n is replaced by 3n + 1.
- Hailstone sequence
- The list of values produced by repeatedly applying the Collatz rule to a starting number.
- Iteration
- The repeated application of the same rule or process to the result from the previous step.
- Cycle
- A repeating loop of values that a sequence enters and never leaves.
Common Mistakes to Avoid
- Applying 3n + 1 to even numbers, which is wrong because even numbers must be divided by 2 first.
- Stopping when the sequence first gets smaller, which is wrong because a hailstone sequence can rise again before reaching 1.
- Assuming many examples prove the conjecture, which is wrong because a proof must work for every positive integer, not just tested cases.
- Forgetting the 1, 4, 2, 1 loop, which is wrong because reaching 1 does not make the rule stop mathematically unless you choose to stop recording.
Practice Questions
- 1 Starting with n = 10, write the Collatz sequence until it reaches 1. How many steps does it take?
- 2 Starting with n = 7, write the Collatz sequence until it reaches 1 and identify the largest value reached.
- 3 Explain why checking the Collatz rule for the first million positive integers would still not prove the conjecture.