Modular Fibonacciësque Sequences.
Version of Sunday 16 October 2016.
Dave Barber's other pages.

§1. A modular fibonacciësque sequence is defined by:

The target range is the set of nonnegative integers less than the modulus. Should any number in the sequence be calculated to lie outside the target range, the modulus can be added or subracted (perhaps repeatedly) to bring it into the target range; in particular, the starters can be restricted to the target range without loss of generality.

This is modular behavior, and the terms in the sequences will always conform to it. By contrast, the terms will sometimes be notated by subscripted variables, and the subscripts will use ordinary arithmetic, not modular.

If the starters are exchanged, a different sequence results.

These sequences are called "fibonacciësque" rather than "Fibonacci" because the starters need not be taken from the celebrated Fibonacci sequence. The diaeresis is placed over the e to emphasize that the e is to be pronounced separately from the adjoining i.


§2. Using i as an arbitrary integer, the first starter can be written:

Fi

and the second can be written:

Fi+1

By definition, the term following the second starter will be:

Fi+2 = Fi+1 + Fi [modular]

To be consistent, the term preceding the first starter must be:

Fi−1 = Fi+1Fi [modular]

The sequence can be extended without bound.

All this is unsurprising for anything Fibonacci-based. The point of interest here is that when the sequence is extended in both directions far enough, the two ends meet: a modular fibonacciësque sequence is periodic. Pertinent results have been published by Coleman et alii.

A reason that the subscripts do not use modular arithmetic is that the period of the sequence quite often differs from the modulus of term calculation.


§3. In the following example sequence, of which exactly one period is represented between square brackets, each term is the sum of the previous two terms under a modulus of 8. The sequence wraps around at the end, with (modularly) 6 + 3 = 1 and 3 + 1 = 4; or equivalently, 1 − 3 = 6 and 4 − 1 = 3.

[ 1 4 5 1 6 7 5 4 1 5 6 3 ]

Any two consecutive terms can be designated as the starters, such as (6,7) or (5,4). Also valid is (3,1), which wraps around. The conventional practice is to use the lowest number in the sequence for the first starter. If there is a tie, the smallest number that follows the first starter anywhere will be used. In this example, (1,4) is preferred over (1,5) or (1,6); the term minimal is hence used for (1,4).

By repeating and grouping terms, this notation can be expanded into a sequence of ordered pairs, as below, containing the same information. The excerpt (a, b) (b, c) means c = a + b (mod 8).

[ (1,4) (4,5) (5,1) (1,6) (6,7) (7,5) (5,4) (4,1) (1,5) (5,6) (6,3) (3,1) ]

In this notation, a subsequence such as (a, b) (d, c) must not occur if d is not equal to b.


§4. The main part of this report is a listing of fibonacciësque sequences for various moduli. Table A is an example:

table A — modulus 8
periodadditive sequence
1[ 0 ]
12[ 0 1 1 2 3 5 0 5 5 2 7 1 ]
6[ 0 2 2 4 6 2 ]
12[ 0 3 3 6 1 7 0 7 7 6 5 3 ]
3[ 0 4 4 ]
6[ 0 6 6 4 2 6 ]
12[ 1 3 4 7 3 2 5 7 4 3 7 2 ]
12[ 1 4 5 1 6 7 5 4 1 5 6 3 ]
census: 1×1 + 3×1 + 6×2 + 12×4 = 64 = 8×8

The table describes the sequence as additive to distinguish it from some multiplicative sequences that appear later.

All sequences are periodic, and exactly one period of each is displayed. The census summarizes how many sequences are of each period.

This for instance:

[ 0 6 6 4 2 6 ]

could have (more repetitively) been written:

[ … 2 6 0 6 6 4 2 6 0 6 6 4 2 6 0 6 6 4 … ]

In the manner of the previous section, table A can be expanded into table B:

table B — modulus 8
periodadditive sequence
1[ (0,0) ]
12[ (0,1) (1,1) (1,2) (2,3) (3,5) (5,0) (0,5) (5,5) (5,2) (2,7) (7,1) (1,0) ]
6[ (0,2) (2,2) (2,4) (4,6) (6,2) (2,0) ]
12[ (0,3) (3,3) (3,6) (6,1) (1,7) (7,0) (0,7) (7,7) (7,6) (6,5) (5,3) (3,0) ]
3[ (0,4) (4,4) (4,0) ]
6[ (0,6) (6,6) (6,4) (4,2) (2,6) (6,0) ]
12[ (1,3) (3,4) (4,7) (7,3) (3,2) (2,5) (5,7) (7,4) (4,3) (3,7) (7,2) (2,1) ]
12[ (1,4) (4,5) (5,1) (1,6) (6,7) (7,5) (5,4) (4,1) (1,5) (5,6) (6,3) (3,1) ]
census: 1×1 + 3×1 + 6×2 + 12×4 = 64 = 8×8

Essential is that each possible ordered pair occurs exactly once in table B.

For any modulus there will be a sequence of period 1, containing only zero. Beyond that, there is great variety from one modulus to the next, and there is no simple way to predict how many distinct sequences there are, or what their periods will be.


§5. The purpose of this report is to provide tables, corresponding to table A, that exhibit fibonacciësque sequences for a variety of moduli. Large moduli generally give rise to large tables. Within each modulus, sequences are sorted by minimal starters.

