Sparse rulers

A sparse ruler for length 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 where found with the min_ruler.c and the min_ruler.cprogram. (These program might still change frequently.)

Results found by others

Number of true, minimal sparse rulers for length 2 

    |   2
----+----
  3 |   1

Number of true, minimal sparse rulers for length 3 

    |   3
----+----
  3 |   2

Number of true, minimal sparse rulers for length 4 

    |   4   5   6   7
----+----------------
  4 |   3   0   2   2

Number of true, minimal sparse rulers for length 5 

    |   5   6   7
----+------------
  4 |   4   0   2

Number of true, minimal sparse rulers for length 6 

    |   6
----+----
  4 |   2

Number of true, minimal sparse rulers for length 7 

    |   7   8   9  10  11  12  13
----+----------------------------
  5 |  12   0   8   8   6   4   4

Number of true, minimal sparse rulers for length 8 

    |   8   9  10  11  12  13
----+------------------------
  5 |   8   0   2   4   2   2

Number of true, minimal sparse rulers for length 9 

    |   9  10  11  12  13
----+--------------------
  5 |   4   0   2   0   2

Number of true, minimal sparse rulers for length 10 

    |  10  11  12  13  14  15  16  17  18  19
----+----------------------------------------
  5 |
  6 |  38   0  16  26  22  42  16  32   8   8  (more)

Number of true, minimal sparse rulers for length 11 

    |  11  12  13  14  15  16  17  18  19  20
----+----------------------------------------
  6 |  30   0  14  16  20  12  20  12  10   0  (more)

Number of true, minimal sparse rulers for length 12 

    |  12  13  14  15  16  17  18  19  20  21
----+----------------------------------------
  6 |  14   0   2   4   0   6   4   8   0   2

Number of true, minimal sparse rulers for length 13 

    |  13  14  15  16  17  18  19
----+----------------------------
  6 |   6   0   0   2   4   0   2

Number of true, minimal sparse rulers for length 14 

    |  14  15  16  17  18  19  20  21  22  23
----+----------------------------------------
  6 |
  7 | 130   0  44  68  72 104  88 164  94 136  (more)

Number of true, minimal sparse rulers for length 15 

    |  15  16  17  18  19  20  21  22  23  24
----+----------------------------------------
  6 |
  7 |  80   0  30  36  40  32  52  46  58  28  (more)

Number of true, minimal sparse rulers for length 16 

    |  16  17  18  19  20  21  22  23  24  25
----+----------------------------------------
  7 |  32   0   4  10  16  12   6  28   8  20  (more)

Number of true, minimal sparse rulers for length 17 

    |  17  18  19  20  21  22  23  24  25  26
----+----------------------------------------
  7 |  12   0   0   2   6   4   0   2   4   2   (more)

Number of true, minimal sparse rulers for length 18 

    |  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

Number of true, minimal sparse rulers for length 19 

    |  19  20  21  22  23  24  25  26  27  28
----+----------------------------------------
  7 |
  8 | 326   0 124 100 194 176 230 198 282 240 (more)

Number of true, minimal sparse rulers for 23 

    |  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

Number of true, minimal sparse rulers for length 24 

    |  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 39
Usage 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     v
Or: 
   |  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

Number of true, minimal sparse rulers for length 29 

    | 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

Number of true, minimal sparse rulers for length 37 

    |  37  --  65
----+--------------------------------------------
 10 |   0  --   *
Stopped after one found.

Results found by others

After some days of searching myself, I got an email from David Fowler, which contained a forwarded mail from Christian Holzbaur, with a reference to the article New Algorithms for Golomb Ruler Derivation and Proof of the 19 Mark Ruler written by Apostolod Dollas, William T. Rankin and David McCracken. It took them 36200 CPU hours on a Sparc Classic to find the 19 mark ruler (which does not surprise me).