The Collatz Conjecture

log in |

Message boards : Science : The Collatz Conjecture

Previous · 1 ·

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

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. It was a big problem when everyone had to use app_info files for ATI cards and the max # of errors was set very low. It was a real pain going through them every day to resubmit them. The max errors was increased to 12 which has pretty much eliminated the problem. Once in a great while I still end up having to resubmit one. It shows up as a new wu name since the name is generated using a timestamp, so looking at the name doesn't really tell you what is inside. I've considered changing the WU names to show the starting number and instead of resubmitting the WU, just zapping the results and clearing the counts so it thinks it is brand new, but I have to play around with a script to do that in test which I haven't gotten around to yet. So for now, I have to look up the WU in the database, copy the file that gets downloaded and resubmit it manually. I wonder it it would help if I posted the failures on the in a "message board of shame" topic. ;-) | |

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

How do you know when the theory has been proved or disproved using this project? What is the mechanism for determining this? | |

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

How do you know when the theory has been proved or disproved using this project? What is the mechanism for determining this? Proving it via brute force checking of numbers requires checking every number to infinity, so we'll never run out of work. ;-) In other words, we have a much better chance of disproving it since all it takes is a single number. The collatz apps used here will return a distinct error if the steps exceed what the application can handle. If one of those is found, it will probably lead to more theories on the way that number behaves to see if there is some pattern as to why the steps never reach 1. At a minimum, we'll check it with a much more robust infinite precision math library to see if the it really is just a large number of steps (e.g. we need increase the precision of the Collatz apps) or whether it somehow just keeps going in a loop or rising to infinity. So, in a nutshell, we are looking for candidates that could disprove it and if we find one (or more), we'll go form there. | |

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

Thanks Slicker, | |

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

And thankfully Collaz is one site that uses my ATI-Graphics card to useful work, | |

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

Since no one can store all results (number + number of steps to reach 1), | |

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

Do we know that all numbers < a have been proven to go to 1? That is only valid if same user is doing all the increasing processing. | |

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

Since no one can store all results (number + number of steps to reach 1), I've been toying with that idea as well, and have put your script to C#, where it's doing quite OK. However, it's definately slower than a full WU... 1G numbers takes about 20 seconds here (Q6600, 2.8Ghz, 1 core). Slicker claims about 600M numbers checked per second, at a higher N too (which shouldn't matter much for this method). So let's say it's still a tiny weeny bit slower. I can't find how many numbers there are in 1 WU, but I'm sure Slicker or Gipsel can tell you :) The routine in question : public static int Collatz (int n) { int m,counter=0; m = n - 1; while(n > m) { if(n % 2 == 0) n = n/2; else n = 1+n*3; counter++; } return counter; } Throw a nice loop around it ( for(int n=5;n<huuuugenumber;n++) {}, you know the drill :P ) and go for it, but in order to speed things up, you might need assembler magic :) On the other hand, i'm currently looking at the binary representation of numbers, and so far it seems the amount of "1"s can only decrease... whereas the number of zeroes (which are lovely, since division by 2 in binary is only too easy) goes everywhere... Probably nothing, but hey :) | |

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

looks like the conjecture has been proved 2 + 2 = 5 Just because I post it on my web site, does that make it true? Nope. Just because Mr. Schorer posts his theory on his web site, it doesn't make it true either. Yes, occampress.com is his web site even though he speaks of himself in the 3rd person on the home page which I find a little scary. His latest paper is dated Nov. 2010 but he has been posting solutions and thoughts on this since at least 2005. So far, a total of zero have been accepted as proof of anything. For a little history, you can check this out: http://en.wikipedia.org/wiki/Talk:Collatz_conjecture/Archive_1 Granted, being posted on Wikipedia doesn't make it true either. So, I would urge you to read what other mathematicians think about his work and whether they agree or not. But, from what I've read so far, the author is the only one who thinks his work is correct and that doesn't count as a solution for me. If his work is correct, then I would expect him to be able to disprove the previous proof that it can't be proven as they can't both be true. That proof can be found here: http://arxiv.org/abs/math.GM/0312309 | |

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

