The Collatz Conjecture
log in

Advanced search

Message boards : Science : The Collatz Conjecture

Previous · 1 · 2 · 3 · Next
Author Message
Profile Slicker
Volunteer moderator
Project administrator
Project developer
Project tester
Project scientist
Avatar
Send message
Joined: 11 Jun 09
Posts: 2525
Credit: 740,580,099
RAC: 1
Message 7556 - Posted: 26 Apr 2010, 21:17:39 UTC - in response to Message 7491.

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?


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. ;-)

Scott
Send message
Joined: 2 Sep 10
Posts: 2
Credit: 26,807,918
RAC: 0
Message 9629 - Posted: 9 Sep 2010, 15:44:14 UTC

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

Thanks

Profile Slicker
Volunteer moderator
Project administrator
Project developer
Project tester
Project scientist
Avatar
Send message
Joined: 11 Jun 09
Posts: 2525
Credit: 740,580,099
RAC: 1
Message 9630 - Posted: 9 Sep 2010, 17:20:49 UTC - in response to Message 9629.

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

Thanks


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.

Scott
Send message
Joined: 2 Sep 10
Posts: 2
Credit: 26,807,918
RAC: 0
Message 9635 - Posted: 9 Sep 2010, 23:20:52 UTC - in response to Message 9630.

Thanks Slicker,

I am glad to hear there is more going on than crunching really large (small?) numbers.

Profile Konis
Send message
Joined: 21 Sep 10
Posts: 5
Credit: 82,577,944
RAC: 330,496
Message 9733 - Posted: 21 Sep 2010, 17:56:33 UTC

And thankfully Collaz is one site that uses my ATI-Graphics card to useful work,
Had i Know half year ago this.. *sniff*


But alas, ye pay for dumb head... whole body suffers...

Crunching numbers happily!
____________

tee.rasen@gmx.de
Send message
Joined: 19 Aug 10
Posts: 1
Credit: 736
RAC: 0
Message 9886 - Posted: 4 Oct 2010, 15:29:59 UTC

Since no one can store all results (number + number of steps to reach 1),
I wonder why we calculate the number of steps at all !?

For a given starting number 'a' we could stop counting the steps as soon as
the current value 'x' is lower than 'a'. We know each number below 'a' already
has been proven to reach 1.

pseudo code without optimisations (well, a bit C related):
x=a;
do {
if (x&1)
x=x*3+1; // odd
else
x=x/2; // even
} while (x>a);

Of course, we just have to detect a 'running away' and a 'loop' scenario.
'Best Of' data could be taken from the number of iterations.
We just need to calculate odd numbers from the WU ranges.
Optimisations should almost be the same as for the current implementation.

At least on 3 years old 2.2 GHz CPU, a current WU takes about 16 hours to calculate. The above code (without optimizations) is about 10 times faster...

What do you think ?

mfbabb2
Send message
Joined: 10 Nov 10
Posts: 7
Credit: 11,676
RAC: 0
Message 10254 - Posted: 11 Nov 2010, 0:33:45 UTC - in response to Message 9886.
Last modified: 11 Nov 2010, 0:34:40 UTC

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.

Reality is x < BASELINE, where BASELINE is upwardly adjusted with succeeding batches after all intervening numbers have been proven.
____________
Murphy

Profile Ethian
Volunteer tester
Send message
Joined: 29 Oct 09
Posts: 20
Credit: 6,649,825
RAC: 0
Message 10410 - Posted: 19 Nov 2010, 22:20:32 UTC - in response to Message 9886.

Since no one can store all results (number + number of steps to reach 1),
I wonder why we calculate the number of steps at all !?

For a given starting number 'a' we could stop counting the steps as soon as
the current value 'x' is lower than 'a'. We know each number below 'a' already
has been proven to reach 1.

pseudo code without optimisations (well, a bit C related):
x=a;
do {
if (x&1)
x=x*3+1; // odd
else
x=x/2; // even
} while (x>a);

