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