Pisano period

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Plot of the first 10,000 Pisano periods.

In number theory, the nth Pisano period, written π(n), is the period with which the sequence of Fibonacci numbers taken modulo n repeats. Pisano periods are named after Leonardo Pisano, better known as Fibonacci. The existence of periodic functions in Fibonacci numbers was noted by Joseph Louis Lagrange in 1774.[1][2]

Definition[edit]

The Fibonacci numbers are the numbers in the integer sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, ... (sequence A000045 in OEIS)

defined by the recurrence relation

F_0 = 0
F_1 = 1
F_i = F_{i-1} + F_{i-2}.

For any integer n, the sequence Fi (mod n) of Fibonacci numbers taken modulo n is periodic. The Pisano period, denoted π(n), is the length of the period of this sequence. For example, the sequence of Fibonacci numbers modulo 3 begins:

0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, ... (sequence A082115 in OEIS)

This sequence has period 8, so π(3) = 8.

Properties[edit]

With the exception of π(2) = 3, the Pisano period π(n) is always even. A simple proof of this can be given by observing that π(n) is equal to the order of the Fibonacci matrix


\mathbf F = \begin{bmatrix} 1 & 1\\0 & 1 \end{bmatrix}

in the general linear group GL2(ℤn) of invertible 2 by 2 matrices in the finite ring ℤn of integers modulo n. Since F has determinant -1, it follows that (-1)π(n) = 1 in ℤn, so π(n) is even.[3]

If m and n are coprime, then π(mn) is the least common multiple of π(m) and π(n), by the Chinese remainder theorem. For example, π(3) = 8 and π(4) = 6 imply π(12) = 24. Thus the study of Pisano periods may be reduced to that of Pisano periods of prime powers q = pk, for k ≥ 1.

If p is prime, π(pk) divides pk–1 π(p). It is conjectured that 
\pi(p^k) = p^{k-1}\pi(p)
for every prime p and integer k > 1. Any prime p providing a counterexample would necessarily be a Wall-Sun-Sun prime, and such primes are also conjectured not to exist.

So the study of Pisano periods may be further reduced to that of Pisano periods of primes. In this regard, two primes are anomalous. The prime 2 has an odd Pisano period, and the prime 5 has period that is relatively much larger than the Pisano period of any other prime. The periods of powers of these primes are as follows:

  • If n = 2k, then π(n) = 3·2k–1 = 3n/2.
  • if n = 5k, then π(n) = 4·5k = 4n.

From these it follows that if n = 2·5k then π(n) = 6n.

The remaining primes all lie in the conjugacy classes p \equiv \pm 1 \pmod {10} or p \equiv \pm 2 \pmod {5}. If p is a prime different from 2 and 5, then the modulo p analogue of Binet's formula implies that π(p) is the multiplicative order of the roots of x2x – 1 modulo p. If p \equiv \pm 1 \pmod {10}, these roots belong to \mathbb{F}_{p} = \mathbb{Z}/p\mathbb{Z} (by quadratic reciprocity) Thus their order, π(p) is a divisor of p – 1. For example π(11) = 11 – 1 = 10 and π(29) = (29 – 1)/2 = 14.

If p \equiv \pm 2 \pmod {5}, the roots modulo p of x2x – 1 do not belong to \mathbb{F}_{p} (by quadratic reciprocity again), and belong to the finite field


\mathbb{F}_{p}[x]/(x^2 - x - 1).

As the Frobenius automorphism x \mapsto x^p exchanges these roots, it follows that, denoting them by r and s, we have rp = s, and thus rp+1 = –1. That is r2(p+1) = 1, and the Pisano period, which is the order of r, is the quotient of 2(p+1) by an odd divisor. This quotient is always a multiple of 4. The first examples of such a p, for which π(p) is smaller than 2(p+1), are π(47) = 2(47 + 1)/3 = 32, π(107) = 2(107 + 1)/3 = 72 and π(113) = 2(113 + 1)/3 = 76.

It follows from above results, that if n = pk is an odd prime power such that π(n) > n, then π(n)/4 is an integer that is not greater than n. The multiplicative property of Pisano periods imply thus that

π(n) ≤ 6n,

with equality if and only if n = 2 · 5r, for r ≥ 1.[4] The first examples are π(10) = 60 and π(50) = 300. If n is not of the form 2 · 5r, then π(n) ≤ 4n.

Tables[edit]

The first twelve Pisano periods (sequence A001175 in OEIS) and their cycles (with spaces before the zeros for readability) are:[5] (using X and E for ten and eleven, respectively)

