W

 Will Nicholes

Fibonacci numbers and Pisano periods

The Fibonacci numbers (sequence A000045) form one of the most important and well-known sequences in mathematics.

The sequence is very easy to construct: start with 0 and 1 as the first two numbers in the sequence, and after that, every new term in the sequence is the sum of the previous two:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377...

If we drop everything except the rightmost digit of each number in the sequence (A003893), we can see that those digits will eventually repeat:

0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7,
0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9,
0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3,
0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1,
0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7...

There are exactly 60 terms in this sequence before it begins repeating. This is known as its Pisano period. By considering only the rightmost digit, we are looking at the Fibonnaci numbers modulo 10.

There are different Pisano periods for different divisors. For example, here are the Fibonacci numbers, modulo 9 (A007887):

0, 1, 1, 2, 3, 5, 8, 4, 3, 7, 1, 8,
0, 8, 8, 7, 6, 4, 1, 5, 6, 2, 8, 1,
0, 1, 1, 2, 3, 5, 8, 4, 3, 7, 1, 8...

In this case the numbers repeat after 24 terms, so for this sequence mod 9 the Pisano period is 24.

The Pisano periods for mod 1, 2, 3, etc. are 1, 3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48... (sequence A001175.)

Let’s return to mod 10. There are 100 different pairs of decimal digits: i.e. 0,0; 0,1; 0,2... 9,8 and 9,9. But only 60 of these pairs appear in the mod 10 sequence (keeping in mind that each of the 60 terms can act as either the first or second digit in a pair.) Where are the other 40 pairs?

It turns out they appear in different, but related, sequences. Here are the Fibonacci-like sequences that appear mod 10:

Period1st2ndFull sequence
1000
60010, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1
20020, 2, 2, 4, 6, 0, 6, 6, 2, 8, 0, 8, 8, 6, 4, 0, 4, 4, 8, 2
3050, 5, 5
12131, 3, 4, 7, 1, 8, 9, 7, 6, 3, 9, 2
4262, 6, 8, 4

The periods of these 6 sequences add up to 100: 1 + 60 + 20 + 3 + 12 + 4, which is what we’d expect for a mod 10 sequence.

Similarly, for mod 9 there are 81 possible pairs, of which only 24 appear in the main sequence, so the remaining 57 pairs must appear in different mod 9 sequences, as we’ll see below.

Table 1 below shows all of the Fibonacci-like sequences for mod 1 through mod 16.

Legend for Table 1

Column descriptionOEIS
MModulus for the sequence shownA179390
ΣSum of all the periods for the mod specifiedA000290
#Number of sequences for the mod specifiedA015134
PPeriod of the sequence specifiedA179393
1First number in the sequenceA179391
2Second number in the sequenceA179392

Table 1

