[plans] distributed.net .plan update

Plan Man plans at nodezero.distributed.net
Mon Nov 1 19:00:04 EST 2004


distributed .plan updates in the last 24 hours:
---

nugget :: 01-Nov-2004 10:24 CST (Monday) ::

distributed.net is proud to announce the completion of OGR-24!

Four years ago, distributed.net users undertook the search for the optimal
24 mark Golomb Ruler.  This year sees the successful conclusion of that
effort.  We have proven conclusively by the exhaustive search of all
possible rulers that the currently best known ruler is indeed the Optimal
one.

More precisely it is:
  24/9-24-4-1-59-25-7-11-2-10-39-14-3-44-26-8-40-6-21-15-16-19-22

This shortest ruler was found by two independent computers. The initial
report was received on May 24th, 2004 and a second, matching result was
returned on July 3rd, 2004. However it was not until the final stub was
returned and verified that could we rule out the possibility of a
still-shorter ruler.  This final stub was returned October 13th, 2004
drawing to a close the complete search of all possible stubs.  Due to the
nature of an exhaustive search, distributed.net users have also proven that
the above solution is unique (the ruler's mirror notwithstanding).

This project was first announced in 1998, started in February 2000, and is
now concluded in 2004.  Although 4 years may seem like a long time, the
search was no trivial task. No fewer than 555,529,785,505,835,800 rulers
were checked during that time.  Moreover, a second pass of all rulers was
done to rule out (heh) any errors.  Additionally a small oversight in the
beginning of the project caused several rulers to be excluded from the
initial search. These were the subject of the much discussed Phase 2
(rulers with initial marks > 70). Incidentally the optimal ruler was
amongst these.  ("9+24+4+1+59 > 70") The double phase, phase 2 and their
verification each required additional structural changes which also
contributed to the overall 4 year duration.

Note that distributed.net users continue to pursue the solution to the
OGR-25 project which began in parallel with OGR-24.  We have currently
completed 10-15% of OGR-25 phase 2 which is about 65% overall. 

To celebrate the successful end of yet another distributed.net project all
our contributors are invited for a drink...when we find a place large
enough to host the 41,805 people that participated in this particular
distributed effort. :)

The shortest ruler was first found by Matt Richards (Matt_R in
#distributed).  It was then confirmed by Mitsuru Aoki of the SEGA Users
Group Team (#1958).  The final stub was returned by Sebastian "Pax"
Schmitz.  We'll be sending them some free distributed.net swag and shirts
for their noteworthy contributions to the project.

Related Links:
 - http://www.distributed.net/ogr/
 - http://n0cgi.distributed.net/statistics/ogr/ogr24-all-nodes-day.png
 - http://n0cgi.distributed.net/statistics/ogr/ogr24p2-percent.png

Thank you all and keep those computers busy!


gregh :: 01-Nov-2004 23:48 GMT (Monday) ::

With the completion of OGR-24, I thought I would draw a diagram of the
best ruler and talk a little bit about what it means.

The diagram can be found here: http://hewgill.com/ogr/ogr24.png

The top portion shows the ruler laid out to scale. The numbers (9, 24,
4, etc) are the distances between each mark. For various lengths
between 1 and 425 units, there is a unique way to measure that distance
using the ruler. The bottom section of the diagram shows how to use the
ruler to measure each possible distance.

For example, the distances 1, 2, 3, and 4 are trivially measured by
lining up with the corresponding distances in the ruler. 5 must be
measured by combining the 4 and the 1 (which are right next to one
another). 6 through 11 are easy because those distances are already
marked on the ruler, 12 must be measured by combining 10 and 2 (the
numbers are a little hard to read around that area, but you can compare
with the final published ruler).

The part that makes this a Golomb ruler is that there is exactly ONE
way to measure each distance. You can't find any other combination of
distances in the given ruler that add up to say, a distance of 100,
except for 39+14+3+44. And the optimal part is that this is the
SHORTEST ruler (with respect to the overall length of 425) that offers
only one way to measure each distance. There exist longer rulers that
also have a unique way to measure each distance, and there are also
shorter rulers that end up having more than one way to measure some
distances. This ruler satisfies both properties.

Note that not every distance between 1 and 425 can be measured with
this ruler. It happens that 128 is the first distance that can't be
measured with the given ruler. In all, only 276 of the distances
between 1 and 425 can be measured. The gaps in the lower portion of the
diagram indicate distances that can't be measured.

Congratulations to all the participants who donated CPU time to prove
this result!



More information about the plans mailing list