thank you for the links :) If we find a single number which loops over and over again on the same sequence (e.g. 3x+1 / 2 occurs repeats with the same numbers over and over and over), that would disprove the Collatz Conjecture. There are checks to look for loops. If that were to happen, we'd need to investigate further to figure out whether it truly has a looping sequence of calculations or whether the steps for that specific number just exceed the max steps the current app can handle. On the other hand, to prove it, one would have to check every number to infinity, so we'll never run out of work if it is true -- or at least not until an accepted mathematical proof is found. ;-) | |

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

I haven't seen it mentioned yet, but does the Conjecture hold true for negative numbers as well? | |

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

No. Or, not without modifications. For example, starting with -25: | |

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

Can we speed up the process? | |

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

To answer my own question with an explanation from another thread, no we probably cannot speed it up. | |

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

Consider a 50 processor GPU taking 1 second to test a set of 50 numbers In the case an AMD HD 5870, the actual stats are: Consider a 1600 processor GPU taking 1 second to test a set of 614,838,520 numbers.In reference to the previous question... Any logic that causes deviation slows down a GPU. Maximum speed is obtained when there are no loops -- or rather the number of iterations within a loop is exactly the same (e.g. they are unrolled). Otherwise, some of the processors have to wait for the other processors which had more iterations to catch back up. In other words, it isn't like a CPU where each core/thread can do something different. On a GPU, all processors to the exact same thing at the exact same time. | |

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

This project's goal is to prove, or disprove, the Collatz Conjecture. But maybe the answer is 42 ;) So this project is actually infinite, I like it.. | |

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

Since no one can store all results (number + number of steps to reach 1), Doing hailstone sequence until the result is smaller than the original number is called 'glide' in this source : http://www.ericr.nl/wondrous/#part2 Proving the 'glide' of every positive integer is limited = Proving Collatz conjecture, and vice versa. Slicker mentioned the apps in this project use 20-iteration precalculation. So the code may look like this (I guess) in pseudocode: /* Assume n = 1048576 k + r (0 < r <1048576), just a division :) After 20 iterations, either applying n/2 or (3n+1)/2 to n according to b being odd or even , we got: n' = ak + b, where a = 3^x Assume we have 4 tables(arrays) containing the results of precalculations: alpha[1048576] : stores a beta[1048576] : stores b steps[1048576] : one 'n/2' operation = 1 step , one '(3n+1)/2' = 2 steps results[1048576] : stores the steps from 1-1048575 when n drops below 1048576 results[x] = collatz steps of 'x' the tables mentioned above took under 10 secs to create on my 2-year-old PC :), but took several hours to code because I'm not a pro coder :( Alright , here we go: */ int collatz(int n){ int count = 0; while(n >= 1048576){ int r = n% 1048576; // Or r = n&1048575(using bitwise operation) n = (n/1048576) * alpha[r] + beta[r]; // Jumping 20 iterations count += steps[r]; } return count + results[n]; } /*This function has only one conditional statement : while(n >= 1048576) and should be suitable for GPU computing. If we only want to disprove the conjecture, not to calculating all the sequences until n hit 1, perhaps this below would work:*/ int collatz(int n){ int count = 0; int original = n;while(n >= original){int r = n% 1048576; // Or r = n&1048575(using bitwise operation n = (n/1048576) * alpha[r] + beta[r]; // Jumping 20 iterations, the 'strike' count += steps[r]; } return count; } Th results maybe: 1. If n will become smaller after some steps, it's good. Just another ordinary hailstone sequence. 2. If there is a big 'loop', when calculating the smallest element in the loop it will run 'forever'. Larger element in the loop may become smaller and goto '1.' but that's OK. We only need to catch the smallest element in the loop. 3.If there is a number and it's hailstone sequence towards infinity, it will run 'forever', too. BTW, by looking into the table, I found most of the numbers get smaller after the 'first strike'; only a few of them 'survive' and grow bigger. Perhaps a sieve-like thing helps to get rid of lots of numbers to be computed. (Or perhaps this will hinder GPU computing; my HD7850 calculates steps of 700+ million numbers per second!) | |

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

Post to thread

Message boards :
Science :
The Collatz Conjecture

Copyright © 2018 Jon Sonntag; All rights reserved.