Sparse Rulers
Sparse Rulers
A sparse ruler is a rod of integer length with a minimal number of marks so that all distances 1 to can be measured. Many lengths, such as 36, have unique rulers with a twin by subtracting marks from , as seen here:
n
n
n
36-{0,1,3,6,13,20,27,31,35,36}={36,35,33,30,23,16,9,5,1,0}
This Demonstration has many but not all sparse rulers. Up to length 198, there are sparse rulers, with of them for length 59 alone. Many of the longest known sparse rulers for a particular number of marks are Wichmann rulers. A Wichmann ruler generator is given in the Initialization.
106520
31980
In a Golomb ruler, distances can be missing but none can be repeated.
In a sparse ruler, distances can be repeated but none can be missing.
In a difference set, modular distances cannot be missing or repeated.
For a minimal sparse ruler of length with marks, let the excess be . The excess is always 0 or 1.
n
m
e
e=m-round(sqrt(3n+9/4))
The "show ruler" box is a toggle for "show grid" of excess to length 2103.
Details
Details
Snapshot 1: a simple case with extra marks at 1, 2 and 4 on a ruler of length 7; all the lengths from 1 to 7 can be measured as , , , , , and .
1-0
4-2
7-4
4-0
7-2
7-1
7-0
External Links
External Links
Permanent Citation
Permanent Citation
Ed Pegg Jr
"Sparse Rulers" from the Wolfram Demonstrations Project http://demonstrations.wolfram.com/SparseRulers/
Published: June 27, 2019