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 were found with the min_ruler.c and the min_ruler.c program. (These program might still change frequently.)

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).

Update October 26, 2008

Today, I read Slashdot article which states: "Distributed.net's 8-year-old OGR-25 distributed computing project has just proven conclusively that the predicted shortest 25-mark Golomb ruler is optimal."

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.

home and email