mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   Checking of Collatz problem / conjecture (https://www.mersenneforum.org/showthread.php?t=24661)

 dabler 2019-08-04 12:58

Checking of Collatz problem / conjecture

While playing with the Collatz problem, I have realized that the trajectory (of any number) can be efficiently computed using the [URL="https://en.wikipedia.org/wiki/Find_first_set"][FONT="Courier New"]ctz[/FONT][/URL] operation (count trailing zeros) and a small lookup table mapping [I]n[/I] to [I]3^n[/I]. The idea is described [URL="https://math.stackexchange.com/questions/3311547/alternative-formulation-of-the-collatz-problem"][B]here[/B][/URL].

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

 dabler 2019-08-06 15:52

How far has Collatz conjecture been computationally verified?

Does anyone provide reference for how far has Collatz conjecture been computationally verified? [URL="http://www.ericr.nl/wondrous/"]This page from 2017 by Eric Roosendaal [/URL] claims that the yoyo@home project checked for convergence all numbers up to approx. 2[SUP]66[/SUP]. Is this record still valid today?

 Uncwilly 2019-08-06 19:44

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

 Nick 2019-08-07 08:13

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

 dabler 2019-08-07 16:13

So far, I see 2[SUP]66.4[/SUP] as the highest record. For more details, see the list of records in my answer [URL="https://math.stackexchange.com/questions/3314430/how-far-has-collatz-conjecture-been-computationally-verified"]here[/URL].

 Dylan14 2019-08-07 20:49

From one of my recently completed work units from the Collatz conjecture BOINC project ([URL]https://boinc.thesonntags.com/collatz/result.php?resultid=40842156[/URL]), 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 2019-08-08 18:35

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

 R. Gerbicz 2019-08-08 18:58

[QUOTE=dabler;523359]Currently, I am able to verify the convergence of all numbers below 2[SUP]32[/SUP] in less than one second (single-threaded program running at Intel Xeon E5-2680 @ 2.40GHz).[/QUOTE]

Pretty weak timing.
[url]https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=36[/url]
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 2019-08-09 12:16

[QUOTE=Dylan14;523304]From one of my recently completed work units from the Collatz conjecture BOINC project ([URL]https://boinc.thesonntags.com/collatz/result.php?resultid=40842156[/URL]), 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.[/QUOTE]

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 2019-08-09 13:29

[QUOTE=R. Gerbicz;523364]Pretty weak timing.
[url]https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=36[/url]
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.[/QUOTE]

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 2019-08-09 18:30

[QUOTE=dabler;523393]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.[/QUOTE]

To your first question: That is correct.
To your second question: [URL="https://boinc.thesonntags.com/collatz/server_status.php"]This page[/URL] 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.

All times are UTC. The time now is 22:35.