﻿ Prime number rulers

# Prime Number Rulers

A prime number ruler is a ruler such that the interior marks of the ruler are on prime number positions. A complete ruler is called minimal when any subsequence of its marks is not complete for the same length. A complete ruler is perfect, if there is no complete ruler with the same length which possesses fewer marks. A perfect ruler is minimal (but not conversely).

Prime number rulers were studied by Naoyuki Tamura. He proved that there exist only finite many prime number rulers and gave a complete list of the minimal prime number rulers which is shown below.

 segments length perfect optimal ruler 2 3 * / * [0, 2, 3] 3 4 * [0, 2, 3, 4] 3 6 * / * [0, 2, 5, 6] 4 8 * [0, 2, 3, 7, 8] 6 12 [0, 2, 3, 5, 7, 11, 12] 6 14 * [0, 2, 3, 5, 7, 13, 14] 6 14 * [0, 2, 3, 7, 11, 13, 14] 7 18 * [0, 2, 3, 5, 7, 11, 17, 18] 7 18 * [0, 2, 3, 5, 11, 13, 17, 18] 7 20 * [0, 2, 3, 7, 11, 17, 19, 20] 8 20 [0, 2, 3, 5, 7, 11, 13, 19, 20] 8 20 [0, 2, 3, 5, 11, 13, 17, 19, 20] 8 24 * [0, 2, 3, 5, 7, 11, 17, 23, 24] 9 24 [0, 2, 3, 5, 11, 13, 17, 19, 23, 24] 9 30 * [0, 2, 3, 5, 7, 11, 17, 23, 29, 30] 9 32 * [0, 2, 3, 7, 13, 17, 23, 29, 31, 32] 10 32 [0, 2, 3, 7, 11, 17, 19, 23, 29, 31, 32] 11 38 [0, 2, 3, 5, 7, 13, 19, 23, 29, 31, 37, 38] 12 44 [0, 2, 3, 5, 7, 11, 19, 23, 29, 31, 37, 43, 44] 12 44 [0, 2, 3, 5, 11, 13, 19, 23, 29, 37, 41, 43, 44] 12 44 [0, 2, 3, 5, 11, 17, 19, 23, 31, 37, 41, 43, 44] 12 44 [0, 2, 3, 5, 11, 19, 23, 29, 31, 37, 41, 43, 44] 12 44 [0, 2, 3, 7, 11, 13, 19, 23, 29, 37, 41, 43, 44] 12 44 [0, 2, 3, 7, 11, 17, 19, 23, 31, 37, 41, 43, 44] 12 44 [0, 2, 3, 7, 11, 19, 23, 29, 31, 37,41, 43, 44] 15 62 [0, 2, 3, 7, 13, 17, 23, 29, 31, 37, 43, 47, 53, 59, 61, 62] 15 62 [0, 2, 3, 7, 13, 19, 23, 29, 31, 37, 41, 47, 53, 59, 61, 62] 15 62 [0, 2, 3, 7, 13, 19, 23, 29, 31, 37, 43, 47, 53, 59, 61, 62]

From this table we infer that the only possible lengths of minimal prime number rulers are:

```3, 4, 6, 8, 12, 14, 18, 20, 24, 30, 32, 38, 44, 62.
```

Compare sequence A227956 in the Online Encyclopedia of Integer Sequences. The only possible lengths of perfect prime number rulers are:

```3, 4, 6, 8, 14, 18, 20, 24, 30, 32.
```

The only possible lengths of optimal prime number rulers are:

```3, 6.
```

There are 102 prime number rulers in total, 28 of which are minimal prime number rulers, 12 perfect prime number rulers and 2 optimal prime number rulers.

A simple fact: The length of a prime number ruler is p + 1 for some prime number p.

Reference: Naoyuki Tamura, Complete List of Prime Number Rulers, Information Science and Technology Center, Kobe University, 2013.

Generation of perfect prime rulers, implementation with Sage.

```1    A103298 = [0, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6,
2               7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9]
3
4    def accumulate(L):
5        total = 0
6        for i in L:
7            total += i
8            yield total
9
10   def PrimesOnly(L):
11       if L[0] != 2: return []
12       R = [0]
13       for a in accumulate(L):
14           if not is_prime(a): return []
15           R.append(a)
16       R.append(a+1)
17       return R
18
19   def isComplete(R) :
20       S = []
21       L = len(R) - 1
22       for i in range(L, 0, -1) :
23           for j in range(1,i+1) :
24               S.append(R[i] - R[i-j])
25       return len(Set(S)) == R[L]
26
27   def CompletePrimeRulers(n):
28       for c in Compositions(n):
29           r = PrimesOnly(c)
30           if r != []:
31               if isComplete(r):
32                   yield r
33
34   def PerfectPrimeRulers(n):
35       if not is_prime(n-1): return []
36       return filter(lambda p: len(p)-1 == A103298[n], CompletePrimeRulers(n-1))
37
38   def main():
39       for n in range(1,21):
40           for p in PerfectPrimeRulers(n):
41               print('segments:', len(p)-1, 'length:', n, p)
42
43   main()
```

Back to the Homepage of Rulers.