The conjecture is that the hailstone number sequence (aka the 3n+1 sequence) always reaches 1. The truth or falsehood of this conjecture is still not known (hence "conjecture"), although it appears that the choice of numbers (3,1 and 2) is particularly problematic.
No useful encoding for the sequence is known, so it seems that Gödelizing the problem won't work, either.
Pick any
natural number, and repeat the following:
- If the number is odd, multiply by 3 and add 1
- Else the number is even; divide it by 2
For instance, if we start from 3, we obtain the sequence
3 10 5 16 8 4 2 1.
Note that from 1 we go back to 4, and remain in the 4-2-1 loop. If we instead started from
31, we'd have a slightly more exciting ride:
155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
but again we reach 1.
The sequence is named for hailstones, since the process is much like the formation of a hailstone: start with a drop of water, which falls until it hits strong winds. These blow it back up, where a layer of ice is formed; then the stone starts falling down again. This process repeats itself in hailstones; do you know if all hailstones formed in this manner reach the ground? (Well, yes, because not every day is cloudy...)
Is it always the case that we reach 1? Nobody knows! The Collatz conjecture is that the process always reaches 1; it has been verified on computer for enormous numbers, and never been falsified. But this is not a proof, of course.
There are two ways in which the Collatz conjecture could fail:
- There exists some cycle other than the 4-2-1 cycle;
- There exists some number for which the hailstone sequence is unbounded, so we just encounter larger and larger numbers, but never repeat ourselves.
Neither of the possibilities has been ruled out (both must be false for the conjecture to be true).