TOPICS
Search

Golomb Ruler


GolombRulers

An n-mark Golomb ruler is a set of n distinct nonnegative integers (a_1,a_2,...,a_n), called "marks," such that the positive differences |a_i-a_j|, computed over all possible pairs of different integers i,j=1, ..., n with i!=j are distinct.

Let a_n be the largest integer in an n-mark Golomb ruler. Then an n-mark Golomb ruler (0,...,a_n) is optimal if

1. There exists no other n-mark Golomb rulers having smaller largest mark a_n, and

2. The ruler is written in canonical form as the "smaller" of the equivalent rulers (0,a_2,...,a_n) and (0,...,a_n-a_2,a_n), where "smaller" means the first differing entry is less than the corresponding entry in the other ruler.

In such a case, a_n is the called the "length" of the optimal n-mark ruler.

Thus, (0, 1, 3) is the unique optimal 3-mark Golomb ruler modulo reversal (i.e., (0, 2, 3) is considered the same ruler).

For example, the set (0, 1, 3, 7) is 4-mark Golomb ruler since its differences are (1=1-0, 2=3-1, 3=3-0, 4=7-3, 6=7-1, 7=7-0), all of which are distinct. However, the unique optimal Golomb 4-mark ruler is (0, 1, 4, 6), which measures the distances (1, 2, 3, 4, 5, 6) (and is therefore also a perfect ruler). As a further example, it turns out that the length of an optimal 6-mark Golomb ruler is 17. In fact, there are a total of four distinct 6-mark Golomb rulers, all of length 17, one of which is given by (0, 1, 4, 10, 12, 17).

Rulers may be indicated in either by giving the distances at which the marks occur, e.g., (0, 1, 3, 7) in the above example, or by the differences between successive marks, which in this case would be [1,2,4].

The lengths of the optimal n-mark Golomb rulers for n=2, 3, 4, ... are 1, 3, 6, 11, 17, 25, 34, ... (OEIS A003022, Vanderschel and Garry). Although the lengths of the optimal n-mark Golomb rulers are not known for n>=25, the known 21-, 22-, 23-, and 24-mark rulers were proved optimal by the Golomb ruler search project between 1998 and 2004. In particular, in 1967, J. P. Robinson and A. J. Bernstein found the 24-mark ruler (0, 9, 33, 37, 38, 97, 122, 129, 140, 142, 152, 191, 205, 208, 252, 278, 286, 326, 332, 353, 368, 384, 403, 425), which was verified to be optimal on Nov. 1, 2004 by a 4-year computation on distributed.net that performed as exhaustive search through 555529785505835800 rulers (distributed.net 2004). In 1984, M. D. Atkinson and A. Hassenklover found the 25-mark ruler (0, 12, 29, 39, 72, 91, 146, 157, 160, 161, 166, 191, 207, 214, 258, 290, 316, 354, 372, 394, 396, 431, 459, 467, 480). A follow-up eight year distributed.net project for the 25-mark ruler, assisted by 124387 people, announced on Oct. 25, 2008 that the 25-mark ruler was optimal.

The number N(n) of inequivalent optimal n-mark Golomb rulers for n=2, 3, ... are 1, 1, 1, 2, 4, 5, 1, 1, 1, ... (OEIS A036501), and the number of distances in an optimal n-mark ruler is given by the triangular number T_n=n(n-1)/2, so for n=1, 2, ..., the first few are 0, 1, 3, 6, 10, 15, ... (OEIS A000217).

The following table gives a complete list of optimal Golomb rulers for small n. A more complete table is maintained by J. B. Shearer.

nN(n)optimal rulers
21(0, 1)
31(0, 1, 3)
41(0, 1, 4, 6)
52(0, 1, 4, 9, 11), (0, 2, 7, 8, 11)
64(0, 1, 4, 10, 12, 17), (0, 1, 4, 10, 15, 17), (0, 1, 8, 12, 14, 17),
(0, 1, 8, 11, 13, 17)
75(0, 1, 4, 10, 18, 23, 25), (0, 2, 3, 10, 16, 21, 25), (0, 1, 11, 16, 19, 23, 25),
(0, 1, 7, 11, 20, 23, 25), (0, 2, 7, 13, 21, 22, 25)
81(0, 1, 4, 9, 15, 22, 32, 34)

See also

Perfect Difference Set, Perfect Ruler, Ruler, Taylor's Condition, Weighing

Explore with Wolfram|Alpha

References

Atkinson, M. D.; Santoro, N.; and Urrutia, J. "Integer Sets with Distinct Sums and Differences and Carrier Frequency Assignments for Nonlinear Repeaters." IEEE Trans. Comm. 34, 614-617, 1986.Colbourn, C. J. and Dinitz, J. H. (Eds.). CRC Handbook of Combinatorial Designs. Boca Raton, FL: CRC Press, p. 315, 1996.Dewdney, A. K. "Computer Recreations." Sci. Amer. 253, 16, June 1985.Dewdney, A. K. "Computer Recreations." Sci. Amer. 254, 20, Mar. 1986.distributed.net. "Project OGR." http://www.distributed.net/ogr/.distributed.net. "distributed.net Is Proud to Announce the Completion of OGR-24." Nov. 1, 2004. http://n0cgi.distributed.net/cgi/planarc.cgi?user=nugget&plan=2004-11-01.10:24.Golomb, S. W. "How to Number a Graph." In Graph Theory and Computing (Ed. R. C. Read). New York: Academic Press, pp. 23-37, 1972.Guy, R. K. "Modular Difference Sets and Error Correcting Codes." §C10 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 118-121, 1994.Hewgill, G. "distributed.net OGR Project." http://www.hewgill.com/ogr/.Kotzig, A. and Laufer, P. J. "Sum Triangles of Natural Numbers Having Minimum Top." Ars. Combin. 21, 5-13, 1986.Lam, A. W. and Sarwate, D. V. "On Optimum Time Hopping Patterns." IEEE Trans. Comm. 36, 380-382, 1988.Miller, L. "Golomb Rulers." http://www.cuug.ab.ca/~millerl/g3-records.html.Pegg, E. Jr. "Math Games: Rulers, Arrays, and Gracefulness." Nov. 15, 2004. http://www.maa.org/editorial/mathgames/mathgames_11_15_04.html.Robinson, J. P. and Bernstein, A. J. "A Class of Binary Recurrent Codes with Limited Error Propagation." IEEE Trans. Inform. Th. 13, 106-113, 1967.Shearer, J. B. "Golomb Rulers." http://www.research.ibm.com/people/s/shearer/grule.html.Sloane, N. J. A. Sequences A000217/M2535, A003022/M2540, A036501, and A039953 in "The On-Line Encyclopedia of Integer Sequences."Sloane, N. J. A. and Plouffe, S. Figure M2540 in The Encyclopedia of Integer Sequences. San Diego, CA: Academic Press, 1995.Vanderschel, D. and Garry, M. "In Search of the Optimal 20, 21, & 22 Mark Golomb Rulers." http://members.aol.com/golomb20/.

Referenced on Wolfram|Alpha

Golomb Ruler

Cite this as:

Weisstein, Eric W. "Golomb Ruler." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GolombRuler.html

Subject classifications