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.

Complete list of the 28 minimal prime number rulers.
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 Back to the Homepage of Rulers.