m, has less then n+1 marks
but can still measure all lengths from 1 to n.
A true sparse ruler is a sparse ruler that cannot measure
length n+1, and a minimal sparse ruler is a sparse
ruler where no mark can be removed.
A ruler is defined by the ascending sequence P_1, ..,
P_k, where P_1 equals zero.
The set of distances D({P_1, .., P_k}) which can be measured
is defined by { P_j - P_i | 0 <= i <= j <= k }.
The ruler P_1, .., P_k is a sparse ruler for length
n if D({P_1, .., P_k}) contains all numbers from 1
to n, and k<n+1.
The sparse ruler P_1, .., P_k for length
n is a true sparse ruler if n+1 is
not in D({P_1, .., P_k}),
and a minimal sparse ruler if for all I <= j <= k,
D({P_1, .., P_k}/{P_j}) does not contain all numbers from
1 to n.
We define tmsp(n,k,l) as function that returns the
number of different true, minimal sparse rulers P_1, ..,
P_k for length n, where P_k = l.
The result presented below were found with the min_ruler.c and the min_ruler.c program. (These program might still change frequently.)
| 2
----+----
3 | 1
| 3
----+----
3 | 2
| 4 5 6 7
----+----------------
4 | 3 0 2 2
| 5 6 7
----+------------
4 | 4 0 2
| 6
----+----
4 | 2
| 7 8 9 10 11 12 13
----+----------------------------
5 | 12 0 8 8 6 4 4
| 8 9 10 11 12 13
----+------------------------
5 | 8 0 2 4 2 2
| 9 10 11 12 13
----+--------------------
5 | 4 0 2 0 2
| 10 11 12 13 14 15 16 17 18 19
----+----------------------------------------
5 |
6 | 38 0 16 26 22 42 16 32 8 8 (more)
| 11 12 13 14 15 16 17 18 19 20
----+----------------------------------------
6 | 30 0 14 16 20 12 20 12 10 0 (more)
| 12 13 14 15 16 17 18 19 20 21
----+----------------------------------------
6 | 14 0 2 4 0 6 4 8 0 2
| 13 14 15 16 17 18 19
----+----------------------------
6 | 6 0 0 2 4 0 2
| 14 15 16 17 18 19 20 21 22 23
----+----------------------------------------
6 |
7 | 130 0 44 68 72 104 88 164 94 136 (more)
| 15 16 17 18 19 20 21 22 23 24
----+----------------------------------------
6 |
7 | 80 0 30 36 40 32 52 46 58 28 (more)
| 16 17 18 19 20 21 22 23 24 25
----+----------------------------------------
7 | 32 0 4 10 16 12 6 28 8 20 (more)
| 17 18 19 20 21 22 23 24 25 26
----+----------------------------------------
7 | 12 0 0 2 6 4 0 2 4 2 (more)
| 18 19 20 21 22 23 24 25 26 27 28 29 30 31
----+--------------------------------------------------------
7 | 0 0 0 0 0 0 2 2 0 0 0 0 0 4
| 19 20 21 22 23 24 25 26 27 28
----+----------------------------------------
7 |
8 | 326 0 124 100 194 176 230 198 282 240 (more)
| 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
----+------------------------------------------------------------
8 | 4 0 0 0 0 0 0 4 2 2 4 0 0 0 2
These are the sparse rulers:
0 1 2 11 15 18 21 23 0 1 4 10 16 18 21 23 0 2 5 7 13 19 22 23 0 2 5 8 12 21 22 23 0 1 7 17 19 21 22 30 0 1 13 16 19 21 23 30 0 7 9 11 14 17 29 30 0 8 9 11 13 23 29 30 0 2 9 15 19 20 23 31 0 8 11 12 16 22 29 31 0 1 4 9 15 20 22 32 0 10 12 17 23 28 31 32 0 2 15 16 21 22 25 33 0 3 10 19 20 21 25 33 0 8 11 12 17 18 31 33 0 8 12 13 14 23 30 33 0 1 8 12 18 21 23 37 0 14 16 19 25 29 36 37
| 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
----+----------------------------------------------------------------
8 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2
These are the sparse rulers:
0 8 15 17 20 21 31 39 0 8 18 19 22 24 31 39Usage of this ruler:
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ---+------------------------------------------------------------------------ 0 | ^ ^ ^ ^ ^ 8 | ^ v ^ ^ ^ | ^ | | | ^ 15 | ^ ^ ^ v | | | v | | | | ^ | ^ 17 | v ^ ^ | | v | | ^ | v | | | | | 20 | ^ v | v | ^ v | | | ^ v | | | | 21 | v v v ^ | v | | ^ | v | | | 31 | ^ v v v v | | | v | 39 | v v v v vOr:
| 0 8 15 17 20 21 31 39 ---+------------------------- 0 | 8 15 17 20 21 8 | 8 7 9 12 13 23 15 | 15 7 2 5 6 16 24 17 | 17 9 2 3 4 14 22 20 | 20 12 5 3 1 11 19 21 | 21 13 6 4 1 10 18 31 | 23 16 14 11 10 8 39 | 24 22 19 18 8
| 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
----+---------------------------------------------------------------------
9 | 6 0 0 0 0 0 0 0 0 4 2 2 0 4 2 2 0 0 2 2 2 0 2
These are the sparse rulers:
0 1 2 14 18 21 24 27 29 0 1 3 6 13 20 24 28 29 0 1 4 10 16 22 24 27 29 0 1 5 9 16 23 26 28 29 0 1 7 15 19 24 27 29 40 0 1 9 21 23 25 27 28 38 0 1 16 19 22 25 27 29 39 0 2 5 7 13 19 25 28 29 0 2 5 8 11 15 27 28 29 0 2 9 15 21 25 26 29 43 0 2 10 15 21 24 27 28 44 0 3 11 22 23 24 28 29 38 0 3 15 23 24 25 29 31 42 0 4 13 24 25 26 27 32 42 0 5 6 14 16 26 29 33 51 0 6 7 18 20 23 28 32 47 0 7 9 21 24 25 29 35 48 0 8 11 20 21 25 26 27 49 0 9 10 14 15 16 27 35 38 0 10 11 13 15 17 29 37 38 0 10 12 14 17 20 23 38 39 0 10 15 16 17 18 29 38 42 0 11 13 16 21 25 33 39 40 0 11 13 17 18 19 27 39 42 0 13 19 23 24 27 39 41 48 0 14 17 18 22 28 34 41 43 0 15 19 24 27 29 40 41 47 0 16 17 20 23 29 34 42 44 0 18 22 25 35 37 45 46 51 0 22 23 24 28 29 38 41 49
| 37 -- 65
----+--------------------------------------------
10 | 0 -- *
Stopped after one found.
After reading this, I discovered that my definition of a sparse ruler is quite different from that of a Golomb ruler. A Golomb ruler is a rule where any distance between two marks is unique, which is quite different from stating that every distance is present. Now that I think of it, I also think that it is much easier to find sparse rulers than Golomb rulers.