More abstractly, a sparse ruler of length
A complete sparse ruler allows one to measure any integer distance up to its full length.
A complete sparse ruler is called minimal if there is no complete sparse ruler of length
In other words, if any of the marks is removed one can no longer measure all of the distances, even if the marks could be rearranged.
A complete sparse ruler is called maximal if there is no complete sparse ruler of greater length with
A sparse ruler is called optimal if it is both minimal and maximal.
Since the number of distinct pairs of marks is
This upper bound can be achieved only for 2, 3 or 4 marks.
For larger numbers of marks, the difference between the optimal length and the bound grows gradually, and unevenly.
For example, for 6 marks the upper bound is 15, but the maximal length is 13.
There are 3 different configurations of sparse rulers of length 13 with 6 marks.
To measure a length of 7, say, with this ruler one would take the distance between the marks at 6 and 13.
marks will be considerably longer than an optimal sparse ruler with
is a lower bound for the length of a Golomb ruler.
A long Golomb ruler will have gaps, that is, it will have distances which it cannot measure.
As found by Brian Wichmann, many optimal rulers[1] are of the form
None of the optimal rulers of length 1, 13, 17, 23 and 58 follow this pattern.
That sequence ends with 58 if the Optimal Ruler Conjecture of Peter Luschny is correct.
be the smallest number of marks for a ruler of length
was studied by Erdos, Gal[3] (1948) and continued by Leech[4] (1956) who proved that the limit
exists and is lower and upper bounded by
was studied by Redei, Renyi[5] (1949) and then by Leech (1956) and Golay[6] (1972).
Due to their efforts the following upper and lower bounds were obtained:
[7] If the Optimal Ruler Conjecture is true, then
, leading to the ″dark mills″ pattern when arranged in columns, OEIS A326499.
[8] All of the windows in the dark mills pattern are Wichmann rulers.
are believed to non-minimal, especially the "cloud" values.
The following are examples of minimal sparse rulers.
A few incomplete rulers can fully measure up to a longer distance than an optimal sparse ruler with the same number of marks.
Rulers that can fully measure up to a longer distance than any shorter ruler with the same number of marks are highlighted.