# Sparse ruler

#### Dear Wikiwand AI, let's keep it short by simply answering these key questions:

Can you list the top facts and stats about Sparse ruler?

A sparse ruler is a ruler in which some of the distance marks may be missing. More abstractly, a sparse ruler of length $L$ with $m$ marks is a sequence of integers $a_{1},a_{2},...,a_{m}$ where $0=a_{1} . The marks $a_{1}$ and $a_{m}$ correspond to the ends of the ruler. In order to measure the distance $K$ , with $0\leq K\leq L$ there must be marks $a_{i}$ and $a_{j}$ such that $a_{j}-a_{i}=K$ .
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 $L$ with $m-1$ marks. 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 length $L+1$ with $m$ marks. A sparse ruler is called optimal if it is both minimal and maximal.
Since the number of distinct pairs of marks is $m(m-1)/2$ , this is an upper bound on the length $L$ of any maximal sparse ruler with $m$ marks. 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.
A Golomb ruler is a sparse ruler that requires all of the differences $a_{j}-a_{i}$ be distinct. In general, a Golomb ruler with $m$ marks will be considerably longer than an optimal sparse ruler with $m$ marks, since $m(m-1)/2$ 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. For example, the optimal Golomb ruler {0, 1, 4, 10, 12, 17} has length 17, but cannot measure lengths of 14 or 15.