PERFECT AND OPTIMAL RULERS

KEYWORDS: Rulers, complete rulers, perfect rulers, optimal rulers, Wichmann rulers, perfect Wichmann rulers, optimal Wichmann rulers, compositions.

Concerned with sequences:

A004137, A103299, A103301, A103300, A103295, A103296, A103294, A103297, A103298, A193802, A193803.

Introduction

Rulers, which we can buy at the stationery shop, are edged with a regular sequence of marks and look somewhat like this '_'_'_'_'_'_'.

Rather dull. Recently, however, the manufacturers of rulers found out that they can reduce production costs by deleting some of the marks from the rulers without reducing their functionality. For example with the ruler '_'___'__' you can also measure all the distances you can measure with the standard ruler of equal length.

How many marks can be deleted, if we want to be able to measure all distances up to some length? In essence, it is this question which we are going to study here and which turns a monotonous ruler in an interesting object of combinatorics.

First of all, we want to be sure that we can measure all length of equal or shorter size then the length of the ruler. Clearly this is a sine qua non for a reasonable ruler. A ruler which has this feature will be called a complete ruler, because it has enough marks to fulfill this basic task. Rulers which can not (incomplete rulers) will not be considered here.

Next we focus on those complete rulers which have as few marks as possible. They will be called perfect rulers. They are complete rulers, but the deletion of a single mark would make them incomplete. There is a certain aesthetic impression associated with perfect rulers: they accomplish a task with a minimum of complexity.

Interestingly, perfect rulers with the same number of marks still differ in their usefulness. Let us consider the following three perfect rulers. All of them have 4 marks. (The numbers correspond to the positions of the marks on the ruler.)

[0, 1, 3, 4], [0, 1, 3, 5], [0, 1, 4, 6]

But with the third one you can measure 33% more lengths compared to the first one. So you would certainly choose the third one if you would like to buy one of these rulers.

But the decisive thing about the third ruler is that there does not exist any other ruler with 4 marks, which is complete and can measure more lengths. Thus the marks cover a maximal metering range. Rulers with this quality are called optimal rulers. Optimal rulers thus combine the aesthetics of a minimum of complexity with a maximum of usefulness.

Rulers with this feature are quite rare creatures. For example there are 52012 perfect rulers with 14 marks, but only 4 out of them are optimal rulers. The enumeration of complete, perfect and optimal rulers will be one of our major tasks.

Optimal rulers, which exist for every number of marks, have a very peculiar length. In fact their lengths are, in dependency on the number of marks,

0, 1, 3, 6, 9, 13, 17, 23, ...

But these numbers also count the maximal number of edges in a graceful graph on n nodes, linking the study of perfect rulers to graph theory, combinatorics and additive number theory.

Clearly we would like to know how to construct such optimal rulers. At first sight this does not seem to be an easy task, but there is an exciting, still unproved conjecture, that there is a blueprint for optimal rulers, which would allow a very simple construction. It says that a ruler with more then 14 marks is optimal only if it is a Wichmann ruler, named after B. Wichmann, who introduced them in 1962 in A note on restricted difference bases.

Rulers in a Nutshell

A ruler is a strict increasing finite sequence of marks, which are understood as nonnegative numbers. By convention the first mark is set to 0.

Rulers are counted with regard to their length L and the number of segments S (a segment is the space between two adjacent marks). A ruler with M marks has S = M - 1 segments.

A ruler is:

COMPLETE, if all distances d with 1 ≤ d ≤ L can be measured with the ruler.
PERFECT, if there is no complete ruler with the same length which possesses fewer marks.
OPTIMAL, if there is no perfect ruler with the same number of marks which has a greater length.

A SAGE WORKSHEET

Rulers

def Partsum(T) :
    return [add([T[j] for j in range(i)]) for i in (0..len(T))]

Given a list T the function partsum returns the list of partial sums of T. For example [1,2,3,4,5] maps on [0,1,3,6,10,15] (the triangular numbers A000217). Note that a '0' is prepended as the first sum is the empty sum.

