Project OGR
OGR
Clients and proxies that are capable of working on OGR capable of working on OGR are available for most platforms. Download and install the latest clients to participate in this new project. There is also a section in our FAQ-o-Matic regarding a number of frequently asked questions about the OGR project.
You can find out more information about our network speed at our OGR statistics page.
If you have any technical support questions regarding the operations of your distributed.net client, then please click here to send mail to help@distributed.net. Be sure to also check out the FAQ-o-Matic to see if your question has already been answered.
What is a Golomb Ruler anyway?
In mathematics, the term "Golomb Ruler" refers to a set of non-negative integers such that no two distinct pairs of numbers from the set have the same difference. Conceptually, this is similar to a ruler constructed in such a way that no two pairs of marks measure the same distance. An Optimal Golomb Ruler (OGR) is the shortest Golomb Ruler possible for a given number of marks. However, finding (and proving) OGR's becomes exponentially more difficult as the number of marks increases, and it is for this reason that we have turned to the web for help in finding the OGR's with 24 and more marks.
Golomb rulers are named after Dr. Solomon W. Golomb, a professor of Mathematics with a special interest in combinatorial analysis, number theory, coding theory and communications. Dr. Golomb also has an interest in mathematical games and puzzles, having been a contributor to many columns in the Scientific American "Mathematical Games". OGR's have many applications including sensor placements for X-ray crystallography and radio astronomy. Golomb rulers can also play a significant role in combinatorics, coding theory and communications, and Dr. Golomb was one of the first to analyze them for use in these areas.
A Golomb ruler is a way to place marks along a line such that each pair of marks measures a unique linear distance. Here is a Golomb ruler with five marks:
| | | | | 0 1 4 9 11
The number below the mark is the distance from the left edge. The length of this ruler is 11, and it happens to be one of the two shortest such rulers with five marks. The other ruler has marks at positions 0, 3, 4, 9, and 11. (The mirror images of these two rulers, 0, 2, 7, 10, 11 and 0, 2, 7, 8, 11, are also optimal Golomb rulers. Usually just one of each mirror-image pair is mentioned.)
You can check that the above ruler is indeed Golomb by writing out a table of all the pairs of marks and their respective distances:
| Mark1 | Mark2 | Distance |
|---|---|---|
| 0 | 1 | 1 |
| 0 | 4 | 4 |
| 0 | 9 | 9 |
| 0 | 11 | 11 |
| 1 | 4 | 3 |
| 1 | 9 | 8 |
| 1 | 11 | 10 |
| 4 | 9 | 5 |
| 4 | 11 | 7 |
| 9 | 11 | 2 |
Note that there are no duplicated distances in the third column. There is also no distance 6, but that is okay because Golomb rulers don't have to measure each distance, only distinct distances.
The goal of "optimizing" Golomb rulers is to get them as short as possible, while not duplicating any measured distances. The two 5-mark rulers above are optimal.
Golomb rulers are usually characterized by their differences, rather than absolute distances as in the above diagram. So the above ruler would be 1-3-5-2 (sometimes this is written as 0-1-3-5-2 but the leading zero is often dropped).
For example, the current best known 21-mark ruler is the following:
2-22-32-21-5-1-12-34-15-35-7-9-60-10-20-8-3-14-19-4
James B. Shearer has compiled a list of all the best known Golomb rulers up to 150 marks. If you're comparing rulers, note that the 21-mark ruler listed on James' page is the mirror image of the one above.
Unfortunately, the search for OGRs becomes exponentially more difficult as the number of marks increases (similar to what mathematicians call "Np complete" problems ... like the infamous Traveling Salesman optimization).
General Links Pertaining to OGR
- Wikipedia's article
- MathWorld's description of Golomb Rulers
- Greg Hewgill's technical OGR information page and his plan file
- The previous OGR Effort (OGR-20, -21, -22, and -23)
- James B. Shearer's list of best known Golomb rulers (up to 150 marks) and his main Golomb page.
- Lloyd Miller's listing of more best known Golomb rulers and other information.
- William T. Rankin's web page describing his master's project involving the distributed search of OGR-17, -18, and -19
- Stephen Wayne Soliday's paper on a Genetic Algorithm for Near Optimal Golomb Rulers
- D. Kent Freeman paper abstract on the Similarity of Maximizing Irregularity and Solving Golomb Rulers
Other hardcopy-only OGR research references
- J. P. Robinson and A. J. Bernstein, "A class of binary recurrent codes with limited error propagation," IEEE Trans. Inform. Theory, vol. IT-13, no. 1, pp. 106-113, 1967.
- M. D. Atkinson, N. Santoro, and J. Urrutia, "Integer sets with distinct sums and differences and carrier frequency assignments for nonlinear repeaters", IEEE Transactions On Communications, vol. Com-34, no. 6, pp. 614-617, June 1986.
- A. W. Lam and D. V. Sarwate, "On optimum time hopping patterns", IEEE Transactions on communications, vol. 36, no. 3, pp. 380-382, March 1988.
- A.Dollas, W.T.Rankin and D.McCracken published "A New Algorithm for Golomb Ruler Derivation and proof of the 19 Mark Ruler" in IEEE Transactions On Information Theory (January, 1998, Volume 44, Number 01).