Largest number checked?
log in

Advanced search

Message boards : Science : Largest number checked?

1 · 2 · Next
Author Message
funkybomber
Send message
Joined: 3 Feb 10
Posts: 1
Credit: 54,660,251
RAC: 0
Message 6270 - Posted: 21 Feb 2010, 13:30:57 UTC

Ok, it's nice that we have a list of the numbers with the most steps to complete the collatz sequence, but shouldn't we also make public the highest integer that has been checked?

It's important to know that, since we all pretty much want to know how far we've collectively gone with our crunching. I think that's an extra incentive for all of us to go on...

Perhaps you could post the the highest integer checked on the "Collatz Best Results" page and periodically update it... (I'm not saying every day, but every once in a while would be nice).

Just my thoughts...

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 6273 - Posted: 21 Feb 2010, 19:40:18 UTC - in response to Message 6270.

Ok, it's nice that we have a list of the numbers with the most steps to complete the collatz sequence, but shouldn't we also make public the highest integer that has been checked?

It's important to know that, since we all pretty much want to know how far we've collectively gone with our crunching. I think that's an extra incentive for all of us to go on...

Perhaps you could post the the highest integer checked on the "Collatz Best Results" page and periodically update it... (I'm not saying every day, but every once in a while would be nice).

Just my thoughts...



The project started at 2,361,183,346,958,000,000,001. At the time I started writing this, 2,362,732,763,790,994,811,240 was the start of the next new WU. Therefore, Collatz volunteers have computed or are in the process of computing the steps for 1,549,416,832,994,811,239 numbers (1.5 quintillion numbers) since the project began.

In the last couple minutes, the next WU number has increased to 2,362,733,109,518,682,270,056. In other words, the actual number is pretty much useless.

I am working on something that will give more daily feedback though. Stay tuned...

Profile cenit
Send message
Joined: 11 Sep 09
Posts: 14
Credit: 22,679,602
RAC: 0
Message 6345 - Posted: 25 Feb 2010, 23:56:47 UTC

is there any reason about 2,361,183,346,958,000,000,001 as the starting number?

The old boinc project "3x+1@home" finished at 2,361,495,584,454,253,581,311 and started at 2,361,183,241,434,822,688,255...
i'm not understanding the lower limits... are we sure that lower number are limited in this conjecture?

Profile cenit
Send message
Joined: 11 Sep 09
Posts: 14
Credit: 22,679,602
RAC: 0
Message 6525 - Posted: 12 Mar 2010, 9:24:20 UTC - in response to Message 6345.

still no one has any idea?

Profile Ethian
Volunteer tester
Send message
Joined: 29 Oct 09
Posts: 20
Credit: 6,649,825
RAC: 0
Message 6589 - Posted: 17 Mar 2010, 9:37:01 UTC

Probably some home-testing from Slicker & Co, to cover the gap between the 3x+1@H and Collatz.
(I'm still amazed the starting numbers are this high... We only increased the upper bound by less than a percent... in 6 months time, using high-end GPU power, that was not available 10 years ago)

Profile Gipsel
Volunteer moderator
Project developer
Project tester
Send message
Joined: 2 Jul 09
Posts: 279
Credit: 77,436,650
RAC: 76,989
Message 6591 - Posted: 17 Mar 2010, 10:35:20 UTC

Who knows, maybe Slicker is planning something? ;)

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 6593 - Posted: 17 Mar 2010, 19:24:29 UTC - in response to Message 6345.

is there any reason about 2,361,183,346,958,000,000,001 as the starting number?

The old boinc project "3x+1@home" finished at 2,361,495,584,454,253,581,311 and started at 2,361,183,241,434,822,688,255...
i'm not understanding the lower limits... are we sure that lower number are limited in this conjecture?


The overlap was extremely cautious. While 3x+1 reported the highest steps for their finishing number, we don't know whether ALL workunits were returned from all of the previous numbers or not. Therefore some overlap was required. The overlap was also helpful in checking that the new apps matched the original 3x+1 findings. Was the overlap too large. Yes. I hadn't intended an overlap of that much, but by the time I realized it, we were about at the end of their findings anyway. That worked out OK because I wasn't 100% sure of the results with all the validate problems we had with the 1.xx apps.

[quote]... but shouldn't we also make public the highest integer that has been checked?[]/quote]

If every person completed every WU they returned successfully, then yes. The problem is that there are "holes" all over that are waiting for WUs to be resent. Some time out. Some are aborted. Some are from detaching. Regardless of the reason, just because someone got a new highest number in their WU, it doesn't mean that all the numbers lower than it have been checked.

For example, today we had a WU returned that found the highest steps for:
2,363,058,707,999,594,908,095

But we also had a WU today which returned the steps for:
2,362,904,828,965,727,392,679

Since there are "only" 200 billion numbers per WU, that equates to 769,000 workunits between them and yet they were returned on the same day. Could the same have happened in the original 3x+1? I don't know as I don't have all the stats, just the final list of numbers with lots of steps.

We will probably be going back and picking up some numbers that are in a range much lower than what we are currently working on now. It seems that there was a gap between where others left off and where the 3x+1 started. I don't know if that was random or agreed upon. I'd also like to come up with a way to guarantee that the results are valid w/o requiring a wingman.

When? Not this month. I'm up to my eyeballs in work with my second job as I (stupidly - hindsight being 20/20) decided an upgrade for the report software would fix some problems (which it did) but only to discover it now formats the dates differently and the memory deallocation has changed. So, I now have 200 reports to upgrade and test which doesn't leave much time for Collatz other than just keeping it running. Hopefully, I'll have more time in a couple weeks to start working on this (and the Collatz server upgrade).

Vid Vidmar*
Send message
Joined: 21 Jul 09
Posts: 24
Credit: 22,494,514
RAC: 0
Message 6842 - Posted: 29 Mar 2010, 19:32:21 UTC - in response to Message 6593.
Last modified: 29 Mar 2010, 19:34:05 UTC

I've been thinking about this search. Are we looking through numbers one by one, or do you do some kind of sieving beforehand (most obvious that come to mind are powers of 2)? If not, would it make sense to store numbers found during a search that are bigger than the starting number, so that they can be eliminated from later searches?
Just a thought.
BR

[edit]spelling and grammar[/edit]
____________

Profile Gipsel
Volunteer moderator
Project developer
Project tester
Send message
Joined: 2 Jul 09
Posts: 279
Credit: 77,436,650
RAC: 76,989
Message 6845 - Posted: 29 Mar 2010, 21:41:46 UTC - in response to Message 6842.
Last modified: 29 Mar 2010, 21:44:02 UTC

Are we looking through numbers one by one,

Yes.

or do you do some kind of sieving beforehand (most obvious that come to mind are powers of 2)?

No. As I said some time before, there are virtually no powers of 2 in the WUs (no WU calculated up to date by this project contained one). There exist some sieving algorithms, but they are not very effective for searching delay time records (longest path to 1). But they could be put to some use for reducing the numbers of candidates one needs to check if one is only interested in disproving the conjecture or to search for the largest excursion to large values. And one needs to be extremely effective with such a sieve, as simply determining the numbers of steps down to one is really fast with the streamlined algorithm used here (a HD5870 can do it for approximately 600 million numbers per second!). So the checks for excluding some numbers from the search would effectively slow down the calculation in most cases.

If not, would it make sense to store numbers found during a search that are bigger than the starting number, so that they can be eliminated from later searches?

I don't hink so. As a single WU checks more than two hundred billion numbers, no database on the planet will be able to handle the amount of data that would be necessary, let alone that the data transfers to all the hosts would be prohibitive anyway.

mda_
Send message
Joined: 1 Jun 10
Posts: 11
Credit: 41,233
RAC: 0
Message 8209 - Posted: 1 Jun 2010, 22:49:44 UTC - in response to Message 6845.

To jump ahead to arbitrarily high numbers :)

#!/usr/bin/env python # DonMorrison at gmail import sys, gmpy def collatz(z): cnt = gmpy.mpz(0) while z != 1: cnt += 1 #print '%d' % z if z % 2:#odd z = 3 * z + 1 else:#even z = z / 2 print 'Total iterations before reaching 1: %d' % cnt collatz(gmpy.mpz(sys.argv[1]))

Profile Ethian
Volunteer tester
Send message
Joined: 29 Oct 09
Posts: 20
Credit: 6,649,825
RAC: 0
Message 8331 - Posted: 11 Jun 2010, 9:17:00 UTC

This too counts completely back to 1.
I think there's 2 simplifications that can be made, if you only care about checking the conjecture.
a. Stop counting when the number reaches a value below starting level. Say we test 17, which goes to 52, 26, 13, and since we started at 0, 13 was already tested, and confirmed not to be an exception. Therefore, you can stop right there, instead of calculating the other steps.
b. Skip all the even numbers, since they're going down below starting value in their first step.
The drawback is that you loose the records, so you don't know how long exactly it took to get to 1.

mda_
Send message
Joined: 1 Jun 10
Posts: 11
Credit: 41,233
RAC: 0
Message 8340 - Posted: 12 Jun 2010, 4:48:08 UTC - in response to Message 8331.

Ethian: Yes, there are various tradeoffs you can make depending on your goals. The goal of my post was to let the curious check an arbitrary number easily. Python is an easy and interactive means to do so -- that script runs on Ubuntu if you just install the python-gmpy package, or on MacOSX with the py-gmpy package (macports). Of course, it's not designed to be particularly fast.

I don't know what kind of stats the admins keep, or if they are mostly interested in the search for a counter-example to the conjecture.

Profile cenit
Send message
Joined: 11 Sep 09
Posts: 14
Credit: 22,679,602
RAC: 0
Message 8414 - Posted: 17 Jun 2010, 6:59:28 UTC - in response to Message 8331.

The drawback is that you loose the records, so you don't know how long exactly it took to get to 1.

I do not think that Slicker keeps the records about each and every number checked. In fact, each wu checks millions of numbers but reports back about the steps of the longest one...

Profile Ethian
Volunteer tester
Send message
Joined: 29 Oct 09
Posts: 20
Credit: 6,649,825
RAC: 0
Message 8430 - Posted: 17 Jun 2010, 16:47:25 UTC

I know that he won't even try to keep a database with how long the numbers take to get to 0, but you can't even know which one takes longest to 0, only which one takes longest to get below the original value. Depending on that number, it may or may not take ages to get to the 4-2-1-cycle.
@Don : it's a nice script, and indeed, depending on your desires, it does the job. However since i'm (personally) most interested in proving (by trial) that the theorem is correct, simply rushing through all the numbers as fast as possible will do. That means assembly magic if possible, and else a nice and quick C(++) or Fortran routine does the job. I think your script could be done in Fortran just as easy ;)

