# 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 ${\displaystyle L}$ with ${\displaystyle m}$ marks is a sequence of integers ${\displaystyle a_{1},a_{2},...,a_{m}}$ where ${\displaystyle 0=a_{1}. The marks ${\displaystyle a_{1}}$ and ${\displaystyle a_{m}}$ correspond to the ends of the ruler. In order to measure the distance ${\displaystyle K}$, with ${\displaystyle 0\leq K\leq L}$ there must be marks ${\displaystyle a_{i}}$ and ${\displaystyle a_{j}}$ such that ${\displaystyle 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 ${\displaystyle L}$ with ${\displaystyle 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 ${\displaystyle L+1}$ with ${\displaystyle m}$ marks. A sparse ruler is called optimal if it is both minimal and maximal.
Since the number of distinct pairs of marks is ${\displaystyle m(m-1)/2}$, this is an upper bound on the length ${\displaystyle L}$ of any maximal sparse ruler with ${\displaystyle 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 ${\displaystyle a_{j}-a_{i}}$ be distinct. In general, a Golomb ruler with ${\displaystyle m}$ marks will be considerably longer than an optimal sparse ruler with ${\displaystyle m}$ marks, since ${\displaystyle 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.