A Golomb ruler is a set of Nonnegative integers such that all pairwise Positive differences are distinct. The optimum Golomb ruler with marks is the Golomb ruler having the smallest possible maximum element (``length''). The set (0, 1, 3, 7) is an order four Golomb ruler since its differences are (, , , , , ), all of which are distinct. However, the optimum 4-mark Golomb ruler is (0, 1, 4, 6), which measures the distances (1, 2, 3, 4, 5, 6) (and is therefore also a Perfect Ruler).

The lengths of the optimal -mark Golomb rulers for , 3, 4, ... are 1, 3, 6, 11, 17, 25, 34, ... (Sloane's A003022, Vanderschel and Garry). The lengths of the optimal -mark Golomb rulers are not known for .

**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.

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.

Lam, A. W. and D. V. Sarwate, D. V. ``On Optimum Time Hopping Patterns.'' *IEEE Trans. Comm.* **36**, 380-382, 1988.

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.

Sloane, N. J. A. Sequence
A003022/M2540
in ``An On-Line Version of the Encyclopedia of Integer Sequences.''
http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S.
*The Encyclopedia of Integer Sequences.* San Diego: Academic Press, 1995.

Vanderschel, D. and Garry, M. ``In Search of the Optimal 20 & 21 Mark Golomb Rulers.'' http://members.aol.com/golomb20/.

© 1996-9

1999-05-25