The Collatz Conjecture
log in

Advanced search

Message boards : Science : The Collatz Conjecture

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: 2149
Credit: 513,523,980
RAC: 527,948
Message 1 - Posted: 11 Jun 2009, 17:05:05 UTC
Last modified: 30 Jun 2009, 10:12:22 UTC

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.

For example:

Start with 3.
3 -> 3 * 3 + 1 = 10
10 -> 10 / 2 = 5
5 -> 5 * 3 + 1 = 16
16 -> 16 / 2 = 8
8 -> 8 / 2 = 4
4 -> 4 / 2 = 2
2 -> 2 / 2 = 1
1 (finished)

It took 7 steps to reach 1.

Searches will start where the previous 3x+1@home project left off, beginning with the number 2,361,183,346,958,000,000,001

Note: This project is not for commercial purposes, nor it is related to any academic research. It was created because. That's it. Just because.

Profile Beyond
Avatar
Send message
Joined: 30 Jul 09
Posts: 203
Credit: 501,910,791
RAC: 13
Message 354 - Posted: 3 Aug 2009, 3:41:30 UTC

How long do you estimate this project will run?

Laura_Stevens
Send message
Joined: 28 Jul 09
Posts: 3
Credit: 136,171
RAC: 0
Message 421 - Posted: 6 Aug 2009, 20:49:04 UTC

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

I've got my goals here, and am heading back to regular programs, but if there is a use to this beyond purely academic conjecture, I may allocate further resources here.

Thanks,
Steve

Profile Slicker
Volunteer moderator
Project administrator
Project developer
Project tester
Project scientist
Avatar
Send message
Joined: 11 Jun 09
Posts: 2149
Credit: 513,523,980
RAC: 527,948
Message 539 - Posted: 12 Aug 2009, 23:38:11 UTC - in response to Message 421.

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

I've got my goals here, and am heading back to regular programs, but if there is a use to this beyond purely academic conjecture, I may allocate further resources here.

Thanks,
Steve


I'd love to tell you that it would cure cancer or something, but no. Per This article:

The 3n+1 conjecture is an example of pure mathematics. It has no known application. There may well be an application out there waiting to be discovered but that is not the reason mathematicians pursue such problems. In the words of one Researcher:

Some very interesting and useful mathematics can often be invented (or is it discovered?) while working on 'useless' problems. Of course, that's not the motivation for those who dedicate years of their lives to proving such conjectures, as I have. We know that we are looking directly at faces of the mind of God that man has never seen before, and that's enough to justify our lives, and hopefully to keep us away from the bottle for a while...
Who said 'useless'?

Laura_Stevens
Send message
Joined: 28 Jul 09
Posts: 3
Credit: 136,171
RAC: 0
Message 587 - Posted: 14 Aug 2009, 21:07:45 UTC - in response to Message 539.

Thank you Slicker,

I in no way meant that the goal was not worth pursuing. I would not have contributed what I have so far if I felt that. But my personal preferences lie elsewhere so I will be giving priorities to those projects pursuing goals I feel a bit more strongly about.

You got a great project here, and I will definitely keep it as an option for a backup project.

Thanks, and all the best !

Palo M.
Volunteer tester
Avatar
Send message
Joined: 24 Sep 09
Posts: 3
Credit: 79,936,915
RAC: 0
Message 2051 - Posted: 28 Sep 2009, 8:17:45 UTC

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

Profile Gipsel
Volunteer moderator
Project developer
Project tester
Send message
Joined: 2 Jul 09
Posts: 279
Credit: 5,940,143
RAC: 18,241
Message 2085 - Posted: 28 Sep 2009, 21:09:55 UTC - in response to Message 2051.

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

[..]
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...

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

Seth Hill
Send message
Joined: 7 Jan 10
Posts: 3
Credit: 2,623,463
RAC: 0
Message 5355 - Posted: 7 Jan 2010, 18:07:15 UTC - in response to Message 2051.

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]

Profile Slicker
Volunteer moderator
Project administrator
Project developer
Project tester
Project scientist
Avatar
Send message
Joined: 11 Jun 09
Posts: 2149
Credit: 513,523,980
RAC: 527,948
Message 5385 - Posted: 8 Jan 2010, 1:44:16 UTC - in response to Message 5355.
Last modified: 8 Jan 2010, 1:44:43 UTC

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


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

