Fibonacci's nephews

Construct a sequence of numbers in the following way: start with the numbers 0 and 1 and then always compute the difference between the last number in the sequence and twice the previous one. Put the result at the end of the row and continue in this manner. So, the first number added to the end of the sequence is 1-2*0=1, the next one is 1-2*1 = -1 and so on:

   1 - 2*  0  =  1
   1 - 2*  1  = -1
  -1 - 2*  1  = -3
  -3 - 2*(-1) = -1
  -1 - 2*(-3) =  5
   5 - 2*(-1) =  7
   ....

The first few elements of the sequence are:

   0   1   1  -1  -3  -1   5   7  -3 -17 -11  23  45  -1  -91 ...

Although the sequence is slightly more erratic than the Fibonacci sequence, it has similar properties and deserves to be called one of its nephews. This time we are interested in remainders after division by q=5. Remember that this modular variant can be built by simply generating it using modular arithmetic:

   1 - 2*  0  =  1  (5)
   1 - 2*  1  =  4  (5)
   4 - 2*  1  =  2  (5)
   2 - 2*  4  =  4  (5)
   4 - 2*  2  =  0  (5)
   0 - 2*  4  =  2  (5)
   ....

And the entire sequence runs as follows:

   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 ...

This sequence has period 24 which is the correct size for a semi-affine plane of order 5. You may easily check that indeed every possible pair of coordinates occurs as a consecutive pair.

To construct a CDS from this sequence we do not even need to build the entire semi-affine plane, we just need to know what the points on only one of its lines are. My favourite lines are [1,1] and [1,0]. For a point (x,y) to be on the line [1,1] we must have x+y=1 (modulo 5) - which is quite easy to check. It is even easier to see whether a point (x,y) is on the line [1,0]: just check whether x equals 1. The results are depicted below:

 sequence : 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,0]:    # #                         #   #         #
 numbering:  0 1 2 3 4 5 6 7 8 91011121314151617181920212223

We find two sets which are a shift of the same CDS of size 5: {0,3,4,17,19} and {1,2,15,17,22}, both with modulus 24. To make doubly sure you should construct all the lines and verify that they are all shifts of this CDS, or you may compute a difference table:

    0    3    4   17   19  (24)
   21    0    1   14   16
   20   23    0   13   15
    7   10   11    0    2
    5    8    9   22    0

and check that all non-diagonal elements are different.

Other nephews of Fibonacci

Unfortunately, like the Fibonacci series, this series only works for a small number of primes q as well. Luckily, for other primes we may use still other series of this kind.

Choose any two numbers A and B (A and B may be positive or negative and need not be different). We build the (A,B)-nephew of Fibonacci as follows (the official name for these sequences is `linear recurrences of degree 2'): start with the numbers 0 and 1 and then always compute A times the last number plus B times the previous number. Put that result at the end of the sequence and start all over again.

The Fibonacci sequence is the linear recurrence with A=1 and B=1. The sequence at the top of this page has A=1 and B=-2. We give some more examples:

 (A,B) | sequence
-----------------
 (1,2) | 0   1   1   3   5  11  21  43  85 171 ...
 (2,1) | 0   1   2   5  12  29  70 169 408 985 ...
(-2,1) | 0   1  -2   5 -12  29 -70 169 -408 985 ...
(2,-3) | 0   1   2   1  -4 -11 -10  13  56  73 ...

The modular versions of some of these sequences will generate a semi-affine plane for well-chosen prime numbers q. For example, the (2,-3)-sequence can be used when q=7:

        0 1 2 1 3 3 4 6 0 3 6 3 2 2 5 4 0 2 4 2 6 6 1 5
           #   #                                     #
        0 6 5 6 4 4 3 1 0 4 1 4 5 5 2 3 0 5 3 5 1 1 6 2 ...
                       #     #                   # #

This results in the CDS {0,2,21,30,33,43,44} of size 7 and modulus 48.

Which nephew for which prime ?

There is no easy rule to tell you which nephew you should use for which prime q, so you have to try a few until you find one with period q^2-1. Fortunately, for a given prime q there are many nephews that work. Also, the following guidelines might help:

You need only try sequences with A,B in the range 1..q-1. Agreed, we have used examples with B outside this range, but we could equally well have used (1,3) when q=5 and (2,4) when q=7. In general the modular sequences (A,B) and (A',B') (for the same modulus q) are identical whenever both A=A' (q) and B=B' (q).
If there is a number z such that z^2=A*z+B (mod q) then the sequence will NOT work.
In a good sequence, the second zero always occurs exactly q+1 positions behind the first zero. (Unfortunately, some bad sequences have this property too.)

Problems

Verify that {0,2,21,30,33,43,44} modulo 48 is indeed a CDS.
Find a CDS of size 11 and modulus 120.
Verify the guidelines above for all semi-affine CDSs constructed so far.
The (2,-1)-nephew will not work for any prime number q. Can you prove this?

How to make perfect CDSs

97/01/03 - Kris Coolsaet