pseudocode :
integer n
do n=5,10000
if(n.eq. 4) then
write(iwr,*)reached 4 for n=',n
enddo
endif
if(n=odd) n=n*3+1 ! *
else n=n/2
endif
enddo

* This bit is trickiest, and the limiting step. Doing it bitwise would make this a hell of a lot easier (last bit zero = delete last bit, else multiply by 3, last bit = 0 and the next bit +1).However... I have no idea how to handle that, so I trust Slicker that he found the faster way ;)

mda_
Send message
Joined: 1 Jun 10
Posts: 11
Credit: 41,233
RAC: 0
Message 8436 - Posted: 17 Jun 2010, 21:21:44 UTC - in response to Message 8430.

Ethian: Thanks for the enthusiasm and the compliment! One point of difference: you cannot prove the conjecture is true by trying all positive numbers, since they are infinite.

When I got my CS Degree ('02), I was taught there are only 3 kinds of proofs:
1) Proof by definition
2) Proof by counter-example
3) Proof by induction (inference from axioms)

There was (and perhaps still is) debate about Diagonalization being a 4th method, or just another case of induction.

What you can do, by checking higher and higher integers, is look for a counter-example (a proof that the conjecture is false).

Profile Ethian
Volunteer tester
Send message
Joined: 29 Oct 09
Posts: 20
Credit: 6,649,825
RAC: 0
Message 8541 - Posted: 24 Jun 2010, 17:16:31 UTC

