How fast are current programs computationally verifying the Collatz conjecture?

Question

I have seen several past or ongoing projects trying to computationally verify the Collatz conjecture. These projects can be divided into two groups according to the algorithm they use:

• The first group checks for the convergence of the problem for all numbers up to some upper bound. The bottom line is that they calculate the Collatz function iterates, starting from the initial number $n$, and stopping once an iterate drops below $n$. This is also known as computing the glide, or stopping time.

• The second group also checks all numbers up to some upper bound, but searches for the highest number of iterates (steps) before reaching 1. This is known as computing the delay, or total stopping time. Importantly, algorithms used for this second group are at least one order of magnitude slower compared to the first group.

The technical details can be found, e.g., in this link.

My question is how fast (in terms of numbers per second) are state-of-the-art methods in both these groups?

I have found that the program of Eric Roosendaal can check 100000000000000 numbers in approximately 7 days on 2.4 GHz processor. This gives about $2^{27.3}$ numbers per second. The algorithm seems to belong to the second group.

I have also found the paper of Honda et al. which claims that they can check $2^{40.25}$ numbers per second for the convergence (the first group), or $2^{29.9}$ numbers per second for the delay, both on GPU.

I am also aware of the ongoing BOINC project. But here I am unable to find how fast their program is, and which algorithm uses. Does anyone have details on this?

Answer 1

You usually use a slight modification: $x_{n+1}$ is either $x_n / 2$ or $(3x_n*1) / 2$. For the first question all you need to show that starting with $x_0$, there will be some k where $x_k < x_0$, for all 2 <= x < some limit.

Assuming $x_k = 65536n + m$, you make a table which is the smallest of the values of the values $x_{k+1}$ to $x_{k+16}$, and what is the value of $x_{k+16}$, in terms of n, for each of the 65536 values of m. So you can calculate 16 steps in one go.

You can very quickly filter out for which m x = 65536n + m shrinks within 16 steps, for the remaining m you check if 2^32 + 65536m’ + m shrinks in 32 steps, and at some point you check individual numbers.

Answer 2

I am bit of a hurry so I will make this quick. Back in february 2018 I had a short correspondence with Eric Roosendaal on the speed and algorithms. I hope he don't mind me quoting him here since it is of interest:

my program has a lot of optimizations – too many to mention them all quickly, but most of them are on the page on technical details. Bruteforcing ‘every’ number is certainly not what it does. A lot are skipped, and most trajectories are cut off (very) early. in fact, optimizing the ‘tail’ of the calculation turned out to have no effect at all, because only a fraction of numbers ‘get’ there (as I recall it was 1 in 10 million or so, not entirely sure).

As for the exact speed – best you try yourself for a few minutes. download the program and start it up with a number around (say) 100E15. It’s mostly optimized for numbers well below 128 bits, because that is the main area of interest. Every 2 or 3 minutes it writes a line with the ‘current’ number, so it’s easy to compare relative speeds.

Regards,

Eric.

Also a bit about the number of digits and delays:

Notice that 21,000 steps for a number that size is certainly not exceptional. I have a few numbers of around 67 digits taking as many as 8700 steps already.

Yes, look at Eric's page it got most of the information needed. The algorithms they use is not very available (probably too complicated to explain in just a few sentences).