n π(n) number of zeros in the cycle (OEISA001176) cycle (OEISA161553) OEIS sequence for the cycle
1 1 1 0 A000004
2 3 1 011 A011655
3 8 2 0112 0221 A082115
4 6 1 011231 A079343
5 20 4 01123 03314 04432 02241 A082116
6 24 2 011235213415 055431453251 A082117
7 16 2 01123516 06654261 A105870
8 12 2 011235 055271 A079344
9 24 2 011235843718 088764156281 A007887
10 60 4 011235831459437 077415617853819 099875279651673 033695493257291 A003893
11 10 1 01123582X1 A105955
12 24 2 011235819X75 055X314592E1 A089911

The first 144 Pisano periods are shown in the following table:

π(n) +1 +2 +3 +4 +5 +6 +7 +8 +9 +10 +11 +12
0+ 1 3 8 6 20 24 16 12 24 60 10 24
12+ 28 48 40 24 36 24 18 60 16 30 48 24
24+ 100 84 72 48 14 120 30 48 40 36 80 24
36+ 76 18 56 60 40 48 88 30 120 48 32 24
48+ 112 300 72 84 108 72 20 48 72 42 58 120
60+ 60 30 48 96 140 120 136 36 48 240 70 24
72+ 148 228 200 18 80 168 78 120 216 120 168 48
84+ 180 264 56 60 44 120 112 48 120 96 180 48
96+ 196 336 120 300 50 72 208 84 80 108 72 72
108+ 108 60 152 48 76 72 240 42 168 174 144 120
120+ 110 60 40 30 500 48 256 192 88 420 130 120
132+ 144 408 360 36 276 48 46 240 32 210 140 24

Pisano periods of Fibonacci numbers[edit]

If n = F (2k) (k ≥ 2), then π(n) = 4k; If n = F (2k + 1) (k ≥ 2), then π(n) = 8k + 4. That is, if the modulo base is a Fibonacci number (≥3) with an even index, the period is twice the index and the cycle has 2 zeros. If the base is a Fibonacci number (≥5) with an odd index, the period is 4 times the index and the cycle has 4 zeros.

k F (k) π(F (k)) first half of cycle (for even k ≥ 4) or first quarter of cycle (for odd k ≥ 4) or all cycle (for k ≤ 3)
(with selected second halves or second quarters)
1 1 1 0
2 1 1 0
3 2 3 0, 1, 1
4 3 8 0, 1, 1, 2, (0, 2, 2, 1)
5 5 20 0, 1, 1, 2, 3, (0, 3, 3, 1, 4)
6 8 12 0, 1, 1, 2, 3, 5, (0, 5, 5, 2, 7, 1)
7 13 28 0, 1, 1, 2, 3, 5, 8, (0, 8, 8, 3, 11, 1, 12)
8 21 16 0, 1, 1, 2, 3, 5, 8, 13, (0, 13, 13, 5, 18, 2, 20, 1)
9 34 36 0, 1, 1, 2, 3, 5, 8, 13, 21, (0, 21, 21, 8, 29, 3, 32, 1, 33)
10 55 20 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, (0, 34, 34, 13, 47, 5, 52, 2, 54, 1)
11 89 44 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, (0, 55, 55, 21, 76, 8, 84, 3, 87, 1, 88)
12 144 24 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, (0, 89, 89, 34, 123, 13, 136, 5, 141, 2, 143, 1)
13 233 52 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
14 377 28 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233
15 610 60 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377
16 987 32 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610
17 1597 68 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987
18 2584 36 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
19 4181 76 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584
20 6765 40 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181
21 10946 84 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765
22 17711 44 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946
23 28657 92 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711
24 46368 48 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657

Pisano periods of Lucas numbers[edit]

The period is relatively small, 4k + 2, for n = F (2k) + F (2k + 2), i.e. Lucas number L (2k + 1), with k ≥ 1. 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 L (2k + 1) π(L (2k + 1)) first half of cycle (for k ≥ 1) or all cycle (for k = 0)
(with selected second halves)
0 1 1 0
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
10 24476 42 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946
11 64079 46 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657

The cycle has only one 0. Besides, 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.

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.

The product of the Pisano period of n and the number of zeros in the "mod n" cycle is the Fibonacci entry point of n. That is, smallest k such that F(k) is divisible by n. They are:

1, 3, 4, 6, 5, 12, 8, 6, 12, 15, 10, 12, 7, 24, 20, 12, 9, 12, 18, 30, 8, 30, 24, 12, 25, 21, 36, 24, 14, 60, 30, 24, 20, 9, 40, 12, 19, 18, 28, 30, 20, 24, 44, 30, 60, 24, 16, 12, 56, 75, ... (sequence A001177 in OEIS)

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.

Generalizations[edit]