ty ;)
I know this is not 'proof', but it's the best we can do. If it can't be proven wrong, i simply assume it is correct. Checking all numbers would be silly, but collecting data on the progress would be nice, since i assume (again) that the amount of steps to reach 1 and the size of the number are correlated in a somewhat linear way. Why? Since there is no way to determine whether this number or the next will have a longer path to 1, chances are that the numbers higher up are coming to a random number as well. Adding all those chances should mean the average down-to-1-time is doubled when number size doubles.Checking is easy, the WU-time should simply keep up with the size of the numbers on test ;)

mda_
Send message
Joined: 1 Jun 10
Posts: 11
Credit: 41,233
RAC: 0
Message 8546 - Posted: 24 Jun 2010, 20:39:02 UTC - in response to Message 8541.

Here's a short Sage (python) program that searches for counterexamples, and displays a graph. It assumes your low input parameter will be 3 mod 4 since a counter-example is supposed to be 3 mod 4 (citation on wikipedia or mathworld.) I could be wrong, I skimmed it. :-) It could be more efficient...but it makes more pretty graphs.

http://www.sagemath.org/download.html

def collatz(z): i = 0 zin = z while z > 1: i = i + 1 if z % 2: z = 3 * z + 1 else: z = z / 2 return (zin, i) def mys(lo, hi): lst = [] while lo < hi: lst.append(collatz(lo)) lo += 4 return list_plot(lst) #mys(3+2^58, 3+2^59)

