mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2019-08-04, 12:58   #1
dabler
 
dabler's Avatar
 
"David Barina"
Jul 2016
Brno

3·11 Posts
Default 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 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 is offline   Reply With Quote
Old 2019-08-06, 15:52   #2
dabler
 
dabler's Avatar
 
"David Barina"
Jul 2016
Brno

3·11 Posts
Default How far has Collatz conjecture been computationally verified?

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. 266. Is this record still valid today?
dabler is offline   Reply With Quote
Old 2019-08-06, 19:44   #3
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

19×443 Posts
Default

Have you tried looking around the internet for the answer yet?
Uncwilly is offline   Reply With Quote
Old 2019-08-07, 08:13   #4
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

24×89 Posts
Default

Maybe this will help:
https://www.mdpi.com/2306-5729/4/2/89
Nick is offline   Reply With Quote
Old 2019-08-07, 16:13   #5
dabler
 
dabler's Avatar
 
"David Barina"
Jul 2016
Brno

2116 Posts
Default

So far, I see 266.4 as the highest record. For more details, see the list of records in my answer here.
dabler is offline   Reply With Quote
Old 2019-08-07, 20:49   #6
Dylan14
 
Dylan14's Avatar
 
"Dylan"
Mar 2017

499 Posts
Default

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.
Dylan14 is online now   Reply With Quote
Old 2019-08-08, 18:35   #7
dabler
 
dabler's Avatar
 
"David Barina"
Jul 2016
Brno

3×11 Posts
Default

Currently, I am able to verify the convergence of all numbers below 232 in less than one second (single-threaded program running at Intel Xeon E5-2680 @ 2.40GHz).
dabler is offline   Reply With Quote
Old 2019-08-08, 18:58   #8
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

101011000102 Posts
Default

Quote:
Originally Posted by dabler View Post
Currently, I am able to verify the convergence of all numbers below 232 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.
R. Gerbicz is offline   Reply With Quote
Old 2019-08-09, 12:16   #9
dabler
 
dabler's Avatar
 
"David Barina"
Jul 2016
Brno

418 Posts
Default

Quote:
Originally Posted by Dylan14 View Post
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 is offline   Reply With Quote
Old 2019-08-09, 13:29   #10
dabler
 
dabler's Avatar
 
"David Barina"
Jul 2016
Brno

3·11 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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.
dabler is offline   Reply With Quote
Old 2019-08-09, 18:30   #11
Dylan14
 
Dylan14's Avatar
 
"Dylan"
Mar 2017

499 Posts
Default

Quote:
Originally Posted by dabler View Post
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.
Dylan14 is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Collatz 3x+1 problem Cybertronic Miscellaneous Math 4 2019-03-20 08:40
Collatz Conjecture Proof Steve One Miscellaneous Math 21 2018-03-08 08:18
this thread is for a Collatz conjecture again MattcAnderson MattcAnderson 16 2018-02-28 19:58
Collatz conjecture MattcAnderson MattcAnderson 4 2017-03-12 07:39
Related to Collatz conjecture nibble4bits Math 1 2007-08-04 07:09

All times are UTC. The time now is 05:57.

Wed Aug 12 05:57:05 UTC 2020 up 26 days, 1:43, 1 user, load averages: 1.45, 1.46, 1.55

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.