A sparse ruler is a ruler of positive integer length 
with marks at integer positions between 0 and 
, including both endpoints, that measures every distance 1,
2, ..., 
using the minimum possible number 
of marks. Distances may be measured more than once. Such
rulers are similar to the type 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 restricted representation of differences problem studied by Erdős and Gál (1948). Leech (1956) and Wichmann (1963) gave bounds and constructions. Modern computer analyses include Robison (2014) and Pegg (2020), but exact minimum mark counts remain unknown for many lengths.
An example sparse ruler can be given by the marks 
0, 1, 2, 3, 27, 32, 36, 40, 44, 48, 52, 55, 58
, with consecutive 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, where 
and 
are nonnegative integers
and powers denote repetition of consecutive gaps:
 |
 |
The maximal length for a Wichmann ruler with 
segments (
marks) is 
for 
. For 
, 3, ..., these have lengths 3, 6, 9, 12, 15, 22, 29, 36,
43, 50, 57, 68, 79, ... (OEIS A289761). An
optimal sparse ruler has the greatest length for a given number of marks. Among known
greatest lengths, the exceptions to attainment by Wichmann
rulers are 1, 13, 17, 23, and 58 (OEIS A349978).
This is an existence assertion and does not imply that every optimal sparse ruler
is a Wichmann ruler. It is conjectured that for
every number of marks greater than 13, a Wichmann ruler
attains the greatest possible length (Saarela and Vanhatalo 2024, p. 10).
The excess of a sparse ruler is 
, where 
is the nearest integer
function. The recorded values for 
, 52, ... begin 1, 0, 0, 0, 0, 0, 0, 0, 1, ... (OEIS A326499), with excess 0 for 
. For lengths above 213, some recorded values
come from constructions whose minimality has not been proved. Exhaustive searches
become increasingly expensive, and it has not been ruled out that 
could be negative for some large 
.
The major and minor Wichmann constructions are simple modifications of each other, and most solutions can be modified in many ways. Pegg (2020) describes constructions
which, for any length 
,
use 
or 
marks. 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 challenging.
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 rulers. The pattern motivates conjectures about the optimality of Wichmann rulers, but does not establish the exact minimum mark count for every length.
A related maximum distinct differences problem fixes both the number of marks and an enclosing interval, and maximizes the number of distinct distances attained. Unlike a sparse ruler, an optimal configuration for this problem may leave some distances unmeasured (Pegg 2026).
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. Jr. "Sparse Rulers." Wolfram Demonstrations Project.
2019.