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)