The Collatz Conjecture

log in |

Message boards : Science : The Collatz Conjecture

Author | Message |
---|---|

This project's goal is to prove, or disprove, the Collatz Conjecture. | |

ID: 1 · Rating: 0 · rate:
/ Reply
Quote
| |

How long do you estimate this project will run? | |

ID: 354 · Rating: 0 · rate:
/ Reply
Quote
| |

Just curious, is there any scientific value to proving or disproving the theorem ? | |

ID: 421 · Rating: 0 · rate:
/ Reply
Quote
| |

Just curious, is there any scientific value to proving or disproving the theorem ? I'd love to tell you that it would cure cancer or something, but no. Per This article:
| |

ID: 539 · Rating: 0 · rate:
/ Reply
Quote
| |

Thank you Slicker, | |

ID: 587 · Rating: 0 · rate:
/ Reply
Quote
| |

Slicker wrote: This project's goal is to prove, or disprove, the Collatz Conjecture. I'm just curious how this project can prove Collatz Conjecture. I assume there is one way how the project can disprove the conjecture - if we find the loop of numbers which to not contain "black-hole" sequence 4-2-1, then the conjecture will be disproved...And what about the other possibility which would disprove conjecture (that the numbers will increase without bound)? I also cannot imagine how project could achieve this... | |

ID: 2051 · Rating: 0 · rate:
/ Reply
Quote
| |

At least the current apps are checking if the numbers increase above a certain threshold (currently 6,2771017353866807638357894232077 * 10^57 = 2^192) and signal the number for which it happens back, so it can be a bit more thoroughly scrutinized. But that didn't happen so far ;) | |

ID: 2085 · Rating: 0 · rate:
/ Reply
Quote
| |

I'm just curious how this project can prove Collatz Conjecture I'm pretty curious about that too. More than that, I'm also curious why the numbers being computed are so small. What's the highest number that you've reached? Your best results example is 2,362,032,211,856,451,015,323 with 2514 steps to one, is on the order of 10e21. Here are a couple examples chosen by keyboard mashing, and calculated in well under a second on my 3 year old laptop: 38407962098672039845720938456023984650923847502398750329847502398475029348693847 57890243785789078092347890578324578023078457897839025478780234785879023487578234 78587032784870623806468238704567802348757823780458702 -> 5057 steps, on the order of 10e211 38407962098672039845720938456023984650923847502398750329847502398475029348693847 57890243785789078092347890578324578023078457897839025478780234785879023487578234 78587032784870623806468238704567802348757823780458702287034592836709875967438239 57462395871039456023984562809374509182374029763972388 -> 7887 steps, on the order of 10e291 Cheers, Seth[/quote] | |

ID: 5355 · Rating: 0 · rate:
/ Reply
Quote
| |

I'm just curious how this project can prove Collatz Conjecture So small? Haven't you ever heard that big things come in small packages? :-) Actually, the original 3x+1 project crunched for a year or two. When they stopped, they listed their highest number and the steps. This project simply picked up where they left off and after searching the internet, I could find no other attempts to check all numbers. Has some other research project already calculated the numbers up to 10e291 or created some type of proof that no numbers less than 10e291 could have an infinite number of steps? The beauty of the applications we are using is that they are fast (600 MILLION numbers calculated per second). Granted, that will slow down as the numbers get larger, but if we need to increase the size because we are just duplicating someone else's work, that surely can be done. But, if no one else has checked all the numbers yet, then there is no need to assume that just because a number is larger that it will have more steps. (BTW, you chose even numbers for your example. You could have chosen two numbers half their size as the first step would be to divide by 2.) | |

ID: 5385 · Rating: 0 · rate:
/ Reply
Quote
| |

More than that, I'm also curious why the numbers being computed are so To add something to the point Slicker made. Have you asked yourself what is needed for a lot of steps to reach 1 or that it is not reached at all? Well quite easy, one needs a lot of odd numbers in the sequence so one has to 3x+1 the number quite often in relation to the division by two. Do you know which number has the highest ratio of 3x+1 operations to /2 operations in its sequence? Well, it's not a very large number, it's 993. So in some sense, 993 was the closest candidate so far ;) | |

ID: 5388 · Rating: 0 · rate:
/ Reply
Quote
| |

Has some other research project already calculated the numbers up to 10e291 or created some type of proof that no numbers less than 10e291 could have an infinite number of steps? I assume not. As far as a proof, my own attempts at a proof have so far been unsuccessful. If that changes I'll let you know :P I mainly was trying to figure out what exactly the project was calculating. My examples were trying to point out that you can count steps really fast. When I first found the project, I had the impression that you were just trying to find numbers that had the most steps to 1. The beauty of the applications we are using is that they are fast (600 MILLION numbers calculated per second). Do you take into account previously checked numbers? Meaning that, for example, if you come across 2^n, does the algorithm know enough to stop there and return n? (BTW, you chose even numbers for your example. You could have chosen two numbers half their size as the first step would be to divide by 2.) Ah, so I did. As I said, I just mashed my number keys long enough to get a couple sufficiently large examples ... 50% chance of even numbers! | |

ID: 5401 · Rating: 0 · rate:
/ Reply
Quote
| |

ID: 5402 · Rating: 0 · rate:
/ Reply
Quote
| |

Do you know which number has the highest ratio of 3x+1 operations to /2 operations in its sequence? Well, it's not a very large number, it's 993. So in some sense, 993 was the closest candidate so far ;) Looks like there are 61 divisions and 93 steps, so the ratio's about 0.52? The strong law of small numbers strikes again (I guess?!). Collatz seems to provide endless opportunities for little oddities like this. | |

ID: 5406 · Rating: 0 · rate:
/ Reply
Quote
| |

