The Collatz conjecture is an unsolved problem in mathematics. It is one of the most famous, and very easy to state, but hasn’t been proven despite being conjectured nearly 90 years ago.
Take any starting integer $a_0$, and follow this process:
\begin{equation*}
a_{i+1} =
\begin{cases}
\;a_i/2 & \text{if $a_i$ is even,}\\
\;3a_i+1 & \text{if $a_i$ is odd.}
\end{cases}
\end{equation*}
We stop applying this when we get $a_k=1$ for some $k$.
For example, with $a_0=17$, we get the sequence $17 \to 52 \to 26 \to 13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1$.
It is conjectured that for any starting number, the process will terminate at 1 after finitely many steps: this is called the Collatz conjecture.
In some places, the statement of the conjecture doesn’t include the termination step, and instead says that it will reach 1 after finitely many steps. This is the same thing, since if you don’t stop as soon as you reach 1, you’ll follow the pattern $1 \to 4 \to 2 \to 1 \to 4\dots$ forever.
This conjecture was proposed in 1937 by Lothar Collatz (pictured above).
The conjecture is widely believed to be true, and so far it has worked for every number mathematicians have tried. Although ‘try everything and see what works’ is a valid approach (Chalkdust has been doing it for years!), it won’t give us a rigorous proof that the conjecture is true, as there would be an infinite number of integers to check.
If the conjecture were false, it would mean there is some number whose sequence doesn’t terminate at 1. Either it would keep increasing beyond any threshold we set, or it would end up in some loop (like the $4 \to 2 \to 1$ loop) of large numbers.
We could try to get a computer to find a counter-example, which would either end up in some other loop of large numbers or find a sequence which gradually increases forever without looping. However, this lands us back in the issue of asking the computer to carry out an infinite number of calculations in a finite amount of time.
Another approach would be to try to get a general proof which may only need some cases checking—for example, we know all powers of 2 eventually terminate. Can we categorise other numbers into finitely many categories which always terminate? Terence Tao had a go at this in 2019, and proved that the Collatz conjecture is ‘almost’ true for ‘almost all’ starting numbers. (In a similar vein, ‘almost all’ issues of Chalkdust have some ‘almost’ good jokes.)
The sequences produced by the algorithm are known as hailstone sequences, due to their rise and fall—until you reach some power of 2, you’ll always have to increase at some step when you’ve reached an odd number.
We say that the stopping time of a number is the smallest number of steps needed to reach 1. The stopping time varies for each starting number; if we begin with 32, we reach 1 after 5 steps, but starting with the smaller number of 27 takes 111 steps to reach 1. The graphs below show the stopping times for the numbers up to 100 and 2000.
An easier ‘problem’, similar to the Collatz conjecture, involves using $a_{i+1} = a_i + 1$ when $a_i$ is odd. This time we get a $1 \to 2 \to 1$ loop, and for every other odd number $a_{i+2}$ will always be smaller than $a_i$. We can rule out both the ‘increasing forever’ and ‘infinite loop of large numbers’ cases, so we know that sequences will always terminate.
This doesn’t work for the actual Collatz conjecture, because $(3a_i+1)/2$ is larger than $a_i$, and if this is odd, then we’ll grow larger still, so there’s a chance we can keep growing by a factor of $3/2$. However, this chance is small, so probabilistically, we’ll decrease in the long run. Unfortunately, this isn’t quite enough to prove we’ll always reach 1—unlikely things happen all the time!
As of 2020, all initial values up to $2^{68} \approx 2.95×10^{20}$ have been checked, and end at 1. This number has improved from earlier verifications; in 1992 the bound was $5.6\times 10^{13}$, which was improved to $19\times 2^{58} \approx 5.48\times 10^{18}$ in 2008.
More from Chalkdust
In conversation with Robin Wilson
Ashleigh Wilcox and Ellen Jolley chat to the professor and maths communicator about books, the Open University and music
Winning Wythoff’s game
Molly Ireland presents a gambit which will impress your mates
Notched edge cards
Joe Celko makes a database from card and knitting needles
On the cover: Spirographs
Ashleigh Wilcox, Jenny Power and Rachel Evans show you how to draw pretty pictures
The problem with addition
It doesn’t add up for Patrick Creagh
Borwein integrals
Aimen Khan ponders how patterns break down