OGR-24 officially solved

[wirthi]

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!

[IronBits]

:|party|:
We took 14th place! :D
:cheers:

[Death]

http://n0cgi.distributed.net/cgi/planarc.cgi?user=gregh&plan=2004-11-01.23:48

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

================================

me ends at

12 Dead J. Dona _|_ [Ukraine RC5] 15-Jul-2000 20-Oct-2004 1559 2,140,918

a few days to top10 :cry:

and a week for catch you

14 Free-DC 30-Dec-2002 21-Oct-2004 662 27 3,486,857 0
15 Ukraine RC5 13-Jul-2000 29-Oct-2004 1,570 93 3,261,813 0

:trash:

[FoBoT]

extra :cool:

:drums: