2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Presumably it would depend quite heavily on the number being computed. $\endgroup$ – Jam Nov 17 '19 at 14:44
  • $\begingroup$ @Jam According to the page of Eric Roosendaal, the complete paths of all numbers up to $N$ bits can be calculated in ${2N}$ bits ($N$ power of 2). So this shouldn't actually matter as the algorithm is implemented with a particular data type (uint64_t or similar). $\endgroup$ – DaBler Nov 21 '19 at 17:14
  • $\begingroup$ @DaBier Yes, you're right. I was thinking on the scale of individual numbers but presumably it should even out on the scale of intervals. $\endgroup$ – Jam Nov 21 '19 at 17:54
1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Although this does not directly answer the question of speed, I find the answer very interesting. However, I did not understand the last part. How do you verify that the $x_k$ shrinks in 32 steps using 16-bit sieve without computing the actual value of $x_{k+16}$? $\endgroup$ – DaBler Nov 21 '19 at 16:06
1
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Nice! Apparently this seems to relate to the algorithm belonging to the second group (tracking the trajectory up to 1). Unfortunately, his programs are only available for Microsoft Windows, so I cannot try it personally. $\endgroup$ – DaBler Nov 25 '19 at 18:17
  • $\begingroup$ Unfortunately, his program doesn't run even in wine (Windows emulator for Linux systems). Could you test its speed for me? $\endgroup$ – DaBler Dec 9 '19 at 17:51
  • $\begingroup$ I don't have his program installed unfortunately. Cant you make a bootmanager and install Windows? $\endgroup$ – Natural Number Guy Dec 9 '19 at 20:38
  • $\begingroup$ You do not have to install it, just download & run it. Never mind. $\endgroup$ – DaBler Dec 10 '19 at 11:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.