Partsum([1,2,3,4,5])

[0, 1, 3, 6, 10, 15]

Recall that a composition of a positive integer n is defined as a list of positive integers which sum to n. If we apply the summation of parts to compositions we get new objects. In the case n = 4 this is displayed in the plot below.

This is all we need to give the basic definition: A ruler is the list of partial sums of an integer-composition.

def Ruler(L, S) :
    return map(Partsum, Compositions(L, length=S))

Ruler(6, 3)

[[0, 4, 5, 6],[0, 3, 5, 6],[0, 3, 4, 6],[0, 2, 5, 6],[0, 2, 4, 6],
[0, 2, 3, 6],[0, 1, 5, 6],[0, 1, 4, 6],[0, 1, 3, 6],[0, 1, 2, 6]]

Let us clarify the terminology: a member of the ruler is called a mark, the length of a ruler L is the difference between the last and the first mark; so all the rulers in the last example have length 6. The second important quantity for classification is the number of segments S. A segment is the space between two marks. So the ruler has [0, 2, 5, 6] has length 6 and 3 segments. The number of marks is M = S + 1.

We denote the set of all rulers which have length L and S segments by R(L, S), where L ≥ 0 and S ≥ 0. The empty ruler is [ ] and the trivial ruler [0, 1, 2, ..., n] is characterized by L = S.

Complete Rulers

A ruler is complete if all distances between 1 and the length of the ruler can be measured.

def isComplete(R) :
    S = Set([])
    L = len(R)-1   
    for i in range(L,0,-1) :
        for j in (1..i) :
            S = S.union(Set([R[i]-R[i-j]]))
    return len(S) == R[L]

def CompleteRuler(L, S) :
    return filter(isComplete, Ruler(L, S))

We give some examples.

list(CompleteRuler(6, 3))

[[0, 2, 5, 6], [0, 1, 4, 6]]

for i in (0..5) : 
    for c in CompleteRuler(5, i) : print c

[0, 3, 4, 5]
[0, 2, 4, 5]
[0, 1, 3, 5]
[0, 1, 2, 5]
[0, 2, 3, 4, 5]
[0, 1, 3, 4, 5]
[0, 1, 2, 4, 5]
[0, 1, 2, 3, 5]
[0, 1, 2, 3, 4, 5]

If we put all complete rulers of the same length L into a bag we get the CompleteRulers(L).

def CompleteRulers(L) :
    return sum([CompleteRuler(L, i) for i in (0..L)],[])

CompleteRulers(5)

[[0, 3, 4, 5], [0, 2, 4, 5], [0, 1, 3, 5], [0, 1, 2, 5], 
[0, 2, 3, 4, 5], [0, 1, 3, 4, 5], [0, 1, 2, 4, 5],
[0, 1, 2, 3, 5], [0, 1, 2, 3, 4, 5]]

Counting complete rulers:

for n in (0..11):
    [len(CompleteRuler(n,k)) for k in (0..n)]

[1]
[0, 1]
[0, 0, 1]
[0, 0, 2, 1]
[0, 0, 0, 3, 1]
[0, 0, 0, 4, 4, 1]
[0, 0, 0, 2, 9, 5, 1]
[0, 0, 0, 0, 12, 14, 6, 1]
[0, 0, 0, 0, 8, 27, 20, 7, 1]
[0, 0, 0, 0, 4, 40, 48, 27, 8, 1]
[0, 0, 0, 0, 0, 38, 90, 75, 35, 9, 1]
[0, 0, 0, 0, 0, 30, 134, 166, 110, 44, 10, 1]

CompleteRulers(L, S)

