Collatz conjecture

Written as a map, the rule of the Collatz conjecture is

A flight runs from $n$ through $f(n)$, $f(f(n))$ and so on, and ends when it reaches 1, since from there it would only go round 1 → 4 → 2 → 1. The conjecture says that every positive whole number gets there. Here you can fly whole numbers, even hundreds of digits long, alone or in a crowd. You can set them against the rough argument that makes the conjecture so believable, and see why that argument is not a proof.

Across is the number of steps and up is the value, on a logarithmic axis unless you choose Plain, which gives the familiar hailstone picture. Each number in the crowd is a coloured line, so a stretch that many numbers travel has stronger shading: brighter on a dark picture, darker on a light one. The number looked at is highlighted, with a red point where it is now. Flights are hard to guess: 27 climbs to 9 232 and needs 111 steps to reach 1, while 28 needs 18.

Why is it believed? An odd step always gives an even number, so count it together with the halving that follows as one shortcut step. Now pretend that the parities of these steps are independent fair coin flips. Half the time $n$ is multiplied by about 3/2 and half the time by 1/2, so on average a shortcut step changes $\ln n$ by

Numbers should then shrink, typically by a factor of 3/4 every two shortcut steps. On the logarithmic axis this drift is the dashed line, drawn for a Same size crowd of 100 or more. It ignores landing: numbers that reach 1 stay on the floor, so near the end the crowd’s average height on this axis falls more slowly than the line.

The coin flips are only a model of how numbers behave on average. The conjecture is about every positive whole number, and a single flight that never reaches 1 would break it.

The negative numbers show what the argument misses. The same rule on them has loops, and three are known, such as −5 → −14 → −7 → −20 → −10 → −5. The coin flips predict shrinking there too, yet going once round any loop changes $\log|n|$ by exactly 0. A downward drift on average cannot rule out a loop, among the positive numbers either.

Coral turns the flights round: grown backwards from 1, the paths of a crowd form a tree. Each edge turns from the one before by $+\alpha$ when the new number is even and by $-\alpha \log_2 3$ when it is odd, with α set by Bend. Going back from 1, an even step doubles the number and raises its $\log_2$ by 1, and an odd step lowers it by a little more than $\log_2 3$. So the edge reaching n has turned from straight up by $\alpha \log_2 n$ in all, plus a little for each odd step: its turning records the size of n. Along a branch the direction rises and falls with the numbers of one flight, so each branch is a flight curled up. Branches join where flights meet. In these terms, the conjecture says that the tree grown from 1 contains every positive whole number.

The problem is generally attributed to Lothar Collatz, who posed questions of this kind in the 1930s. The coral follows Edmund Harriss’s “Collatz seaweed” (2016).