# Golomb Rulers and Fibonacci Sequences

Golomb Rulers and Fibonacci Sequences

A generalized Fibonacci sequence is defined by . A maximal generalized Fibonacci sequence mod is a generalized Fibonacci sequence with smallest period equal to length -1.

F(n+2)=aF(n+1)+bF(n)

p

2

p

For example, with , , (or equivalently with prime 5 and pair ), the sequence starts of length 24 and then repeats. From that initial subsequence, construct the 24 overlapping coordinates: ; apart from , they are a permutation of the coordinates for a 5×5 table with rows and columns both indexed by 0 to 4. Since there are no smaller periods, all coordinates except are represented. Place the numbers at those coordinates and leave in the upper left blank.

a=1

b=3

p=5

(1,3)

(0,1,1,4,2,4,0,2,2,3,4,3,0,4,4,1,3,1,0,3,3,2,1,2)

(0,1),(1,1),(1,4),(4,2),(2,4),…,(1,2),(2,0)

(0,0)

(0,0)

0,1,2,3,…,-2

2

p

(0,0)

A Golomb ruler is a set of marks at integer positions along a line, such that no two pairs of marks are the same distance apart. Selecting any row or column other than the first (with index 0) gives marks for a nonoptimal Golomb ruler of length -1 that wraps around (i.e. the first and last marks are also subtracted). No distance between marks is repeated.

2

p

In the example under discussion, the second column (with index 1) is , which are the marks. The differences are . The negative differences mod 24 are . No values repeat; the missing values are .

(0,1,14,16,21)

{1,2,5,7,13,14,15,16,20,21}

{23,22,19,17,11,10,9,8,4,3}

(6,12,18)