A sparse ruler is a ruler in which some of the distance marks may be missing. More abstractly, a sparse ruler of length
L
m
a1,a2,...,am
0=a1<a2<...<am=L
a1
am
K
0\leK\leL
ai
aj
aj-ai=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
m-1
m
Since the number of distinct pairs of marks is
m(m-1)/2
L
m
For example, for 6 marks the upper bound is 15, but the maximal length is 13. There are 3 different configurations of sparse rulers of length 13 with 6 marks. One is . To measure a length of 7, say, with this ruler one would take the distance between the marks at 6 and 13.
A Golomb ruler is a sparse ruler that requires all of the differences
aj-ai
m
m
m(m-1)/2
Many optimal rulers are of the form
W(r,s)=1r,r+1,(2r+1)r,(4r+3)s,(2r+2)(r+1),1r,
ab
b
a
r=1
s=2
W(1,2)
A minor variant is
w(r,s)=1r,r+1,(2r+1)(r+1),(4r+3)s,(2r+2)r,1r,
W(r,s)
W(1,2)
w(1,2)
4r(r+s+2)+3(s+1)
4r+s+3
For every
n
l(n)
n
l(6)=4
l(n)
\limn\toinfty{l(n)2}/n
2+\tfrac{4}{3\pi}=2.424...<2.434...=max0<\theta<2\pi2(1-\tfrac{\sin(\theta)}{\theta})\le\limn\toinfty
l(n)2 | \le | |
n |
375 | |
112 |
=3.348...
Much better upper bounds exist for
n
A
N
k\len
k=a-b
a,b\inA
n
k(n)
n
k(n)\lel(n)
k(n)
max0<\theta<2\pi2(1-\tfrac{\sin(\theta)}{\theta})\le\limn\toinfty
k(n)2 | |
n=inf |
n\inN
k(n)2 | =2.6571...< | ||
|
83. | |
Define the excess as
E(n)=l(n)-\lceil\sqrt{3n+\tfrac{9}{4}}\rfloor
E(n)
n
E(n)=0|1
n
n>213
E=1
n>213
The following are examples of minimal sparse rulers. Optimal rulers are highlighted. When there are too many to list, not all are included. Mirror images are not shown.
Length | Marks | Number | Examples | List Form | Wichmann | ||||||
1 | 2 | 1 | II | ||||||||
2 | 3 | 1 | III | ||||||||
3 | 3 | 1 | II.I | W(0,0) | |||||||
4 | 4 | 2 | III.I II.II | | |||||||
5 | 4 | 2 | III..I II.I.I | | |||||||
6 | 4 | 1 | II..I.I | W(0,1) | |||||||
7 | 5 | 6 | IIII...I III.I..I III..I.I II.I.I.I II.I..II II..II.I | | |||||||
8 | 5 | 4 | III..I..I II.I...II II..I.I.I II...II.I | | |||||||
9 | 5 | 2 | III...I..I II..I..I.I | | - W(0,2) | ||||||
10 | 6 | 19 | IIII..I...I | ||||||||
11 | 6 | 15 | IIII...I...I | ||||||||
12 | 6 | 7 | IIII....I...I III...I..I..I II.I.I.....II II.I...I...II II..II....I.I II..I..I..I.I II.....II.I.I | | - - - - - W(0,3) - | ||||||
13 | 6 | 3 | III...I...I..I II..II.....I.I II....I..I.I.I | | |||||||
14 | 7 | 65 | IIIII....I....I | ||||||||
15 | 7 | 40 | II.I..I...I...II II..I..I..I..I.I | | W(1,0) W(0,4) | ||||||
16 | 7 | 16 | IIII....I...I...I | ||||||||
17 | 7 | 6 | IIII....I....I...I III...I...I...I..I III.....I...I.I..I III.....I...I..I.I II..I.....I.I..I.I II......I..I.I.I.I | | |||||||
18 | 8 | 250 | II..I..I..I..I..I.I | W(0,5) | |||||||
19 | 8 | 163 | IIIII....I....I....I | ||||||||
20 | 8 | 75 | IIIII.....I....I....I | ||||||||
21 | 8 | 33 | IIIII.....I.....I....I | ||||||||
22 | 8 | 9 | IIII....I....I....I...I III.......I....I..I..II II.I.I........II.....II II.I..I......I...I...II II.I.....I.....I...II.I II..II......I.I.....I.I II....II..I.......I.I.I II....I..I......I.I.I.I II.....II........II.I.I | | - - - W(1,1) - - - - - | ||||||
23 | 8 | 2 | III........I...I..I..I.I II..I.....I.....I.I..I.I | | |||||||
24 | 9 | 472 | IIIIII......I.....I.....I | ||||||||
25 | 9 | 230 | IIIIII......I......I.....I | ||||||||
26 | 9 | 83 | IIIII.....I....I.....I....I | ||||||||
27 | 9 | 28 | IIIII.....I.....I.....I....I | ||||||||
28 | 9 | 6 | III..........I....I..I..I..II II.I.I.I..........II.......II II.I..I..I......I......I...II II.I.....I.....I.....I...II.I II.....I...I........I..I.II.I II.......II..........II.I.I.I | | |||||||
29 | 9 | 3 | III...........I...I..I..I..I.I II.I..I......I......I...I...II II..I.....I.....I.....I.I..I.I | | - W(1,2) - | ||||||
35 | 10 | 5 | III..............I...I..I..I..I..I.I II.I..I..I......I......I......I...II II.I..I..I.........I...I......I...II II..II..........I.I......I.I.....I.I II..I.....I.....I.....I.....I.I..I.I | | |||||||
36 | 10 | 1 | II.I..I......I......I......I...I...II | W(1,3) | |||||||
43 | 11 | 1 | II.I..I......I......I......I......I...I...II | W(1,4) | |||||||
46 | 12 | 342 | III..I....I....I..........I.....I.....I.....III | W(2,1) | |||||||
50 | 12 | 2 | IIII...................I....I...I...I...I...I..I..I II.I..I......I......I......I......I......I...I...II | | - W(1,5) | ||||||
57 | 13 | 12 | III..I....I....I..........I..........I.....I.....I.....III II.I..I......I......I......I......I......I......I...I...II | | W(2,2) W(1,6) | ||||||
58 | 13 | 6 | IIII.......................I....I...I...I...I...I...I..I..I III...I.I........I........I........I........I..I......I..II III.....I......II.........I.........I.........I..I...I.I..I II.I..I..........I..I......I.......I.........I...I...I...II II.I..I..........I......I..I..........I......I...I...I...II II...I..I...I........I........I........I........I....II.I.I | | |||||||
68 | 14 | 2 | III..I....I....I..........I..........I..........I.....I.....I.....III III.....I......II.........I.........I.........I.........I..I...I.I..I | | W(2,3) - | ||||||
79 | 15 | 1 | III..I....I....I..........I..........I..........I..........I.....I.....I.....III | W(2,4) | |||||||
90 | 16 | 1 | III..I....I....I..........I..........I..........I..........I..........I.....I.....I.....III | W(2,5) | |||||||
101 | 17 | 1 | III..I....I....I..........I..........I..........I..........I..........I..........I.....I.....I.....III | W(2,6) | |||||||
112 | 18 | 1 | III..I....I....I..........I..........I..........I..........I..........I..........I..........I.....I.....I.....III | W(2,7) | |||||||
123 | 19 | 2 | IIII...I......I......I......I..............I..............I..............I..............I.......I.......I.......I.......IIIIIII..I....I....I..........I..........I..........I..........I..........I..........I..........I..........I.....I.....I.....III | | W(3,4) W(2,8) | ||||||
138 | 20 | 1 | IIII...I......I......I......I..............I..............I..............I..............I..............I.......I.......I.......I.......IIII | W(3,5) |
A few incomplete rulers can fully measure up to a longer distance than an optimal sparse ruler with the same number of marks.
\{0,2,7,14,15,18,24\}
\{0,2,7,13,16,17,25\}
\{0,5,7,13,16,17,31\}
\{0,6,10,15,17,18,31\}
Marks | Length | Measures up to | Ruler | |
---|---|---|---|---|
7 | 24 | 18 | ||
7 | 25 | 18 | ||
7 | 31 | 18 | ||
7 | 31 | 18 | ||
8 | 39 | 24 | ||
10 | 64 | 37 | ||
10 | 73 | 37 | ||
11 | 68 | 44 | ||
11 | 91 | 45 | ||
12 | 53 | 51 | ||
12 | 60 | 51 | ||
12 | 73 | 51 | ||
12 | 75 | 51 | ||
12 | 82 | 51 | ||
12 | 83 | 51 | ||
12 | 85 | 51 | ||
12 | 87 | 51 | ||
13 | 61 | 59 | ||
13 | 69 | 59 | ||
13 | 69 | 59 | ||
13 | 82 | 59 | ||
13 | 83 | 59 | ||
13 | 88 | 59 | ||
13 | 88 | 59 | ||
13 | 90 | 59 | ||
13 | 91 | 59 | ||
13 | 92 | 59 | ||
13 | 94 | 59 | ||
13 | 95 | 59 | ||
13 | 96 | 59 | ||
13 | 101 | 59 | ||
13 | 108 | 59 | ||
13 | 113 | 61 | ||
13 | 133 | 60 |
1,2, … ,N
1,2, … ,n
1,2, … ,N
1,2,\ldots,n