How was the $3x+1$ problem checked up to $5 \times 2^{60}$?

Question

The Wikipedia article for the Collatz conjecture states that:

The conjecture has been checked by computer for all starting values up to $5 \times 2^{60} \approx 5.764 \times 10^{18}$.

It gives an inline citation to the URL http://www.ieeta.pt/~tos/3x+1.html which seems to have expired, and directs to a computational research institute called IEETA "Retrieved 27 November 2011". Searching their site for 3x+1, Collatz and conjecture left me empty handed.

Q: How was the $3x+1$ problem checked up to $5 \times 2^{60}$?

I'm particularly interested in if there are non-trivial algorithmic improvements over direct computation. Or perhaps this was this simply a matter of hit it with a big computer?

Answer 1

It is enough to show that for each starting value $a_0>1$, there is some $k$ with $a_k<a_0$.

• We have $a_1<a_0$ if the step sequence starts with down, i.e. if $a_0\equiv 0\pmod 2$
• We have $a_3<a_0$ if the steps start up,down,down (because $\frac{3a_0+1}4<a_0$ for $a_0>1$); this rules out $a_0\equiv 1\pmod 4$
• Looking at up,down,up,down,down,down, we can exclude $a_0\equiv 3\pmod {16}$

Even after these simple remarks, we have already handled $81.25\,\%$ of all starting numbers.

More generally, a sequence of $u$ ups and $d$ downs implies that $a_{u+d}=\frac{3^u a_0+c}{2^d}$, where $c\in\mathbb N$ depends on the exact order of the ups and downs. Provided $3^u<2^d$, this eliminates the residue class $a_0\equiv 3^{-u}c\pmod{2^d}$ with possible small execptions (i.e. when $a_0\le \frac c{2^d-3^u}$). The trick with pushing the bound for $a_0$ beyond $2^N$, is to continue investigating longer and longer sequences of up and down.

Answer 2

The Collatz Conjecture says that starting with any integer $x \geq 1$, the Collatz sequence will eventually have an element equal to 1. It's quite easy to prove that it is equivalent to the following: For every $x \geq 2$, the Collatz sequence will eventually have an element less than x.

We change the rule so that $x$ is replaced with either $\frac{3x + 1}{2}$ or with $\frac{x}{2}$. We call replacing $x$ with $\frac{3x + 1}{2}$ an odd step, and $\frac{x}{2}$ an even step. If we have $o$ odd steps out of $n$ steps, then $x$ is replaced approximately with $\frac{3^o}{2^n}$. $x$ becomes smaller if $o \times \log_2 (3) < n$ or $o < 0.63093n$.

If you write $x$ as a binary integer, the last $n$ bits will tell you what the next $n$ steps of the sequence are. It also tells you whether after any of those $n$ steps the result was smaller than $x$. So you immediately exclude huge amounts of numbers from the calculation.

Then for those values of the last $n$ bits that pass this test, you look at the last $2n$ bits. Calculate what the last $n$ bits will be after $n$ steps, and check with precalculated data whether these 2n bits will lead to a smaller value within $2n$ steps.

Now you have hugely reduced the numbers that you need to examine. And you can perform $n$ steps of the calculation in one step. ($n$ will probably about 24 or so).