Of course, we just have to detect a 'running away' and a 'loop' scenario.
'Best Of' data could be taken from the number of iterations.
We just need to calculate odd numbers from the WU ranges.
Optimisations should almost be the same as for the current implementation.

At least on 3 years old 2.2 GHz CPU, a current WU takes about 16 hours to calculate. The above code (without optimizations) is about 10 times faster...

What do you think ?

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 :)

Profile Slicker
Volunteer moderator
Project administrator
Project developer
Project tester
Project scientist
Avatar
Send message
Joined: 11 Jun 09
Posts: 2525
Credit: 740,580,099
RAC: 1
Message 10427 - Posted: 22 Nov 2010, 15:59:53 UTC - in response to Message 10422.

looks like the conjecture has been proved

http://www.occampress.com/solutionsubmit2.pdf


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

Profile Slicker
Volunteer moderator
Project administrator
Project developer
Project tester
Project scientist
Avatar
Send message
Joined: 11 Jun 09
Posts: 2525
Credit: 740,580,099
RAC: 1
Message 10429 - Posted: 22 Nov 2010, 19:38:23 UTC - in response to Message 10428.

thank you for the links :)
especially the last one about un-resolvability.
So basically what this project is doing is trying to plot a function Steps(x) ?
You cannot prove that Steps(x) is finite for every x so what is the point in doing the calculations ?


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. ;-)

Profile Misfit
Avatar
Send message
Joined: 3 Sep 10
Posts: 5
Credit: 43,720,971
RAC: 8
Message 10555 - Posted: 4 Dec 2010, 19:42:19 UTC

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

Profile Slicker
Volunteer moderator
Project administrator
Project developer
Project tester
Project scientist
Avatar
Send message
Joined: 11 Jun 09
Posts: 2525
Credit: 740,580,099
RAC: 1
Message 10582 - Posted: 7 Dec 2010, 19:26:08 UTC - in response to Message 10555.

No. Or, not without modifications. For example, starting with -25:
-25
-74
-37
-110
-55
-164
-82
-41
-122
-61
-182
-91
-272
-136
-68
-34
-17
-50
-25
LOOP!!!!

It probably works if you use 3x-1 instead of 3x+1 though.

Profile Dave
Avatar
Send message
Joined: 16 Jun 11
Posts: 10
Credit: 706,504
RAC: 0
Message 12502 - Posted: 25 Jun 2011, 0:43:16 UTC

Can we speed up the process?

I have noticed that iff the numbers 1..n are proven to be within the conjecture then so are the even numbers up to 2n, and alternate odd numbers up to n+n/3 (by the use of (3x+1)/2).

Do we have a value of n for which all previous numbers have been tested?

Is something like this already used? probably as it seems very obvious to me.

Profile Dave
Avatar
Send message
Joined: 16 Jun 11
Posts: 10
Credit: 706,504
RAC: 0
Message 12828 - Posted: 14 Oct 2011, 3:33:34 UTC - in response to Message 12502.

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

With parallel processing it is faster to test everything than to sort out the rubbish.

Consider a 50 processor GPU taking 1 second to test a set of 50 numbers, that is 200 numbers in 4 seconds, the 200 numbers could be sorted to yeild only 50 that need testing for 1 second but a GPU is not very good at that type of thing and would take, say, 5 seconds to do it. So without sorting it would take 4 seconds per 200 numbers, with sorting it would take 6 seconds. All timing is simplified for sake of the example.
____________

Profile Slicker
Volunteer moderator
Project administrator
Project developer
Project tester
Project scientist
Avatar
Send message
Joined: 11 Jun 09
Posts: 2525
Credit: 740,580,099
RAC: 1
Message 12938 - Posted: 15 Nov 2011, 14:45:46 UTC - in response to Message 12828.
Last modified: 15 Nov 2011, 14:46:53 UTC

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.

