Halve it if even, triple it and add 1 if odd: why does every number end at 1?

For a positive whole number $n$ let

and repeat. The Collatz conjecture (also the 3n+1 problem, or the hailstone problem) says that whatever number you start from, you eventually reach 1 and then cycle through 4, 2, 1.

Lothar Collatz posed it in 1937. The paths jump up and down: 27 takes 111 steps and peaks at 9232; below 10,000 the longest is 6171, at 261 steps.

Each number has exactly one next step, so all the paths together form a tree rooted at 1. Walking back from $n$, $2n$ always leads to $n$; an extra branch appears only when $n-1$ is a multiple of 3 and $(n-1)/3$ is odd.

The stage starts at the root 1 and, for every step back, turns left 0.16 radians at an even number and right 0.29 radians at an odd one, each step the same length. The paths of 1 to 10,000 pass through 21,664 different numbers (some far above 10,000). Thicker lines are stretches more of those numbers pass through. The picture was popularised by Edmund Harriss; this one is computed from the rule.

An odd $n$ becomes even after $3n+1$, so it is halved at least once; half the time twice, a quarter of the time three times… On average each tripling is followed by two halvings. Think of the pair as "times 3, divided by 4":

So on average the numbers shrink. But that is only an average: a particular number could be halved only once, time after time, and keep climbing. A proof must rule out both climbing for ever and falling into some other cycle, and today’s mathematics cannot yet do either.

• Checked: in 2020 David Barina verified by computer everything up to $2^{68}\approx2.95\times10^{20}$; all reach 1.
• Almost all: in 2019 Terence Tao proved that almost all starting points have orbits that fall to "almost bounded" values, one of the strongest results so far; but almost all is not all.
• No small cycles: any other cycle, if one exists, is known to be extremely long.

Paul Erdős once said: "Mathematics may not be ready for such problems."