The Pisano periods of Pell numbers (or 2-Fibonacci numbers) are

1, 2, 8, 4, 12, 8, 6, 8, 24, 12, 24, 8, 28, 6, 24, 16, 16, 24, 40, 12, 24, 24, 22, 8, 60, 28, 72, 12, 20, 24, 30, 32, 24, 16, 12, 24, 76, 40, 56, 24, 10, 24, 88, 24, 24, 22, 46, 16, 42, 60, ... (sequence A175181 in OEIS)

The Pisano periods of 3-Fibonacci numbers are

1, 3, 2, 6, 12, 6, 16, 12, 6, 12, 8, 6, 52, 48, 12, 24, 16, 6, 40, 12, 16, 24, 22, 12, 60, 156, 18, 48, 28, 12, 64, 48, 8, 48, 48, 6, 76, 120, 52, 12, 28, 48, 42, 24, 12, 66, 96, 24, 112, 60, ... (sequence A175182 in OEIS)

The Pisano periods of Jacobsthal numbers (or (1,2)-Fibonacci numbers) are

1, 1, 6, 2, 4, 6, 6, 2, 18, 4, 10, 6, 12, 6, 12, 2, 8, 18, 18, 4, 6, 10, 22, 6, 20, 12, 54, 6, 28, 12, 10, 2, 30, 8, 12, 18, 36, 18, 12, 4, 20, 6, 14, 10, 36, 22, 46, 6, 42, 20, ... (sequence A175286 in OEIS)

The Pisano periods of (1,3)-Fibonacci numbers are

1, 3, 1, 6, 24, 3, 24, 6, 3, 24, 120, 6, 156, 24, 24, 12, 16, 3, 90, 24, 24, 120, 22, 6, 120, 156, 9, 24, 28, 24, 240, 24, 120, 48, 24, 6, 171, 90, 156, 24, 336, 24, 42, 120, 24, 66, 736, 12, 168, 120, ... (sequence A175291 in OEIS)

The Pisano periods of Tribonacci numbers (or 3-step Fibonacci numbers) are

1, 4, 13, 8, 31, 52, 48, 16, 39, 124, 110, 104, 168, 48, 403, 32, 96, 156, 360, 248, 624, 220, 553, 208, 155, 168, 117, 48, 140, 1612, 331, 64, 1430, 96, 1488, 312, 469, 360, 2184, 496, 560, 624, 308, 440, 1209, 2212, 46, 416, 336, 620, ... (sequence A046738 in OEIS)

The Pisano periods of Tetranacci numbers (or 4-step Fibonacci numbers) are

1, 5, 26, 10, 312, 130, 342, 20, 78, 1560, 120, 130, 84, 1710, 312, 40, 4912, 390, 6858, 1560, 4446, 120, 12166, 260, 1560, 420, 234, 1710, 280, 1560, 61568, 80, 1560, 24560, 17784, 390, 1368, 34290, 1092, 1560, 240, 22230, 162800, 120, 312, 60830, 103822, 520, 2394, 1560, ... (sequence A106295 in OEIS)

See also generalizations of Fibonacci numbers.

Number theory[edit]

Pisano periods can be analyzed using algebraic number theory.

Let \pi_k(n) be the n-th Pisano period of the k-Fibonacci sequence Fk(n) ( k can be any natural number, these sequences are defined as Fk(0) = 0, Fk(1) = 1, and for any natural number n > 1, Fk(n) = kFk(n-1) + Fk(n-2)). If m and n are coprime, then \pi_k(m\cdot n) = \mathrm{lcm}(\pi_k(m),\pi_k(n)), by the Chinese remainder theorem: two numbers are congruent modulo mn if and only if they are congruent modulo m and modulo n, assuming these latter are coprime. For example, \pi_1(3)=8 and \pi_1(4)=6, so \pi_1(12=3\cdot 4) = \mathrm{lcm}(\pi_1(3),\pi_1(4))= \mathrm{lcm}(8,6)=24. Thus it suffices to compute Pisano periods for prime powers q=p^n. (Usually, \pi_k(p^n) = p^{n-1}\cdot \pi_k(p), unless p is k-Wall-Sun-Sun prime, or k-Fibonacci-Wieferich prime, that is, p2 divides Fk(p-1) or Fk(p+1), where Fk is the k-Fibonacci sequence, for example, 241 is a 3-Wall-Sun-Sun prime, since 2412 divides F3(242).)

For prime numbers p, these can be analyzed by using Binet's formula:

