:: 01-Nov-2004 10:24 GMT (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!