L\S	0	1	2	3	4	5	6	7	8	9	10	11	sum
0	1												1
1	0	1											1
2	0	0	1										1
3	0	0	2	1									3
4	0	0	0	3	1								4
5	0	0	0	4	4	1							9
6	0	0	0	2	9	5	1						17
7	0	0	0	0	12	14	6	1					33
8	0	0	0	0	8	27	20	7	1				63
9	0	0	0	0	4	40	48	27	8	1			128
10	0	0	0	0	0	38	90	75	35	9	1		248
11	0	0	0	0	0	30	134	166	110	44	10	1	495

This is sequence A103294. In the triangle the length of the rulers increase from top to bottom and the number of segments increase from left to right, entries above the main diagonal are 0. The number of complete rulers with length n are the row sums A103295. The most important sequence is the irregular diagonal to the right of the zero entries: the number of perfect rulers with length n A103300.

Perfect Rulers

A ruler r is a perfect ruler if it is complete and no complete ruler with the same length possesses less marks.

def PerfectRulers(L) :
    for i in (0..L) :
        R = CompleteRuler(L, i)
        if len(R) > 0 : return R
    return []

PerfectRulers(5)

[[0, 3, 4, 5], [0, 2, 4, 5], [0, 1, 3, 5], [0, 1, 2, 5]]

for i in (0..6) :
    [c for c in PerfectRulers(i)]

[[0]]
[[0, 1]]
[[0, 1, 2]]
[[0, 2, 3], [0, 1, 3]]
[[0, 2, 3, 4], [0, 1, 3, 4], [0, 1, 2, 4]]
[[0, 3, 4, 5], [0, 2, 4, 5], [0, 1, 3, 5], [0, 1, 2, 5]]
[[0, 2, 5, 6], [0, 1, 4, 6]]

A more appropriate name for len(x) would be cardinality(x).

len(PerfectRulers(10))

len(CompleteRulers(10))

Representations of rulers

First we look at a symbolic representation which captures the intuitive meaning of a ruler.

def Ruler_AsRuler(R) :
    l = 0
    S = ""
    for i in range(0, len(R)) :
        while l < R[i] - i :
            S = S + '-';
            l = l + 1
        S = S + '|';
    return S

Ruler_AsRuler([0,1,4,10,16,18,21,23])

'||--|-----|-----|-|--|-|'

If we substitute the symbols by zeros and ones we might get the people from the CS department on board.

def Ruler_AsBinaryString(R) :
    l = 0
    S = ""
    for i in range(0, len(R)) :
        while l < R[i] - i :
            S = S + '0';
            l = l + 1
        S = S + '1';
    return S

for c in PerfectRulers(5) : print Ruler_AsBinaryString(c)

Ruler_AsBinaryString([0, 2, 5, 6])

'1010011'

bin(83)

'0b1010011'

def Ruler_AsInteger(R) :
    return int(Ruler_AsBinaryString(R),2)

Ruler_AsInteger([0, 2, 5, 6])

Finally we look at the difference representation of a ruler.

def DiffRep(R):
    L = []
    for i in (1..len(R)-1) :
       L.append(R[i] - R[i-1])
    return L

DiffRep([0, 4, 5, 9])

[4, 1, 4]

Partsum([4,1,4])

[0, 4, 5, 9]

Clearly the difference representation of a ruler is nothing but the composition to which we referred in the definition of a ruler.

def Composition(R):
    return DiffRep(R)

Ordering rulers

for i in (0..5) :
    sorted([Ruler_AsInteger(c) for c in CompleteRulers(i)])

[1]
[3]
[7]
[11, 13, 15]
[23, 27, 29, 31]
[39, 43, 47, 53, 55, 57, 59, 61, 63]

for i in (0..7) :
    sorted([Ruler_AsInteger(c) for c in PerfectRulers(i)])

[1]
[3]
[7]
[11, 13]
[23, 27, 29]
[39, 43, 53, 57]
[83, 101]
[143, 151, 167, 171, 179, 203, 205, 211, 213, 229, 233, 241]

SPR = sorted(sum(([Ruler_AsInteger(c) for c in PerfectRulers(i)]
      for i in (0..7)),[]))
SPR