F_k\left(n\right) = {{\varphi_k^n-(k-\varphi_k)^n} \over {\sqrt {k^2+4}}}={{\varphi_k^{n}-(-1/\varphi_k)^{n}} \over {\sqrt {k^2+4}}},\, where \varphi_k\, is the kth metallic mean
\varphi_k = \frac{k + \sqrt{k^2+4}}{2}.

If k2+4 is a quadratic residue modulo p (and p > 2, p does not divide k2+4), then \sqrt{k^2+4}, 1/2, and k/\sqrt{k^2+4} can be expressed as integers modulo p, and thus Binet's formula can be expressed over integers modulo p, and thus the Pisano period divides the totient \phi(p)=p-1, since any power (such as \varphi_k^n) has period dividing \phi(p), as this is the order of the group of units modulo p.

For k = 1, this first occurs for p = 11, where 42 = 16 ≡ 5 (mod 11) and 2 · 6 = 12 ≡ 1 (mod 11) and 4 · 3 = 12 ≡ 1 (mod 11) so 4 = √5, 6 = 1/2 and 1/√5 = 3, yielding φ = (1 + 4) · 6 = 30 ≡ 8 (mod 11) and the congruence

F_1\left(n\right) \equiv 3\cdot \left(8^n - 4^n\right) \pmod{11}.

Another example, which shows that the period can properly divide p − 1, is π1(29) = 14.

If k2+4 is not a quadratic residue modulo p, then Binet's formula is instead defined over the quadratic extension field (Z/p)[√k^2+4], which has p2 elements and whose group of units thus has order p2 − 1, and thus the Pisano period divides p2 − 1. For example, for p = 3 one has π1(3) = 8 which equals 32 − 1 = 8; for p = 7, one has π1(7) = 16, which properly divides 72 − 1 = 48.

This analysis fails for p = 2 and p is a divisor of the squarefree part of k2+4, since in these cases are zero divisors, so one must be careful in interpreting 1/2 or √k^2+4. For p = 2, k2+4 is congruent to 1 mod 2 (for k odd), but the Pisano period is not p − 1 = 1, but rather 3 (in fact, this is also 3 for even k). For p divides the squarefree part of k2+4, the Pisano period is πk(k2+4) = p2-p = p(p − 1), which does not divide p − 1 or p2 − 1.

Fibonacci integer sequences modulo n[edit]

One can consider Fibonacci integer sequences and take them modulo n, or put differently, consider Fibonacci sequences in the ring Z/nZ. 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 that 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: (the original Fibonacci cycles are excluded) (using X and E for ten and eleven, respectively)

n multiples other cycles number of cycles
(including the original Fibonacci cycles)
1 1
2 0 2
3 0 2
4 0, 022 033213 4
5 0 1342 3
6 0, 0224 0442, 033 4
7 0 02246325 05531452, 03362134 04415643 4
8 0, 022462, 044, 066426 033617 077653, 134732574372, 145167541563 8
9 0, 0336 0663 022461786527 077538213472,
044832573145 055167426854
5
10 0, 02246 06628 08864 04482, 055, 2684 134718976392 6
11 0 02246X5492, 0336942683, 044819X874, 055X437X65,
0661784156, 0773X21347, 0885279538,
0997516729, 0XX986391X, 14593, 28X76
14
12 0, 02246X42682X 0XX8628X64X2,
033693, 0448 0884, 066, 099639
07729E873X1E 0EEX974E3257,
1347E65E437X538E761783E2,
156E5491XE98516718952794
10

Number of Fibonacci integer cycles mod n are:

1, 2, 2, 4, 3, 4, 4, 8, 5, 6, 14, 10, 7, 8, 12, 16, 9, 16, 22, 16, 29, 28, 12, 30, 13, 14, 14, 22, 63, 24, 34, 32, 39, 34, 30, 58, 19, 86, 32, 52, 43, 58, 22, 78, 39, 46, 70, 102, 25, 26, ... (sequence A015134 in OEIS)

References[edit]

  1. ^ Weisstein, Eric W., "Pisano Period", MathWorld.
  2. ^ On Arithmetical functions related to the Fibonacci numbers. Acta Arithmetica XVI (1969). Retrieved 22 September 2011.
  3. ^ A Theorem on Modular Fibonacci Periodicity. Theorem of the Day (2015). Retrieved 7 January 2016.
  4. ^ Freyd & Brown (1992)
  5. ^ Graph of Fibonacci cycles modulo 1 to 24. Each row of the image represents a different modulo base n, from 1 at the bottom to 24 at the top. The columns represent the Fibonacci numbers mod n, from 0 mod n at the left to 59 mod n on the right. In each cell, the brightness indicates the value of the residual, from dark for 0 to near-white for n-1. Blue squares on the left represent the first period; the number of blue squares is the Pisano number.

External links[edit]