mda_
Send message
Joined: 1 Jun 10
Posts: 11
Credit: 41,233
RAC: 0
Message 8577 - Posted: 26 Jun 2010, 3:26:11 UTC - in response to Message 8546.

Ethian: it's log-linear, or at least appears to be for as far as can be quickly computed. It's easy to modify that small program I posted to change the x-axis to log(input). I misspoke though, it, of course, does not detect non-trivial cycles (counter-examples)...so it's just for fun.... :)

mda_
Send message
Joined: 1 Jun 10
Posts: 11
Credit: 41,233
RAC: 0
Message 8660 - Posted: 1 Jul 2010, 17:46:27 UTC

Slicker: What's the highest work unit received to date, can ya share? Taking the numbers from your posts above, it sounds like we're working in the [2^71,...) range.

(float(log(2361183346958000000001)/log(2)),float(log(2362904828965727392679)/log(2)))
-> (71.000000064475202, 71.001051515495149)

I'm sure the OEIS would love a "b-file" contribution. :-)

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 11191 - Posted: 28 Jan 2011, 22:31:21 UTC - in response to Message 8660.
Last modified: 28 Jan 2011, 23:13:45 UTC

Slicker: What's the highest work unit received to date, can ya share? Taking the numbers from your posts above, it sounds like we're working in the [2^71,...) range.

(float(log(2361183346958000000001)/log(2)),float(log(2362904828965727392679)/log(2)))
-> (71.000000064475202, 71.001051515495149)

I'm sure the OEIS would love a "b-file" contribution. :-)


The new workunits will now contain the starting number and the length in the name. For example, if the WU is named collatz_2367871917423103551848_824633720832 that means it starts at 2,367,871,917,423,103,551,848 and will be checking 824,633,720,832 numbers. The last _0, _1, _2, etc. are the number of times it has been sent. _0 and _1 are normal. You will only see _2, _3, and higher when one of the first two errors out, times out, or is aborted.

1 · 2 · Next
Post to thread

Message boards : Science : Largest number checked?


Main page · Your account · Message boards


Copyright © 2018 Jon Sonntag; All rights reserved.