[1, 3, 7, 11, 13, 23, 27, 29, 39, 43, 53, 57, 83, 101, 143,
 151, 167, 171, 179, 203, 205, 211, 213, 229, 233, 241]

If we speak of the natural order of rulers we mean the order given by this procedure.

The output below shows the perfect rulers as binary strings in their natural order.

for c in SPR : print bin(c).lstrip("0b")

Let's have a quick look at the Hamming distances of the rulers with equal length in this sequence.

def HammingDistance(s, t) :
    assert len(s) == len(t)
    return sum(a != b for a, b in zip(s, t))

T = sorted([Ruler_AsInteger(c) for c in PerfectRulers(12)])
b = "0000000000000"
L = []
for c in T : 
    a = bin(c).lstrip("0b")
    L.append(HammingDistance(a, b))
    b = a
L

[6, 4, 6, 2, 2, 6, 4, 6, 6, 2, 6, 2, 6, 4]

Optimal rulers

A ruler is optimal if it is perfect and no perfect ruler with the same number of segments has a greater length.

Each row and each column of the matrix CompleteRuler(L, S) has only finite many entries different from 0. Moreover, if S ≤ L and CompleteRuler(L, S) = 0 then CompleteRuler(K, S) = 0 for all L ≤ K and CompleteRuler(L, N) = 0 for all N ≤ S.

Thus we have the characterization of a nonempty ruler R:

R is perfect iff
R is in CompleteRuler(L, S) and CompleteRuler(L, S-1) = 0;

R is optimal iff
R is in CompleteRuler(L, S) and CompleteRuler(L+1, S) = 0.

The list below displays only one out of the pair [r, reverse(r)], i. e. disregards the mirror-symmetric rulers.

OptimalRulers = [
[0],
[0, 1],
[0, 1, 3],
[0, 1, 4, 6],
[0, 1, 4, 7, 9],
[0, 1, 2, 6, 9],
[0, 1, 6, 9, 11, 13],
[0, 1, 4, 5, 11, 13],
[0, 1, 2, 6, 10, 13],
[0, 1, 8, 11, 13, 15, 17],
[0, 1, 4, 10, 12, 15, 17],
[0, 1, 2,  8, 12, 15, 17],
[0, 1, 2,  8, 12, 14, 17],
[0, 1, 2,  6, 10, 14, 17],
[0, 1, 2,  3,  8, 13, 17],
[0, 1, 4, 10, 16, 18, 21, 23],
[0, 1, 2, 11, 15, 18, 21, 23],
[0, 1, 4, 10, 16, 22, 24, 27, 29],
[0, 1, 3,  6, 13, 20, 24, 28, 29],
[0, 1, 2, 14, 18, 21, 24, 27, 29],
[0, 1, 3, 6, 13, 20, 27, 31, 35, 36],
[0, 1, 3, 6, 13, 20, 27, 34, 38, 42, 43],
[0, 1, 3, 6, 13, 20, 27, 34, 41, 45, 49, 50],
[0, 1, 2, 3, 23, 28, 32, 36, 40, 44, 47, 50],
[0, 1, 5, 8, 12, 21, 30, 39, 48, 53, 54, 56, 58],
[0, 1, 3, 6, 17, 24, 27, 38, 45, 49, 53, 57, 58],
[0, 1, 3, 6, 17, 20, 27, 35, 45, 49, 53, 57, 58],
[0, 1, 2, 8, 15, 16, 26, 36, 46, 49, 53, 55, 58],
[0, 1, 2, 6,  8, 17, 26, 35, 44, 47, 54, 57, 58],
[0, 1, 2, 3, 27, 32, 36, 40, 44, 48, 52, 55, 58],
[0, 1, 2, 8, 15, 16, 26, 36, 46, 56, 59, 63, 65, 68],
[0, 1, 2, 5, 10, 15, 26, 37, 48, 54, 60, 66, 67, 68],
[0, 1, 2, 5, 10, 15, 26, 37, 48, 59, 65, 71, 77, 78, 79],
[0, 1, 2, 5, 10, 15, 26, 37, 48, 59, 70, 76, 82, 88, 89, 90],
[0, 1, 2, 5, 10, 15, 26, 37, 48, 59, 70, 81, 87, 93, 99, 100, 101]
]

