Tables
The first Pisano periods (sequence A001175 in OEIS) and their cycles (with spaces before the zeros for readability) 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, 1) |
| 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 − 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,
with equality if and only if n = 2 · 5k, for k ≥ 1, the first examples being π(10) = 60 and π(50) = 300.
Read more about this topic: Pisano Period
Famous quotes containing the word tables:
“The evening falters. Couples in their coats
Are leaving gaps already, and the rest
Move tables closer.”
—Philip Larkin (1922–1986)
“O these encounterers, so glib of tongue,
That give a coasting welcome ere it comes,
And wide unclasp the tables of their thoughts
To every ticklish reader! Set them down
For sluttish spoils of opportunity
And daughters of the game.”
—William Shakespeare (1564–1616)
“Eddie Felson: Church of the Good Hustler.
Charlie: Looks more like a morgue to me. Those tables are the slabs they lay the stiffs on.
Eddie Felson: I’ll be alive when I get out, Charlie.”
—Sydney Carroll, U.S. screenwriter, and Robert Rossen. Eddie Felson (Paul Newman)