MΣ#P12Full sequence
1111000
2421000
23010, 1, 1 (A011655)
3921000
38010, 1, 1, 2, 0, 2, 2, 1 (A082115)
41641000
46010, 1, 1, 2, 3, 1 (A079343)
43020, 2, 2
46030, 3, 3, 2, 1, 3
52531000
520010, 1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, 2, 2, 4, 1 (A082116)
54131, 3, 4, 2 (A070352)
63641000
624010, 1, 1, 2, 3, 5, 2, 1, 3, 4, 1, 5, 0, 5, 5, 4, 3, 1, 4, 5, 3, 2, 5, 1 (A082117)
68020, 2, 2, 4, 0, 4, 4, 2
63030, 3, 3
74941000
716010, 1, 1, 2, 3, 5, 1, 6, 0, 6, 6, 5, 4, 2, 6, 1 (A105870)
716020, 2, 2, 4, 6, 3, 2, 5, 0, 5, 5, 3, 1, 4, 5, 2
716030, 3, 3, 6, 2, 1, 3, 4, 0, 4, 4, 1, 5, 6, 4, 3
86481000
812010, 1, 1, 2, 3, 5, 0, 5, 5, 2, 7, 1 (A079344)
86020, 2, 2, 4, 6, 2
812030, 3, 3, 6, 1, 7, 0, 7, 7, 6, 5, 3
83040, 4, 4
86060, 6, 6, 4, 2, 6
812131, 3, 4, 7, 3, 2, 5, 7, 4, 3, 7, 2 (A111958)
812141, 4, 5, 1, 6, 7, 5, 4, 1, 5, 6, 3
98151000
924010, 1, 1, 2, 3, 5, 8, 4, 3, 7, 1, 8, 0, 8, 8, 7, 6, 4, 1, 5, 6, 2, 8, 1 (A007887)
924020, 2, 2, 4, 6, 1, 7, 8, 6, 5, 2, 7, 0, 7, 7, 5, 3, 8, 2, 1, 3, 4, 7, 2
98030, 3, 3, 6, 0, 6, 6, 3
924040, 4, 4, 8, 3, 2, 5, 7, 8, 1, 4, 5, 0, 5, 5, 1, 6, 7, 4, 2, 6, 8, 5, 4
1010061000
1060010, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1 (A003893)
1020020, 2, 2, 4, 6, 0, 6, 6, 2, 8, 0, 8, 8, 6, 4, 0, 4, 4, 8, 2
103050, 5, 5
1012131, 3, 4, 7, 1, 8, 9, 7, 6, 3, 9, 2
104262, 6, 8, 4
11121141000
1110010, 1, 1, 2, 3, 5, 8, 2, 10, 1 (A105955)
1110020, 2, 2, 4, 6, 10, 5, 4, 9, 2
1110030, 3, 3, 6, 9, 4, 2, 6, 8, 3
1110040, 4, 4, 8, 1, 9, 10, 8, 7, 4
1110050, 5, 5, 10, 4, 3, 7, 10, 6, 5
1110060, 6, 6, 1, 7, 8, 4, 1, 5, 6
1110070, 7, 7, 3, 10, 2, 1, 3, 4, 7
1110080, 8, 8, 5, 2, 7, 9, 5, 3, 8
1110090, 9, 9, 7, 5, 1, 6, 7, 2, 9
11100100, 10, 10, 9, 8, 6, 3, 9, 1, 10
115141, 4, 5, 9, 3 (A168429)
1110181, 8, 9, 6, 4, 10, 3, 2, 5, 7 (A048271)
115282, 8, 10, 7, 6
12144101000
1224010, 1, 1, 2, 3, 5, 8, 1, 9, 10, 7, 5, 0, 5, 5, 10, 3, 1, 4, 5, 9, 2, 11, 1 (A089911)
1224020, 2, 2, 4, 6, 10, 4, 2, 6, 8, 2, 10, 0, 10, 10, 8, 6, 2, 8, 10, 6, 4, 10, 2
126030, 3, 3, 6, 9, 3
128040, 4, 4, 8, 0, 8, 8, 4
123060, 6, 6
1224070, 7, 7, 2, 9, 11, 8, 7, 3, 10, 1, 11, 0, 11, 11, 10, 9, 7, 4, 11, 3, 2, 5, 7
126090, 9, 9, 6, 3, 9
1224131, 3, 4, 7, 11, 6, 5, 11, 4, 3, 7, 10, 5, 3, 8, 11, 7, 6, 1, 7, 8, 3, 11, 2
1224151, 5, 6, 11, 5, 4, 9, 1, 10, 11, 9, 8, 5, 1, 6, 7, 1, 8, 9, 5, 2, 7, 9, 4
1316971000
1328010, 1, 1, 2, 3, 5, 8, 0, 8, 8, 3, 11, 1, 12, 0, 12, 12, 11, 10, 8, 5, 0, 5, 5, 10, 2, 12, 1 (A105994)
1328020, 2, 2, 4, 6, 10, 3, 0, 3, 3, 6, 9, 2, 11, 0, 11, 11, 9, 7, 3, 10, 0, 10, 10, 7, 4, 11, 2
1328040, 4, 4, 8, 12, 7, 6, 0, 6, 6, 12, 5, 4, 9, 0, 9, 9, 5, 1, 6, 7, 0, 7, 7, 1, 8, 9, 4
1328131, 3, 4, 7, 11, 5, 3, 8, 11, 6, 4, 10, 1, 11, 12, 10, 9, 6, 2, 8, 10, 5, 2, 7, 9, 3, 12, 2
1328141, 4, 5, 9, 1, 10, 11, 8, 6, 1, 7, 8, 2, 10, 12, 9, 8, 4, 12, 3, 2, 5, 7, 12, 6, 5, 11, 3
1328151, 5, 6, 11, 4, 2, 6, 8, 1, 9, 10, 6, 3, 9, 12, 8, 7, 2, 9, 11, 7, 5, 12, 4, 3, 7, 10, 4
1419681000
1448010, 1, 1, 2, 3, 5, 8, 13, 7, 6, 13, 5, 4, 9, 13, 8, 7, 1, 8, 9, 3, 12, 1, 13, 0, 13, 13, 12, 11, 9, 6, 1, 7, 8, 1, 9, 10, 5, 1, 6, 7, 13, 6, 5, 11, 2, 13, 1 (A105995)
1416020, 2, 2, 4, 6, 10, 2, 12, 0, 12, 12, 10, 8, 4, 12, 2
1448030, 3, 3, 6, 9, 1, 10, 11, 7, 4, 11, 1, 12, 13, 11, 10, 7, 3, 10, 13, 9, 8, 3, 11, 0, 11, 11, 8, 5, 13, 4, 3, 7, 10, 3, 13, 2, 1, 3, 4, 7, 11, 4, 1, 5, 6, 11, 3
1416040, 4, 4, 8, 12, 6, 4, 10, 0, 10, 10, 6, 2, 8, 10, 4
1448050, 5, 5, 10, 1, 11, 12, 9, 7, 2, 9, 11, 6, 3, 9, 12, 7, 5, 12, 3, 1, 4, 5, 9, 0, 9, 9, 4, 13, 3, 2, 5, 7, 12, 5, 3, 8, 11, 5, 2, 7, 9, 2, 11, 13, 10, 9, 5
1416060, 6, 6, 12, 4, 2, 6, 8, 0, 8, 8, 2, 10, 12, 8, 6
143070, 7, 7
15225121000
1540010, 1, 1, 2, 3, 5, 8, 13, 6, 4, 10, 14, 9, 8, 2, 10, 12, 7, 4, 11, 0, 11, 11, 7, 3, 10, 13, 8, 6, 14, 5, 4, 9, 13, 7, 5, 12, 2, 14, 1 (A106005)
1540020, 2, 2, 4, 6, 10, 1, 11, 12, 8, 5, 13, 3, 1, 4, 5, 9, 14, 8, 7, 0, 7, 7, 14, 6, 5, 11, 1, 12, 13, 10, 8, 3, 11, 14, 10, 9, 4, 13, 2
1520030, 3, 3, 6, 9, 0, 9, 9, 3, 12, 0, 12, 12, 9, 6, 0, 6, 6, 12, 3
1540040, 4, 4, 8, 12, 5, 2, 7, 9, 1, 10, 11, 6, 2, 8, 10, 3, 13, 1, 14, 0, 14, 14, 13, 12, 10, 7, 2, 9, 11, 5, 1, 6, 7, 13, 5, 3, 8, 11, 4
158050, 5, 5, 10, 0, 10, 10, 5
1540080, 8, 8, 1, 9, 10, 4, 14, 3, 2, 5, 7, 12, 4, 1, 5, 6, 11, 2, 13, 0, 13, 13, 11, 9, 5, 14, 4, 3, 7, 10, 2, 12, 14, 11, 10, 6, 1, 7, 8
158131, 3, 4, 7, 11, 3, 14, 2
158181, 8, 9, 2, 11, 13, 9, 7
1581131, 13, 14, 12, 11, 8, 4, 12
158262, 6, 8, 14, 7, 6, 13, 4
154393, 9, 12, 6
16256161000
1624010, 1, 1, 2, 3, 5, 8, 13, 5, 2, 7, 9, 0, 9, 9, 2, 11, 13, 8, 5, 13, 2, 15, 1 (A079345)
1612020, 2, 2, 4, 6, 10, 0, 10, 10, 4, 14, 2
1624030, 3, 3, 6, 9, 15, 8, 7, 15, 6, 5, 11, 0, 11, 11, 6, 1, 7, 8, 15, 7, 6, 13, 3
166040, 4, 4, 8, 12, 4
1624050, 5, 5, 10, 15, 9, 8, 1, 9, 10, 3, 13, 0, 13, 13, 10, 7, 1, 8, 9, 1, 10, 11, 5
1612060, 6, 6, 12, 2, 14, 0, 14, 14, 12, 10, 6
1624070, 7, 7, 14, 5, 3, 8, 11, 3, 14, 1, 15, 0, 15, 15, 14, 13, 11, 8, 3, 11, 14, 9, 7
163080, 8, 8
1660120, 12, 12, 8, 4, 12
1624131, 3, 4, 7, 11, 2, 13, 15, 12, 11, 7, 2, 9, 11, 4, 15, 3, 2, 5, 7, 12, 3, 15, 2
1624141, 4, 5, 9, 14, 7, 5, 12, 1, 13, 14, 11, 9, 4, 13, 1, 14, 15, 13, 12, 9, 5, 14, 3
1624151, 5, 6, 11, 1, 12, 13, 9, 6, 15, 5, 4, 9, 13, 6, 3, 9, 12, 5, 1, 6, 7, 13, 4
16241111, 11, 12, 7, 3, 10, 13, 7, 4, 11, 15, 10, 9, 3, 12, 15, 11, 10, 5, 15, 4, 3, 7, 10
1612262, 6, 8, 14, 6, 4, 10, 14, 8, 6, 14, 4
1612282, 8, 10, 2, 12, 14, 10, 8, 2, 10, 12, 6

The yellow-shaded cells indicate the start of a new modulus; the green-shaded cells indicate the row containing the fundamental Pisano period for that modulus (sequence A001175.)

See also sequence A161553, which lists the fundamental sequences for the green-shaded rows.

Below is a more compact version of the above table, showing the periods but not the sequences themselves.

Table 2

MΣ#Periods
1111
2421, 3
3921, 8
41641, 6, 3, 6
52531, 20, 4
63641, 24, 8, 3
74941, 16, 16, 16
86481, 12, 6, 12, 3, 6, 12, 12
98151, 24, 24, 8, 24
1010061, 60, 20, 3, 12, 4
11121141, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 5, 10, 5
12144101, 24, 24, 6, 8, 3, 24, 6, 24, 24
1316971, 28, 28, 28, 28, 28, 28
1419681, 48, 16, 48, 16, 48, 16, 3
15225121, 40, 40, 20, 40, 8, 40, 8, 8, 8, 8, 4
16256161, 24, 12, 24, 6, 24, 12, 24, 3, 6, 24, 24, 24, 24, 12, 12

 

Validate this page