There are 155050 perfect rulers with length in [0, 123], but only 74 optimal rulers in this range.

Optimal rulers are the most interesting creatures in our setup. Unfortunately no blueprint for these rulers is known. Therefore we turn to the Wichmann rulers which might provide an easy to compute substitute for optimal rulers. However, for convenience, we provide a function which returns for some small arguments optimal rulers based on known data.

OR = [[0,0],[1,1],[3,2],[6,3],[9,4],[13,5],[17,6],[23,7],
     [29,8],[36,9]]

def OptimalRulers(S):
    assert(S in (0..9))
    return CompleteRuler(OR[S][0],OR[S][1])

for i in (0..6) :
    for c in OptimalRulers(i) : print Ruler_AsBinaryString(c)

1
11
1011
1101
1010011
1100101
1001000111
1010010011
1100100101
1110001001
10010001000111
10100000110011
10101001000011
11000010010101
11001100000101
11100010001001
100010000100001111
100100010001000111
100101000100000111
101001000100000111
101001010000010011
101010100100000011
110000001001010101
110010000010100101
111000001000100101
111000001000101001
111000100010001001
111100001000010001

Wichmann rulers

B. Wichmann. A note on restricted difference bases.
J. London Math. Soc. 38, 1962, 465--466

Let us look at two examples first.

R = [0, 1, 2, 8, 15, 16, 26, 36, 46, 56, 59, 63, 65, 68]
Composition(R)

[1, 1, 6, 7, 1, 10, 10, 10, 10, 3, 4, 2, 3]

S = [0, 1, 2, 5, 10, 15, 26, 37, 48, 54, 60, 66, 67, 68]
Composition(S)

[1, 1, 3, 5, 5, 11, 11, 11, 6, 6, 6, 1, 1]

Both rulers R and S are optimal. However the second one has a special structure which can be read of from his associated composition. To see this let us look at the type of the composition of S.

type(R) = [1*2, 6*1,7*1,1*1,10*4, 3*1, 4*1, 2*1, 3*1]

type(S) = [1*2, 3*1, 5*2, 11*3, 6*3, 1*2]

The symbolic notation 'p*m' means 'p occurs m times in immediate succession'. 'p' denotes the part and 'm' the multiplicity.

Def. The type of a ruler is the type of its associated composition.

Def. A ruler is of Wichmann type if it's type has the form, for r ≥ 0, s ≥ 0,

W(r, s) = [1*r, r+1, (2r+1)*r, (4r+3)*s, (2r+2)*(r+1), 1*r]

We see that the second ruler is of Wichmann type: type(S) = W(2,3).

If a ruler R is of Wichmann type then the number of segments of R is
S = 4r+s+2 and the length of R is L = 4r(r+s+2) + 3(s+1).

def flatten(I) :
    """ Utility function unrelated to rulers """
    L = []
    for i in I :
        if hasattr(i, "__iter__") :
            L.extend(flatten(i))
        else :
            L.append(i)
    return L
    
def Wichmann(r,s) :
    C = [[1]*r,r+1,[2*r+1]*r,[4*r+3]*s,[2*r+2]*(r+1),[1]*r]
    return Partsum(flatten(C))

Wichmann(2,3)

[0, 1, 2, 5, 10, 15, 26, 37, 48, 54, 60, 66, 67, 68]

Or as a binary strings:

Ruler_AsBinaryString(Wichmann(2,3))

'111001000010000100000000001000000000010000000000100000100000100000111'

Since the 1s are the markers of the ruler and the number of markers is M = S + 1 the binary string representation of a Wichmann ruler of type (r, s) contains exactly 4r+s+3 times the 1.

The optimal ruler conjecture