My examples were trying to point out that you can count steps really fast. That's true and we know that of course. But you will be hard pressed to name applications counting faster than ours ;) The beauty of the applications we are using is that they are fast (600 MILLION numbers calculated per second). In a limited way yes, we do. The problem is that there is not enough memory on the whole planet to store the path lengths for all numbers checked so far. One has to restrict it to a small subset. The lookup tables the applications use represent the "prior knowledge" to speed up as well as shorten the calculations if we come across a known one. And to clarify what Slicker wrote, checking 600 million numbers per second (on a HD5870) says we determine the exact number of steps needed to reach 1 for that many starting numbers and not that the app does 600 million steps per second. That means tracing a single number, all the multiplying, adding and dividing to finally reach 1 (about 500 steps are needed on average with the current numbers, but the apps do some shortcuts as already said) takes only 1.6 nanoseconds (0,0000000016 seconds). Try to beat that! ;) To put this into some perspective, that are only 5 clock cycles of a 3GHz CPU. It would need that much time just to read the number out of its registers ;) By the way, the sum of the needed step count for all numbers in the WU is given in the task details you can look up for each WU (I inserted the thousands seperator): needed 1798 steps for 2,362,102,969,852,703,557,631 Besides the number with the highest step count in the checked range, you can see that the ~206 billion numbers together needed ~107 trillion steps (done in about 345 seconds on a HD5870) to reach 1. That number is actually used to check the validity of the returned result (besides further provisions) and to calculate the granted credits for the specific WU. | |

ID: 5408 · Rating: 0 · rate:
/ Reply
Quote
| |

Looks like there are 61 divisions and 93 steps, so the ratio's about 0.52? Don't take my comment above too serious. I just wanted to illustrate the point, that often larger numbers are not automatically "better" in some metric. Actually, the record of 993 is not exactly the ratio of even to odd numbers in the sequence, it is a little more complicated. The metric, the 993 has the record in is called residue and is defined as: Res(N) = 2^E(N) / (3^O(N) * N) where N is the starting number, E(N) the number of even elements, and O(N) the number of odd elements in the sequence to 1. All numbers so far have residues between exactly 1.0 (all powers of 2) and 1.25314214. And very strangely, for whatever reason, practically no numbers appear to exist with residues between 1.02 and 1.06. So yes, such conjectures provide endless opportunities for little oddities ;) | |

ID: 5409 · Rating: 0 · rate:
/ Reply
Quote
| |

Do you take into account previously checked numbers? The application stores some pre-calculated steps. It uses those with the optimized algorithm w/ parity as explained on the Collatz Wikipedia page. The example on the wiki page looks ahead 5 iterations by pre-calculating the steps for 2^5 numbers (a.k.a. 1-32). The apps used here will look ahead up to 20 iterations which means it uses the steps from 2^20 pre-calculated numbers (1 thru 1,048,576). At 4 bytes each and with 4 arrays required, thats 16MB of RAM. The amount of ram needed doubles for each additional iteration. So, it wouldn't be possible to store all the previous numbers in memory. They would have to be stored on disk. The server would need to keep track of the steps of every number calculated, not just the highest one in a range of numbers. Since the app calculates 200 billion numbers per work unit, the result file to be uploaded would be 800 GB in size. That's GB, no MB. The server would need to append each work units results to a monstrous data file that the client would need to download. The data file would be about 20,000,000,000,000 terabytes in size. Yes, 20 trillion terabytes. My budget just doesn't allow me to purchase that kind of disk space. Google might be able to, but not me. | |

ID: 5410 · Rating: 0 · rate:
/ Reply
Quote
| |

The apps used here will look ahead up to 20 iterations which means it uses the steps from 2^20 pre-calculated numbers (1 thru 1,048,576). At 4 bytes each and with 4 arrays required, thats 16MB of RAM. The amount of ram needed doubles for each additional iteration. If anyone asks why exactly 20 steps and not something like 22, when the amount of needed RAM just doubles with each additional step, well, starting with 21 steps, the stored values wouldn't fit 32bit (4 byte) anymore. That means 21 steps wouldn't need 32 MBytes but 64 MBytes (8 byte per value). Also, doubling the size of the values results in doubling the amount of the needed memory bandwidth for every lookup. And all that for a measly 5% theoretical speedup, which would not materialize because of this. Furthermore the 32Bit CPUs (or GPUs) wouldn't be able to handle the numbers natively causing a massive slowdown. That's why we settled for 20 steps. By the way, scientific publications concerning the technique claimed an optimum of only 12 steps (64kB tables) in the past to accomodate the on chip caches. But we found our approach is significantly more efficient on all systems ;) | |

ID: 5411 · Rating: 0 · rate:
/ Reply
Quote
| |

The number theory behind the conjecture is deep, and like many deep number theory questions (Exs: Riemann Zeta, Goldbach Conjecture, Fermat's Last Theorem) the mathematical interest is not so much about the truth of the statement or not. | |

ID: 5976 · Rating: 0 · rate:
/ Reply
Quote
| |

Finding a counterexample while exceptionally unlikely, would put the question to rest, and simultaneously inspire a study of the weird class of numbers that do not satisfy the Collatz Conjecture. Which point leads me to ask a question I have long wondered about. Are we plugging all "holes"? On occasion we have people killing tasks for various reasons and there is the possibility that one or more specific tasks would be the "one" that no one actually calculates because there never was a satisfactory result returned because all the issues fail. With a work-unit set is never calculated, are then there not gaps in the numbers we have tested? If there are, unlike SaH where it is a lot of "who cares", what if that is where the "golden BB" is? | |

ID: 7491 · Rating: 0 · rate:
/ Reply
Quote
| |

Post to thread

Message boards :
Science :
The Collatz Conjecture

Copyright © 2017 Jon Sonntag; All rights reserved.