Profile Gipsel
Volunteer moderator
Project developer
Project tester
Send message
Joined: 2 Jul 09
Posts: 279
Credit: 5,940,143
RAC: 18,241
Message 5388 - Posted: 8 Jan 2010, 2:14:59 UTC - in response to Message 5355.
Last modified: 8 Jan 2010, 2:15:38 UTC

More than that, I'm also curious why the numbers being computed are so small.

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

Seth Hill
Send message
Joined: 7 Jan 10
Posts: 3
Credit: 2,623,463
RAC: 0
Message 5401 - Posted: 8 Jan 2010, 19:28:32 UTC - in response to Message 5385.

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!

TIR0
Send message
Joined: 11 Dec 09
Posts: 1
Credit: 5,856,502
RAC: 0
Message 5402 - Posted: 8 Jan 2010, 19:42:32 UTC

Seth Hill
Send message
Joined: 7 Jan 10
Posts: 3
Credit: 2,623,463
RAC: 0
Message 5406 - Posted: 8 Jan 2010, 21:02:33 UTC - in response to Message 5388.

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.

Profile Gipsel
Volunteer moderator
Project developer
Project tester
Send message
Joined: 2 Jul 09
Posts: 279
Credit: 5,940,143
RAC: 18,241
Message 5408 - Posted: 8 Jan 2010, 21:40:35 UTC - in response to Message 5401.
Last modified: 8 Jan 2010, 22:09:32 UTC

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

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?

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
107,159,749,967,996 total executed steps for 206,158,430,208 numbers

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.

Profile Gipsel
Volunteer moderator
Project developer
Project tester
Send message
Joined: 2 Jul 09
Posts: 279
Credit: 5,940,143
RAC: 18,241
Message 5409 - Posted: 8 Jan 2010, 21:58:22 UTC - in response to Message 5406.
Last modified: 8 Jan 2010, 22:10:19 UTC

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.

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

Profile Slicker
Volunteer moderator
Project administrator
Project developer
Project tester
Project scientist
Avatar
Send message
Joined: 11 Jun 09
Posts: 2149
Credit: 513,523,980
RAC: 527,948
Message 5410 - Posted: 8 Jan 2010, 22:02:18 UTC - in response to Message 5401.

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.

Profile Gipsel
Volunteer moderator
Project developer
Project tester
Send message
Joined: 2 Jul 09
Posts: 279
Credit: 5,940,143
RAC: 18,241
Message 5411 - Posted: 8 Jan 2010, 22:22:14 UTC - in response to Message 5410.
Last modified: 8 Jan 2010, 22:33:26 UTC

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

CmdrJameson
Send message
Joined: 3 Feb 10
Posts: 1
Credit: 0
RAC: 0
Message 5974 - Posted: 3 Feb 2010, 21:00:13 UTC

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

CLST
Send message
Joined: 10 Nov 09
Posts: 3
Credit: 11,085,993
RAC: 0
Message 5976 - Posted: 3 Feb 2010, 23:45:32 UTC

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.

The real worth is in getting there. Fermat's Last Theorem is not a useful theorem. It doesn't illuminate our lives with great truth. The proof of it however relied on and required the development of advanced mathematics which is in itself useful.

Similarly knowing the truth value of the Collatz Conjecture isn't in itself useful. The question simply never comes up! Ditto with the Goldbach Conjecture.

But who knows what the hell you have to do to prove it? That's the real question. And looking at the behavior of the algorithm on different numbers could be just the muse needed to prove it.

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.

Profile Paul D. Buck
Volunteer tester
Send message
Joined: 30 Aug 09
Posts: 412
Credit: 185,735,226
RAC: 0
Message 7491 - Posted: 25 Apr 2010, 4:41:40 UTC - in response to Message 5976.

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?

1 · 2 · 3 · Next
Post to thread

Message boards : Science : The Collatz Conjecture


Main page · Your account · Message boards


Copyright © 2014 Jon Sonntag; All rights reserved.