Pisano period
From Wikipedia, the free encyclopedia
In mathematics, the nth Pisano period, written π(n), is the period with which the sequence of Fibonacci numbers, modulo n repeats. For example, the Fibonacci numbers mod 3 are 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, etc., with the first eight numbers repeating, so π(3) = 8.
The first Pisano periods (sequence A001175 in OEIS) and their cycles (with spaces before the zeros for readibility) are:
| n | π(n) | nr. of 0s | cycle |
|---|---|---|---|
| 1 | 1 | 1 | 0 |
| 2 | 3 | 1 | 011 |
| 3 | 8 | 2 | 0112 0221 |
| 4 | 6 | 1 | 011231 |
| 5 | 20 | 4 | 01123 03314 04432 02241 |
| 6 | 24 | 2 | 011235213415 055431453251 |
| 7 | 16 | 2 | 01123516 06654261 |
| 8 | 12 | 2 | 011235 055271 |
| 9 | 24 | 2 | 011235843718 088764156281 |
| 10 | 60 | 4 | 011235831459437 077415617853819 099875279651673 033695493257291 |
Onward the Pisano periods are 10, 24, 28, 48, 40, 24, 36, 24, 18, 60, 16, 30, 48, 24, 100 ...
For n > 2 the period is even, because alternatingly F(n)2 is one more and one less than F(n − 1)F(n + 1) (Cassini's identity).
The period is relatively small, 4k + 2, for n = F (2k) + F (2k + 2), i.e. Lucas number L (2k + 1), with k a positive integer. This is because F(−2k − 1) = F (2k + 1) and F(−2k) = −F (2k), and the latter is congruent to F(2k + 2) modulo n, showing that the period is a divisor of 4k + 2; the period cannot be 2k + 1 or less because the first 2k + 1 Fibonacci numbers from 0 are less than n.
| k | n | π(n) | first half of cycle (with selected second halfs) |
|---|---|---|---|
| 1 | 4 | 6 | 0, 1, 1, 2 (, 3, 3) |
| 2 | 11 | 10 | 0, 1, 1, 2, 3, 5 (, 8, 2, 10, 1) |
| 3 | 29 | 14 | 0, 1, 1, 2, 3, 5, 8, 13 (, 21, 5, 26, 2, 28, 1) |
| 4 | 76 | 18 | 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 (, 55, 13, 68, 5, 73, 2, 75, 1) |
| 5 | 199 | 22 | 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 (, 144, 34, 178, 13, 191, 5, 196, 2, 198, 1) |
| 6 | 521 | 26 | 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 |
| 7 | 1364 | 30 | 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610 |
| 8 | 3571 | 34 | 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 |
| 9 | 9349 | 38 | 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181 |
The second half of the cycle, which is of course equal to the part on the left of 0, consists of alternatingly numbers F(2m + 1) and n &minuns; F(2m), with m decreasing.
Furthermore, the period is 4k for n = F(2k), and 8k + 4 for n = F(2k + 1).
The number of occurrences of 0 per cycle is 1, 2, or 4. Let p be the number after the first 0 after the combination 0, 1. Let the distance between the 0s be q.
- There is one 0 in a cycle, obviously, if p = 1. This is only possible if q is even or n is 1 or 2.
- Otherwise there are two 0s in a cycle if p2 ≡ 1. This is only possible if q is even.
- Otherwise there are four 0s in a cycle. This is the case if q is odd and n is not 1 or 2.
For generalized Fibonacci sequences (satisfying the same recurrence relation, but with other initial values, e.g. the Lucas numbers) the number of occurrences of 0 per cycle is 0, 1, 2, or 4. Also, it can be proven that
- π(n) ≤ 6n,
and that the equality applies infinitely often (whenever n/2 equals a power of 5).
Contents |
[edit] Sums
Using
F(0) + F(1) + F(2) + … + F(k) = F(k + 2) − 1
it follows that the sum of π(n) consecutive Fibonacci numbers is a multiple of n.
Moreover, for the values in the table the sum of π(n) consecutive Fibonacci numbers is n times the (π(n)/2 + 1)th element:
[edit] Powers of 10
The Pisano periods when n is a power of 10 are 60, 300, 1500, 15000, 150000, ... (sequence A096363 in OEIS). Mathematician Dov Jarden proved that for n greater than 2 the periodicity mod 10n is 15·10n-1.[1]
[edit] Fibonacci integer sequences modulo n
One can consider Fibonacci integer sequences and take them modulo n, or put differently, consider Fibonacci sequences in the domain Z/n. The period is a divisor of π(n). The number of occurrences of 0 per cycle is 0, 1, 2, or 4. If n is not a prime the cycles include those which are multiples of the cycles for the divisors. For example, for n = 10 the extra cycles include those for n = 2 multiplied by 5, and for n = 5 multiplied by 2.
Table of the extra cycles:
| n | multiples | other cycles |
|---|---|---|
| 1 | ||
| 2 | 0 | |
| 3 | 0 | |
| 4 | 0, 022 | 033213 |
| 5 | 0 | 1342 |
| 6 | 0, 0224 0442, 033 | |
| 7 | 0 | 02246325 05531452, 03362134 04415643 |
| 8 | 0, 022462, 044, 066426 | 033617 077653, 134732574372, 145167541563 |
| 9 | 0, 0336 0663 | 022461786527 077538213472, 044832573145 055167426854 |
| 10 | 0, 02246 06628 08864 04482, 055, 2684 | 134718976392 |
[edit] Term
Pisano periods are named after Leonardo Pisano, better known as Fibonacci.
[edit] References
- ^ Weisstein, Eric W.. Pisano Period. MathWorld. Wolfram Web Resources. Retrieved on 2008-03-03.
