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.