http://www.americanscientist.org/template/AssetDetail/assetid/20836/page/3
Collective Wisdom
The world is not panting in desperate need of better Golomb rulers,
and yet these combinatorial curiosities do have practical uses. For
example, in setting up an interferometer for radio astronomy,
placing the antennas on the marks of a Golomb ruler maximizes the
recovery of information about the phases of the signals received.
Many good Golomb rulers have been found by trial-and-error, but
proving them optimal (or finding a better ruler if one exists) is
computationally expensive. In 1995 a dozen workstations took four
CPU-years to prove there is no 19-mark ruler shorter than 246 units.
The computation was done by Apostolos Dollas, William T. Rankin and
David McCracken of Duke University.
In 1996 David Vanderschel and Mark Garry, who had both worked on
Golomb rulers independently, merged their ideas in a program called
GVANT, which turned out to be significantly more efficient than
earlier programs. They quickly confirmed the known results for
rulers of up to 19 marks, but even with their highly optimized
algorithm a search for the best 20-mark ruler was a formidable
undertaking. They therefore sought Internet collaborators. With
seven helpers it took about half a year to prove that a 20-mark
ruler of length 283 is optimal.
In the spring of 1997 Vanderschel and Garry turned to the 21-mark
ruler, for which the shortest known arrangement is 333 units long.
For this ruler a naive algorithm would have to check more than 1030
arrangements of the marks; GVANT prunes the number of cases to about
1015. Roughly 100 volunteers have pitched in to help, but after a
year's searching there is still plenty of work left for latecomers.
Out of 1,200 trillion arrangements to be checked, fewer than 200
trillion have been examined so far.
ID Number: A003022 (Formerly M2540) URL:
http://www.research.att.com/projects/OEIS?Anum=A003022 Sequence:
1,3,6,11,17,25,34,44,55,72,85,106,127,151,177,199,216,246,
283,333,356,372
Name: Length of shortest Golomb ruler with n marks.
Comments: a(n) is the least integer such that there is an n-element
set of integers between 0 and a(n), the sums of pairs (of not
necessarily distinct elements) of which are distinct.
The concept of Golomb rulers was first introduced by W. C. Babcock
in 1952. Today the rulers are named by Solomon W. Golomb, a
professor of Mathematics and Electrical Engineering at the
University of Southern California.
A Golomb ruler is defined as a ruler which has marks at integer
locations such that the distance between any two marks of the ruler
is unique. Normally the first mark of the ruler is set on position 0
and the position of the right-most mark is called the length of the
ruler. Most interesting are rulers having smallest possible length n
for a given number m of marks. Such rulers are called optimum Golomb
rulers (OGR) and they are used in a variety of real-world
applications such as Communications and Radio astronomy, X-Ray
Crystallography and Self-Orthogonal Codes. If each of the distances
1, 2, ..., n of a Golomb ruler of length n is measured exactly once
the ruler is called perfect.
It's not too difficult to show that perfect Golomb rulers exist only
for ruler lengths up to four marks. For five marks and more only
optimum Golomb rulers exist and the search for such rulers has to be
done by exhaustive search. Today all optimum Golomb rulers up to 23
marks are known and in July 2000 distributed.net started the web
search for the 24 and 25 OGR's.
In the table below all known optimum Golomb rulers are listed. Note
that the mirror image of a optimum Golomb ruler is also optimum and
only one of the two mirror rulers is mentioned in the table.
http://www.wschnei.de/number-theory/golomb-rulers.html
0,0,0,1,2,4,6,8,10,17,19,28,36,46,57,63,63,75,93,123,125,119
0,1,4,10,12,17
1,2,5,11,19,24,26
0,1,4,9,15,22,32,34
0,1,5,12,25,27,35,41,44
0,1,6,10,23,26,34,41,53,55
0,1,4,13,28,33,47,54,64,70,72
0,2,6,24,29,40,43,55,68,75,76,85
0,2,5,25,37,43,59,70,85,89,98,99,106
0,4,6,20,35,52,59,77,78,86,89,99,122,127
0,4,20,30,57,59,62,76,100,111,123,136,144,145,151
0,5,7,17,52,56,67,80,81,100,122,138,159,165,168,191,199
http://home.planet.nl/~faase009/Ha_sparse_rulers.html
http://library.wolfram.com/infocenter/Articles/3820/
In case you don't already receive this news, the OGR-24 project has
been completed:
Cheers,
Ludovic
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!