A sparse ruler is a ruler that has integer length 
and the minimal 
marks allowing measurement of all distances 1, 2, 3, 4, ...
up to 
(possibly with repetition). They are therefore very similar to the type of ruler
considered by Gardner (1985, pp. 65-67 and 261-262).
Consider a sparse ruler of length 13. Clearly, five marks wouldn't be enough since there are at most 
differences between possible marks. On the other hand, six marks is enough, but because
that gives 
differences, there must be two repeats. An example of such a set of marks is 
0, 1, 6, 9, 11, and 13
, which gives all distances up to 13, but includes distance
2 and 5 twice each (
and 
; 
and 
). In fact, no perfect
sparse ruler, i.e., a sparse ruler that uniquely measures all distances up to its
length, exists for five or more marks (Golomb 1972; Gardner 1983, p. 154).
Sparse rulers arise in the representation of differences problem of Erdős and Gál (1949). The problem of finding a sparse ruler of a given length was solved partially by Leech (1956) and mostly by Wichmann (1963). However, the power of Wichmann's solution wasn't realized until a modern computer analysis by Robinson (2014) and Pegg (2020).
An example sparse ruler can be given by the marks 
0, 1, 2, 3, 27, 32, 36, 40, 44, 48, 52, 55, 58
, with differences between marks 
1, 1, 1, 24, 5, 4, 4, 4, 4, 4, 3, 3
. A ruler like this having repeated values has a shortened
form written as 
.
This notation leads to the major 
and minor 
Wichmann constructions:
 |
 |
The maximal length for a Wichmann ruler with 
marks is 
. For 
, 2, ..., these have lengths 3, 6, 9, 12, 15, 22, 29, 36,
43, 50, 57, 68, 79, ... (A289761). An optimal
sparse ruler has the greatest length for a given number of marks. Except for lengths
1, 13, 17, 23 and 58 (A349978), all known optimal
sparse rulers are Wichmann constructions. The optimal ruler conjecture posits that
all optimal sparse rulers other than these exceptions are Wichmann constructions.
A sparse ruler of length 
has 
marks, where 
is called the excess and is equal to
0 or 1. The values of 
for 
, 51, ... are given by 1, 0, 0, 0,
0, 0, 0, 0, 1, ... (A326499), which is a sequence
with offset 50 since 
for all 
.
The difficulty of computer searching increases exponentially with the length. In
fact, it has not even been ruled out that the excess could be 
for some (large) value of 
.
The major and minor Wichmann constructions are simple modifications of each other, and most solutions can be modified in many ways. For more than 880 marks, adding a single mark at the end of a Wichmann construction can produce a solution with excess 0 or 1 for any length above 257992. That makes sparse rulers unusual among problems in combinatorics in that the smaller (not larger) cases are the hardest to find, with the sparse ruler of length 1792 being particularly hard to find.
Plotting the excess values in batches of maximal Wichmann rulers leads to a pattern called "Dark Satanic Mills on a Cloudy Day" by N. J. A. Sloane. All the windows in the Dark Mill are Wichmann constructions. Due to this pattern, it is believed Wichmann (1963) solved the problem, with the caveats above.
by Differences." Proc.
Nederl. Akad. Wetensch. 51, 1155-1158, 1948. Also published as Indagationes
Math. 10, 379-382, 1949.Gardner, M. 
by Differences." J. London Math. Soc. 31,
160-169, 1956.Pegg, E. "Hitting All the Marks: Exploring New Bounds
for Sparse Rulers and a Wolfram Language Proof." 2020.