Jozef J
Send message
Joined: 2 Aug 13
Posts: 17
Credit: 1,343,479,849
RAC: 100,427
Message 18165 - Posted: 20 Dec 2013, 19:31:06 UTC - in response to Message 5974.

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

In a nutshell, the Collatz Conjecture states: For any number if the number is even divide by two else multiple by three and add one. Repeat. Eventually all numbers will reach 1.


It will be 1 in the end, i.e. the 1-cyle, if you are "honest" to yourself (or even "dishonest", it doesn't matter). This is why I think so:

As I understood the Collatz conjecture, it is in fact the mathematical expression of a quite old philosophical problem, the so-called Münchhausen Trilemma, also called Agrippa's Trilemma. Please compare these Wiki entries:

Collatz conjecture
Münchhausen Trilemma

The result "1" in the Collatz conjecture can be set equal to "The axiomatic argument, which rests on accepted precepts", which can also simply be named as Dogma (=subjective opinion).

I think the Münchhausen Trilemma simply describes the universe (from "within"). You (possibly) will not be able to "really" escape it (try to think how to escape, and you'll see what I mean). It will always give you the "one" as result and maybe that's not so bad (Metonymic: It tells you its subjective opinion "I'm there!").

In some way one may say what you are trying to do is to prove/disprove the Münchhausen Trilemma. This is a though job. My personal opinion is that you can't prove or disprove it, because it's even valid on itself and only describes the universe. It reveals that the universe exists "in some way" (expressed as 1 or 1-cycle as of Collatz conjecture) in direct opposition to what otherwise would be "the void" or simply nothing (my subjective assumption).

- By calculating for this project you are on the path of the "regressive (infinite) argument" (you will be in this state, as long as the project is running, which may be an infinite time, given the universe last infinitly (otherwise calculations may be stopped forcibly at the point in time, where the universe ceases to exist).

- There may also be a cycle of starting/stopping this project (or comparable projects), representing the circular argument.

- Finally, it may end "on purpose", saying something like "we probably proved it" or "we can not prove it" or similar statements which represent the axiomatic argument (dogma). This is very likly to happen, as, when it comes to human beings, this is the "natural" way of exiting the M.T.

This also shows that the real trap is, that you are already in the infinite path and/or circularity loop which you are searching for, by doing this search, which will always give a "quick" exit with the expected result (the 1).

I think this shows in the long run this problem is not mathematical, it's superimposed by the philosophical description. It's either "one" or void. It's about the universe itself, and maybe number crunching will not be enough to solve it. Of course it's very clear that I may be wrong with this assumption (it's also a dogma). On the other hand, if you find "something unexpected" this may be a very special event.

But maybe the answer is 42 ;)



But maybe the answer is 42 ;)


So this project is actually infinite, I like it..

Profile sosiris
Send message
Joined: 11 Dec 13
Posts: 123
Credit: 55,800,869
RAC: 0
Message 18257 - Posted: 10 Jan 2014, 3:53:26 UTC - in response to Message 10410.

Since no one can store all results (number + number of steps to reach 1),
I wonder why we calculate the number of steps at all !?

For a given starting number 'a' we could stop counting the steps as soon as
the current value 'x' is lower than 'a'. We know each number below 'a' already
has been proven to reach 1.

pseudo code without optimisations (well, a bit C related):
x=a;
do {
if (x&1)
x=x*3+1; // odd
else
x=x/2; // even
} while (x>a);

Of course, we just have to detect a 'running away' and a 'loop' scenario.
'Best Of' data could be taken from the number of iterations.
We just need to calculate odd numbers from the WU ranges.
Optimisations should almost be the same as for the current implementation.

At least on 3 years old 2.2 GHz CPU, a current WU takes about 16 hours to calculate. The above code (without optimizations) is about 10 times faster...

What do you think ?

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 :)


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!)

Previous · 1 · 2 · 3 · Next
Post to thread

Message boards : Science : The Collatz Conjecture


Main page · Your account · Message boards


Copyright © 2018 Jon Sonntag; All rights reserved.