An 
-mark Golomb ruler is a set of 
distinct nonnegative integers 
, called "marks," such that the positive
differences 
,
computed over all possible pairs of different integers 
, ..., 
with 
are distinct.
Let 
be the largest integer in an 
-mark Golomb ruler. Then an 
-mark Golomb ruler 
is optimal if
1. There exists no other 
-mark
Golomb rulers having smaller largest mark 
, and
2. The ruler is written in canonical form as the "smaller" of the equivalent rulers 
and 
, where "smaller"
means the first differing entry is less than the corresponding entry in the other
ruler.
In such a case, 
is the called the "length" of the optimal 
-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 (
, 
, 
, 
, 
, 
), 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]](/images/equations/GolombRuler/Inline24.svg)
.
The lengths of the optimal 
-mark Golomb rulers for 
, 3, 4, ... are 1, 3, 6, 11, 17, 25, 34, ... (OEIS A003022,
Vanderschel and Garry). Although the lengths of the optimal 
-mark Golomb rulers are not known for 
, 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 
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 
people, announced on Oct. 25, 2008 that the 25-mark ruler
was optimal.
The number 
of inequivalent optimal 
-mark
Golomb rulers for 
,
3, ... are 1, 1, 1, 2, 4, 5, 1, 1, 1, ... (OEIS A036501),
and the number of distances in an optimal 
-mark ruler is given by the triangular
number 
,
so for 
,
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 
. A more complete table is maintained
by J. B. Shearer.
 |  | optimal rulers |
| 2 | 1 | (0, 1) |
| 3 | 1 | (0, 1, 3) |
| 4 | 1 | (0, 1, 4, 6) |
| 5 | 2 | (0, 1, 4, 9, 11), (0, 2, 7, 8, 11) |
| 6 | 4 | (0, 1, 4, 10, 12, 17), (0, 1, 4, 10, 15, 17), (0, 1, 8, 12, 14, 17), |
| (0, 1, 8, 11, 13, 17) | ||
| 7 | 5 | (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) | ||
| 8 | 1 | (0, 1, 4, 9, 15, 22, 32, 34) |