Not every optimal ruler is a ruler of Wichmann type. In the last section we saw an example for such a ruler.

However it was conjectured:

All optimal rulers with more than 13 segments are either Wichmann rulers or the mirror images of Wichmann rulers.

If the conjecture is true than the sequence A004137 continues 168, 183, 198, 213, 232, 251, 270, 289, 308, 327,...

A more cautious conjecture is: In the set of optimal rulers with S segments where S > 12 there exists at least one ruler of Wichmann type.

In view of the small basis of evidence at the current state this conjecture should preferably be regarded as a challenge for research. In any case it is an interesting observation and an investigation of the relation between optimal rulers and Wichmann rulers appears to be a worthwhile endeavor.

It should also be noted that rulers with different Wichmann types can fall into the same class of optimal rulers as the example below shows.

print Wichmann(2,8)
print Wichmann(3,4)

[0,1,2,5,10,15,26,37,48,59,70,81,92,103,109,115,121,122,123]
[0,1,2,3, 7,14,21,28,43,58,73,88,96,104,112,120,121,122,123]

See also the sequences A193802 and A193803.

Counting Rulers

Note that we use the number of segments S rather than the number of marks M as our primary id. A larger table can be found here.

Seg- ment	Length	Perfect Optimal	Sum
0	0	1	1
1	1	1	1
2	2	1	3
2	3	2	3
3	4	3	9
	5	4
	6	2
4	7	12	24
	8	8
	9	4
5	10	38	88
	11	30
	12	14
	13	6
OEIS	A103297 A004137	A103300 A103299	A103301

The challenges now are:

Extend this table!
Generate perfect rulers fast!
(Dis-)Prove the optimal ruler conjecture.

Here you can download the Sage worksheet.

User:Peter Luschny/PerfectRulers

Contents

PERFECT AND OPTIMAL RULERS

Introduction

Rulers in a Nutshell

A SAGE WORKSHEET

Rulers

Complete Rulers

Perfect Rulers

Representations of rulers

Ordering rulers

Optimal rulers

Wichmann rulers

The optimal ruler conjecture

Counting Rulers

Navigation menu

Views

Personal tools

Navigation

Search

Tools

L\S	0	1	2	3	4	5	6	7	8	9	10	11	sum
0	1												1
1	0	1											1
2	0	0	1										1
3	0	0	2	1									3
4	0	0	0	3	1								4
5	0	0	0	4	4	1							9
6	0	0	0	2	9	5	1						17
7	0	0	0	0	12	14	6	1					33
8	0	0	0	0	8	27	20	7	1				63
9	0	0	0	0	4	40	48	27	8	1			128
10	0	0	0	0	0	38	90	75	35	9	1		248
11	0	0	0	0	0	30	134	166	110	44	10	1	495

L\S	0	1	2	3	4	5	6	7	8	9	10	11	sum
0	1												1
1	0	1											1
2	0	0	1										1
3	0	0	2	1									3
4	0	0	0	3	1								4
5	0	0	0	4	4	1							9
6	0	0	0	2	9	5	1						17
7	0	0	0	0	12	14	6	1					33
8	0	0	0	0	8	27	20	7	1				63
9	0	0	0	0	4	40	48	27	8	1			128
10	0	0	0	0	0	38	90	75	35	9	1		248
11	0	0	0	0	0	30	134	166	110	44	10	1	495

L\S	0	1	2	3	4	5	6	7	8	9	10	11	sum
0	1												1
1	0	1											1
2	0	0	1										1
3	0	0	2	1									3
4	0	0	0	3	1								4
5	0	0	0	4	4	1							9
6	0	0	0	2	9	5	1						17
7	0	0	0	0	12	14	6	1					33
8	0	0	0	0	8	27	20	7	1				63
9	0	0	0	0	4	40	48	27	8	1			128
10	0	0	0	0	0	38	90	75	35	9	1		248
11	0	0	0	0	0	30	134	166	110	44	10	1	495