Checking of Collatz problem / conjecture

[dabler]

While playing with the Collatz problem, I have realized that the trajectory (of any number) can be efficiently computed using the ctz operation (count trailing zeros) and a small lookup table mapping n to 3^n. The idea is described here.

Would anyone be able to further optimize this approach? Any feedback is welcome.

[dabler]

Does anyone provide reference for how far has Collatz conjecture been computationally verified? This page from 2017 by Eric Roosendaal claims that the yoyo@home project checked for convergence all numbers up to approx. 2⁶⁶. Is this record still valid today?

[Uncwilly]

Have you tried looking around the internet for the answer yet?

[Nick]

Maybe this will help:
https://www.mdpi.com/2306-5729/4/2/89

[dabler]

So far, I see 2^66.4 as the highest record. For more details, see the list of records in my answer here.

[Dylan14]

From one of my recently completed work units from the Collatz conjecture BOINC project (https://boinc.thesonntags.com/collat...ultid=40842156), it appears numbers near 6.16*10^21 are being tested, which is between 2^72 and 2^73. Although with the large number of pending tasks, the actual search limit might be lower than this.

[dabler]

Currently, I am able to verify the convergence of all numbers below 2³² in less than one second (single-threaded program running at Intel Xeon E5-2680 @ 2.40GHz).

[R. Gerbicz]

Originally Posted by dabler

Currently, I am able to verify the convergence of all numbers below 2³² in less than one second (single-threaded program running at Intel Xeon E5-2680 @ 2.40GHz).

Pretty weak timing.
https://onlinejudge.org/index.php?op...lem&problem=36
and look at the statistics page (for this problem) on rank=15. Note that the judge in those times was way slower than the current judge or your computer. Beat this.

[dabler]

Originally Posted by Dylan14

From one of my recently completed work units from the Collatz conjecture BOINC project (https://boinc.thesonntags.com/collat...ultid=40842156), it appears numbers near 6.16*10^21 are being tested, which is between 2^72 and 2^73. Although with the large number of pending tasks, the actual search limit might be lower than this.

If I understand it correctly, then you had verified the numbers between 6162977316019422363648 and 6162977368795980496896, which is approximately 2^45 numbers, each one having approximately 73 bits, in 48 minutes using GeForce GTX 1050 Ti GPU. Is that correct?

How can I find out the number of unfinished (pending) tasks? I cannot find any overall progress page.

Thanks.

[dabler]

Originally Posted by R. Gerbicz

Pretty weak timing.
https://onlinejudge.org/index.php?op...lem&problem=36
and look at the statistics page (for this problem) on rank=15. Note that the judge in those times was way slower than the current judge or your computer. Beat this.

Well, this is a completely different problem. You had got eight (!) integers less than 10 000 (approx. 14-bit numbers). All computations had fit into 32-bit words.

I have 2^32 integers, whereas computations can be handled in either in 64-bit or, in the worst case, in arbitrarily precision arithmetic.

[Dylan14]

Originally Posted by dabler

If I understand it correctly, then you had verified the numbers between 6162977316019422363648 and 6162977368795980496896, which is approximately 2^45 numbers, each one having approximately 73 bits, in 48 minutes using GeForce GTX 1050 Ti GPU. Is that correct?

How can I find out the number of unfinished (pending) tasks? I cannot find any overall progress page.

Thanks.

To your first question: That is correct.
To your second question: This page says how many tasks are out in the wild and how many are queued up to be processed. Unfortunately, it does not say where the leading or trailing edge of the search is. That would be a good thing to have on that page.