additive fibonacciësque sequences
grouped by modulus
1 ‐ 10 11 ‐ 20 21 ‐ 30 31 ‐ 40
41 ‐ 45 46 ‐ 50 51 ‐ 55 56 ‐ 60
61 ‐ 65 66 ‐ 70 71 ‐ 75 76 ‐ 80
81 ‐ 82 83 ‐ 84 85 ‐ 86 87 ‐ 88 89 ‐ 90
91 ‐ 92 93 ‐ 94 95 ‐ 96 97 ‐ 98 99 ‐ 100
101 ‐ 102 103 ‐ 104 105 ‐ 106 107 ‐ 108 109 ‐ 110
111 ‐ 112 113 ‐ 114 115 ‐ 116 117 ‐ 118 119 ‐ 120
digest of censuses


§6. What happens if multiplication is substituted for addition? In some cases, it works. Here are examples:

multiplicative fibonacciësque sequences
grouped by modulus
primes 2 ‐ 29 primes 31 ‐ 47 primes 53 ‐ 71 primes 73 ‐ 79
primes 83 ‐ 89 primes 97 ‐ 101 primes 103 ‐ 107 primes 109 ‐ 113
digest of censuses

Conjecture: Given a prime number p, it is always possible to form:

a system of multiplicative modular fibonacciësque sequences, with modulus p, on the set { 1 … p − 1 }
which corresponds to
the system of additive modular fibonacciësque sequences, with modulus p − 1, on the set { 0 … p − 2 }.

Appropriate is a detailed examination of one example. Start with these additive sequences:

table C — modulus 12
lineperiodadditive sequence
a 1[  0 ]
b24 [  0  1  1  2  3  5  8  1  9 10  7  5  0  5  5 10  3  1  4  5  9  2 11  1 ]
c24 [  0  2  2  4  6 10  4  2  6  8  2 10  0 10 10  8  6  2  8 10  6  4 10  2 ]
d 6 [  0  3  3  6  9  3 ]
e 8 [  0  4  4  8  0  8  8  4 ]
f 3 [  0  6  6 ]
g24 [  0  7  7  2  9 11  8  7  3 10  1 11  0 11 11 10  9  7  4 11  3  2  5  7 ]
h 6 [  0  9  9  6  3  9 ]
i24 [  1  3  4  7 11  6  5 11  4  3  7 10  5  3  8 11  7  6  1  7  8  3 11  2 ]
j24 [  1  5  6 11  5  4  9  1 10 11  9  8  5  1  6  7  1  8  9  5  2  7  9  4 ]
census: 1×1 + 3×1 + 6×2 + 8×1 + 24×5 = 144 = 12×12

and these multiplicative sequences:

table D — modulus 13
lineperiodmultiplicative sequence
q 1 [  1 ]
r24 [  1  2  2  4  8  6  9  2  5 10 11  6  1  6  6 10  8  2  3  6  5  4  7  2 ]
s 8 [  1  3  3  9  1  9  9  3 ]
t24 [  1  4  4  3 12 10  3  4 12  9  4 10  1 10 10  9 12  4  9 10 12  3 10  4 ]
u 6 [  1  5  5 12  8  5 ]
v24 [  1  7  7 10  5 11  3  7  8  4  6 11  1 11 11  4  5  7  9 11  8 10  2  7 ]
w 6 [  1  8  8 12  5  8 ]
x 3 [  1 12 12 ]
y24 [  2  6 12  7  6  3  5  2 10  7  5  9  6  2 12 11  2  9  5  6  4 11  5  3 ]
z24 [  2  8  3 11  7 12  6  7  3  8 11 10  6  8  9  7 11 12  2 11  9  8  7  4 ]
census: 1×1 + 3×1 + 6×2 + 8×1 + 24×5 = 144 = 12×12

Construct the following one-to-correspondence between the additive set { 0 … p − 2 } and the multiplicative set { 1 … p − 1 }:

table E
add  0 1 2 3  4 5 6 7  8 91011
mul  1 2 4 8  3 61211  9 510 7

Now tables C and D can be interwoven, using table E, to form table F:

table F
period oper line sequences
 1adda [  0 ]
mulq [  1 ]
24addb [  0  1  1  2  3  5  8  1  9 10  7  5  0  5  5 10  3  1  4  5  9  2 11  1 ]
mulr [  1  2  2  4  8  6  9  2  5 10 11  6  1  6  6 10  8  2  3  6  5  4  7  2 ]
24addc [  0  2  2  4  6 10  4  2  6  8  2 10  0 10 10  8  6  2  8 10  6  4 10  2 ]
mult [  1  4  4  3 12 10  3  4 12  9  4 10  1 10 10  9 12  4  9 10 12  3 10  4 ]
 6addd [  0  3  3  6  9  3 ]
mulw [  1  8  8 12  5  8 ]
 8adde [  0  4  4  8  0  8  8  4 ]
muls [  1  3  3  9  1  9  9  3 ]
 3addf [  0  6  6 ]
mulx [  1 12 12 ]
24addg [  0  7  7  2  9 11  8  7  3 10  1 11  0 11 11 10  9  7  4 11  3  2  5  7 ]
mulv [  1 11 11  4  5  7  9 11  8 10  2  7  1  7  7 10  5 11  3  7  8  4  6 11 ]
notation has been rotated
 6addh [  0  9  9  6  3  9 ]
mulu [  1  5  5 12  8  5 ]
24addi [  1  3  4  7 11  6  5 11  4  3  7 10  5  3  8 11  7  6  1  7  8  3 11  2 ]
mulz [  2  8  3 11  7 12  6  7  3  8 11 10  6  8  9  7 11 12  2 11  9  8  7  4 ]
24addj [  1  5  6 11  5  4  9  1 10 11  9  8  5  1  6  7  1  8  9  5  2  7  9  4 ]
muly [  2  6 12  7  6  3  5  2 10  7  5  9  6  2 12 11  2  9  5  6  4 11  5  3 ]
census: 1×1 + 3×1 + 6×2 + 8×1 + 24×5 = 144 = 12×12