Как найти период пизано

In number theory, the nth Pisano period, written as π(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 the OEIS)

defined by the recurrence relation

For any integer n, the sequence of Fibonacci numbers F_i 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 the 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

in the general linear group GL₂(ℤ_n) of invertible 2 by 2 matrices in the finite ring ℤ_n of integers modulo n. Since Q has determinant −1, the determinant of Q^π(n) is (−1)^π(n), and since this must equal 1 in ℤ_n, either n ≤ 2 or π(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 = p^k, for k ≥ 1.

If p is prime, π(p^k) divides p^k–1 π(p). It is unknown if

for every prime p and integer k > 1. Any prime p providing a counterexample would necessarily be a Wall–Sun–Sun prime, and conversely every Wall–Sun–Sun prime p gives a counterexample (set k = 2).

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 = 2^k, then π(n) = 3·2^k–1 = 3·2^k/2 = 3n/2.
• if n = 5^k, then π(n) = 20·5^k–1 = 20·5^k/5 = 4n.

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

The remaining primes all lie in the residue classes or . 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 a root of x² − x − 1 modulo p. If , these roots belong to (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 the roots modulo p of x² − x − 1 do not belong to (by quadratic reciprocity again), and belong to the finite field

As the Frobenius automorphism exchanges these roots, it follows that, denoting them by r and s, we have r^p = s, and thus r^p+1 = –1. That is r^2(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. (See the table below)

It follows from above results, that if n = p^k 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 · 5^r, for r ≥ 1.^[4]

The first examples are π(10) = 60 and π(50) = 300. If n is not of the form 2 · 5^r, then π(n) ≤ 4n.

Tables[edit]

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

n	π(n)	number of zeros in the cycle (OEIS: A001176)	cycle (OEIS: A161553)	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	01123582A1	A105955
12	24	2	011235819A75 055A314592B1	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 two zeros. If the base is a Fibonacci number (≥ 5) with an odd index, the period is four times the index and the cycle has four 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]

If n = L(2k) (k ≥ 1), then π(n) = 8k; if n = L(2k + 1) (k ≥ 1), then π(n) = 4k + 2. That is, if the modulo base is a Lucas number (≥ 3) with an even index, the period is four times the index. If the base is a Lucas number (≥ 4) with an odd index, the period is twice the index.

k	L(k)	π(L(k))	first half of cycle (for odd k ≥ 2) or first quarter of cycle (for even k ≥ 2) or all cycle (for k = 1) (with selected second halves or second quarters)
1	1	1	0
2	3	8	0, 1, (1, 2)
3	4	6	0, 1, 1, (2, 3, 1)
4	7	16	0, 1, 1, 2, (3, 5, 1, 6)
5	11	10	0, 1, 1, 2, 3, (5, 8, 2, 10, 1)
6	18	24	0, 1, 1, 2, 3, 5, (8, 13, 3, 16, 1, 17)
7	29	14	0, 1, 1, 2, 3, 5, 8, (13, 21, 5, 26, 2, 28, 1)
8	47	32	0, 1, 1, 2, 3, 5, 8, 13, (21, 34, 8, 42, 3, 45, 1, 46)
9	76	18	0, 1, 1, 2, 3, 5, 8, 13, 21, (34, 55, 13, 68, 5, 73, 2, 75, 1)
10	123	40	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, (55, 89, 21, 110, 8, 118, 3, 121, 1, 122)
11	199	22	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, (89, 144, 34, 178, 13, 191, 5, 196, 2, 198, 1)
12	322	48	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, (144, 233, 55, 288, 21, 309, 8, 317, 3, 320, 1, 321)
13	521	26	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
14	843	56	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233
15	1364	30	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377
16	2207	64	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610
17	3571	34	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987
18	5778	72	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
19	9349	38	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584
20	15127	80	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181
21	24476	42	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765
22	39603	88	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946
23	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
24	103682	96	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657

For even k, the cycle has two zeros. For odd k, the cycle has only one zero, and 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.

Number of zeros in the cycle[edit]

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 p² ≡ 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.

The ratio of the Pisano period of n and the number of zeros modulo n in the cycle gives the rank of apparition or Fibonacci entry point of n. That is, smallest index k such that n divides F(k). 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, … (sequence A001177 in the OEIS)

In Renault’s paper the number of zeros is called the «order» of F mod m, denoted , and the «rank of apparition» is called the «rank» and denoted .^[6]

According to Wall’s conjecture, . If has prime factorization then .^[6]

Generalizations[edit]

The Pisano periods of Lucas numbers are

1, 3, 8, 6, 4, 24, 16, 12, 24, 12, 10, 24, 28, 48, 8, 24, 36, 24, 18, 12, 16, 30, 48, 24, 20, 84, 72, 48, 14, 24, 30, 48, 40, 36, 16, 24, 76, 18, 56, 12, 40, 48, 88, 30, 24, 48, 32, … (sequence A106291 in the OEIS)

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, … (sequence A175181 in the 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, … (sequence A175182 in the 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, … (sequence A175286 in the 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, … (sequence A175291 in the 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, … (sequence A046738 in the 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, … (sequence A106295 in the OEIS)

See also generalizations of Fibonacci numbers.

Number theory[edit]

Pisano periods can be analyzed using algebraic number theory.

Let be the n-th Pisano period of the k-Fibonacci sequence F_k(n) (k can be any natural number, these sequences are defined as F_k(0) = 0, F_k(1) = 1, and for any natural number n > 1, F_k(n) = kF_k(n−1) + F_k(n−2)). If m and n are coprime, then , 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, and so Thus it suffices to compute Pisano periods for prime powers (Usually, , unless p is k-Wall–Sun–Sun prime, or k-Fibonacci–Wieferich prime, that is, p² divides F_k(p − 1) or F_k(p + 1), where F_k is the k-Fibonacci sequence, for example, 241 is a 3-Wall–Sun–Sun prime, since 241² divides F₃(242).)

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

where is the kth metallic mean

If k² + 4 is a quadratic residue modulo p (where p > 2 and p does not divide k² + 4), then and 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 , since any power (such as ) has period dividing as this is the order of the group of units modulo p.

For k = 1, this first occurs for p = 11, where 4² = 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

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

If k² + 4 is not a quadratic residue modulo p, then Binet’s formula is instead defined over the quadratic extension field , which has p² elements and whose group of units thus has order p² − 1, and thus the Pisano period divides p² − 1. For example, for p = 3 one has π₁(3) = 8 which equals 3² − 1 = 8; for p = 7, one has π₁(7) = 16, which properly divides 7² − 1 = 48.

This analysis fails for p = 2 and p is a divisor of the squarefree part of k² + 4, since in these cases are zero divisors, so one must be careful in interpreting 1/2 or . For p = 2, k² + 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 k² + 4, the Pisano period is π_k(k² + 4) = p² − p = p(p − 1), which does not divide p − 1 or p² − 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, 18964X3257, 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, … (sequence A015134 in the OEIS)

Notes[edit]

References[edit]

• Bloom, D. M. (1965), «Periodicity in generalized Fibonacci sequences», Amer. Math. Monthly, 72 (8): 856–861, doi:10.2307/2315029, JSTOR 2315029, MR 0222015
• Brent, Richard P. (1994), «On the periods of generalized Fibonacci sequences», Mathematics of Computation, 63 (207): 389–401, arXiv:1004.5439, Bibcode:1994MaCom..63..389B, doi:10.2307/2153583, JSTOR 2153583, MR 1216256, S2CID 1038296
• Engstrom, H. T. (1931), «On sequences defined by linear recurrence relations», Trans. Am. Math. Soc., 33 (1): 210–218, doi:10.1090/S0002-9947-1931-1501585-5, JSTOR 1989467, MR 1501585
• Falcon, S.; Plaza, A. (2009), «k-Fibonacci sequence modulo m«, Chaos, Solitons & Fractals, 41 (1): 497–504, Bibcode:2009CSF….41..497F, doi:10.1016/j.chaos.2008.02.014
• Freyd, Peter; Brown, Kevin S. (1992), «Problems and Solutions: Solutions: E3410», Amer. Math. Monthly, 99 (3): 278–279, doi:10.2307/2325076, JSTOR 2325076
• Laxton, R. R. (1969), «On groups of linear recurrences», Duke Mathematical Journal, 36 (4): 721–736, doi:10.1215/S0012-7094-69-03687-4, MR 0258781
• Wall, D. D. (1960), «Fibonacci series modulo m», Amer. Math. Monthly, 67 (6): 525–532, doi:10.2307/2309169, JSTOR 2309169
• Ward, Morgan (1931), «The characteristic number of a sequence of integers satisfying a linear recursion relation», Trans. Am. Math. Soc., 33 (1): 153–165, doi:10.1090/S0002-9947-1931-1501582-X, JSTOR 1989464
• Ward, Morgan (1933), «The arithmetical theory of linear recurring series», Trans. Am. Math. Soc., 35 (3): 600–628, doi:10.1090/S0002-9947-1933-1501705-4, JSTOR 1989851
• Zierler, Neal (1959), «Linear recurring sequences», J. SIAM, 7 (1): 31–38, doi:10.1137/0107003, JSTOR 2099002, MR 0101979

External links[edit]

• The Fibonacci sequence modulo m
• A research for Fibonacci numbers
• Fibonacci sequence starts with q, r modulo m
• Johnson, Robert C., Fibonacci resources
• Fibonacci Mystery — Numberphile on YouTube, a video with Dr. James Grime and the University of Nottingham

Период Пизано

Given two number N and M. The task is to find the N-th fibonacci number mod M.
In general let F_N be the N-th fibonacci number then the output should be F_N % M.

The Fibonacci sequence is a series of numbers in which each no. is the sum of two preceding nos. It is defined by the recurrence relation: 

F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2

These nos. are in the following sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …
Here N can be large.

Examples: 

Input: N = 438, M = 900 
Output: 44

Input: N = 1548276540, M = 235 
Output: 185  

Approach: 
However, for such values of N, a simple recursive approach to keep calculating N Fibonacci numbers with a time complexity of O(2^N) should be avoided. Even an iterative or a Dynamic Programming approach with an algorithm looping for N iterations will not be time-efficient.
This problem can be solved using the properties of Pisano Period. 
For a given value of N and M >= 2, the series generated with F_i modulo M (for i in range(N)) is periodic. 

The period always starts with 01. The Pisano Period is defined as the length of the period of this series.
To understand it further, let’s see what happens when M is small:

i	0	1	2	3	4	5	6	7	8	9	10	11
Fi	0	1	1	2	3	5	8	13	21	34	55	89
Fi mod 2	0	1	1	0	1	1	0	1	1	0	1	1
Fi mod 3	0	1	1	2	0	2	2	1	0	1	1	2

For M = 2, the period is 011 and has length 3 while for M = 3 the sequence repeats after 8 nos.

Example: 
So to compute, say F₂₀₁₉ mod 5, we’ll find the remainder of 2019 when divided by 20 (Pisano Period of 5 is 20). 2019 mod 20 is 19. Therefore, F₂₀₁₉ mod 5 = F₁₉ mod 5 = 1. This property is true in general. 
We need to find the remainder when N is divided by the Pisano Period of M. Then calculate F_(N)remainder mod M for the newly calculated N.

Below is the implementation of F_N modulo M:

Pisano Period of 235 is 160. 1548276540 mod 160 is 60. F₆₀ mod 235 = 185. Using Pisano Period, we now need to calculate Fibonacci nos. iteratively for a relatively lower N than specified in the original problem and then calculate F_N modulo M.
Time Complexity: O(M²)

Auxiliary Space: O(1)
 

Last Updated :
29 Mar, 2022

Like Article

Save Article

Период последовательности Фибоначчи по модулю целого числа График первых 10 000 периодов Пизано.

В числе теория, n-й период Пизано, записанный π (n), является периодом, с которым последовательность из чисел Фибоначчи взято по модулю n повторов. Периоды Пизано названы в честь Леонардо Пизано, более известного как Фибоначчи. Существование периодических функций в числах Фибоначчи было отмечено Джозефом Луи Лагранжем в 1774 году.

Содержание

• 1 Определение
• 2 Свойства
• 3 Таблицы
• 4 периода Пизано Фибоначчи числа
• 5 периодов Пизано чисел Лукаса
• 6 Число нулей в цикле
• 7 Обобщения
• 8 Теория чисел
• 9 Целочисленных последовательностей Фибоначчи по модулю n
• 10 Примечания
• 11 Ссылки
• 12 Внешние ссылки

Определение

Числа Фибоначчи — это числа в целочисленной последовательности :

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,… (последовательность A000045 в OEIS )

определяется отношением повторения

F 0 = 0 { displaystyle F_ {0} = 0}

F 1 = 1 { displaystyle F_ {1} = 1}

F i = F я — 1 + F я — 2. { Displaystyle F_ {i} = F_ {i-1} + F_ {i-2}.}

Для любого целого числа n последовательность чисел Фибоначчи F i взятых по модулю n является периодическим. Период Пизано, обозначаемый π (n), — длина периода этой последовательности. Например, последовательность чисел Фибоначчи по модулю 3 начинается:

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,… (последовательность A082115 в OEIS )

Эта последовательность имеет период 8, поэтому π (3) = 8.

Свойства

За исключением π (2) = 3, период Пизано π (n) всегда четный. Простое доказательство этого можно определить, заметив, что π (n) равно порядку матрицы Фибоначчи.

Q = [1 1 1 0] { displaystyle mathbf {Q} = { begin {bmatrix} 1 1 \ 1 0 end {bmatrix}}}

в общей линейной группе GL2(ℤn) обратимых 2х2 матриц в конечном кольцо ℤnиз целых чисел по модулю n. Поскольку Q имеет определитель −1, определитель Q равен (−1), и поскольку он должен быть равен 1 в ℤ n, либо n ≤ 2, либо π (n) четно.

Если m и n взаимно простые, то π (mn) является наименьшим общим кратным чисел π (m) и π ( n) по китайской теореме об остатках. Например, π (3) = 8 и π (4) = 6 означает, что π (12) = 24. Таким образом, изучение периодов Пизано может быть сведено к изучению периодов Пизано простых степеней q = p., для k ≥ 1.

Если p является простым, π (p) делит p π (p). Это предположение, что π (pk) = pk — 1 π (p) { displaystyle pi (p ^ {k}) = p ^ {k-1} pi (p) }для любого простого p и целого k>1. Любое простое число p, обеспечивающее контрпример, обязательно будет простым числом Стена-Солнце-Солнце, и предполагается, что таких простых чисел не существует.

Итак, исследование Пизано периоды могут быть далее сокращены до периодов простых чисел Пизано. В этом отношении два простых числа являются аномальными. Простое число 2 имеет нечетный период Пизано, а простое число 5 имеет период, который относительно намного больше периода Пизано любого другого простого числа. Периоды степеней этих простых чисел следующие:

• Если n = 2, то π (n) = 3 · 2 = 3 · 2/2 = 3n / 2.
• если n = 5, тогда π (n) = 20 · 5 = 20 · 5/5 = 4n.

Отсюда следует, что если n = 2 · 5, то π (n) = 6n.

Все остальные простые числа лежат в классах остатков p ≡ ± 1 (mod 10) { displaystyle p Equiv pm 1 { pmod {10}}}или п ≡ ± 3 (mod 10) { displaystyle p Equiv pm 3 { pmod {10}}}. Если p — простое число, отличное от 2 и 5, то аналог по модулю p формулы Бине означает, что π (p) является порядком умножения корней из x — x — 1 по модулю p. Если p ≡ ± 1 (mod 10) { displaystyle p Equiv pm 1 { pmod {10}}}, эти корни принадлежат F p = Z / p Z { displaystyle mathbb {F} _ {p} = mathbb {Z} / p mathbb {Z}}(по квадратичной взаимности ). Таким образом, их порядок, π (p) является делителем числа p — 1. Например, π (11) = 11-1 = 10 и π (29) = (29 — 1) / 2 = 14..

Если p ≡ ± 3 (mod 10), { displaystyle p Equiv pm 3 { pmod {10}},}корни по модулю p x — x — 1 не принадлежат F p { displaystyle mathbb {F} _ {p}}(опять же по квадратичной взаимности) и принадлежат конечному полю

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

Как автоморфизм Фробениуса x ↦ xp { displaystyle x mapsto x ^ {p}}меняет местами эти корни, из этого следует, что, обозначая их r и s, мы имеем r = s, и, следовательно, r = –1. То есть r = 1, а период Пизано, который является порядком r, является отношением 2 (p + 1) к нечетному делителю. Это частное всегда кратно 4. Первыми примерами таких ap, для которых π (p) меньше 2 (p + 1), являются π (47) = 2 (47 + 1) / 3 = 32, π (107) = 2 (107 + 1) / 3 = 72 и π (113) = 2 (113 + 1) / 3 = 76. (См. Таблицу ниже)

Из приведенных выше результатов следует, что если n = p — нечетная степень простого числа такая, что π (n)>n, тогда π (n) / 4 — целое число, не большее, чем n. Мультипликативное свойство периодов Пизано означает, таким образом, что

π (n) ≤ 6n с равенством тогда и только тогда, когда n = 2 · 5, для r ≥ 1.

Первые примеры: π (10) = 60 и π (50) = 300. Если n не имеет формы 2 · 5, тогда π (n) ≤ 4n.

Таблицы

Первые двенадцать периодов Пизано (последовательность A001175 в OEIS ) и их циклы (с пробелами перед нулями для удобочитаемости) (используя шестнадцатеричные шифры A и B для десяти и одиннадцати, соответственно):

n	π(n)	количество нулей в цикле (OEIS : A001176 )	цикл (OEIS : A161553 )	OEIS последовательность для цикла le
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	0112351421343205128248 055114843
7	16	2	01123516 06654261	A105870
8	12	2	011235 055271	A079344
9	24	2	011235843718 088764156281	A007887
10	60	4	011235831459437 077415617853819 09987527629437 077415617853819 099875276295325329 099875279502193 055A314592B1	A089911

Первые 144 периода Пизано показаны в следующей таблице:

π (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

периоды Пизано чисел Фибоначчи

Если n = F (2k) ( k ≥ 2), то π (n) = 4k; если n = F (2k + 1) (k ≥ 2), то π (n) = 8k + 4. То есть, если основанием по модулю является число Фибоначчи (≥ 3) с четным индексом, период в два раза больше index и цикл имеет два нуля. Если основанием является число Фибоначчи (≥ 5) с нечетным индексом, период в четыре раза больше индекса, а цикл имеет четыре нуля.

k	F(k)	π(F(k))	первая половина цикла (для четных k ≥ 4) или первая четверть цикла (для нечетных k ≥ 4) или весь цикл (для k ≤ 3). (с выбранными вторыми половинами или вторыми четвертями)
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, 2 33, 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

периоды Пизано чисел Лукаса

Если n = L ( 2k) (k ≥ 1), то π (n) = 8k; если n = L (2k + 1) (k ≥ 1), то π (n) = 4k + 2. То есть, если основанием по модулю является число Люка (≥ 3) с четным индексом, период равен четырехкратному индекс. Если основание — это число Люка (≥ 4) с нечетным индексом, период вдвое больше индекса.

k	L(k)	π(L(k))	первая половина цикла (для нечетных k ≥ 2) или первая четверть цикла (для четных k ≥ 2) или весь цикл (для k = 1). (с выбранными вторыми половинами или вторыми четвертями)
1	1	1	0
2	3	8	0, 1, (1, 2)
3	4	6	0, 1, 1, (2, 3, 1)
4	7	16	0, 1, 1, 2, (3, 5, 1, 6)
5	11	10	0, 1, 1, 2, 3, (5, 8, 2, 10, 1)
6	18	24	0, 1, 1, 2, 3, 5, (8, 13, 3, 16, 1, 17)
7	29	14	0, 1, 1, 2, 3, 5, 8, (13, 21, 5, 26, 2, 28, 1)
8	47	32	0, 1, 1, 2, 3, 5, 8, 13, (21, 34, 8, 42, 3, 45, 1, 46)
9	76	18	0, 1, 1, 2, 3, 5, 8, 13, 21, (34, 55, 13, 68, 5, 73, 2, 75, 1)
10	123	40	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, (55, 89, 21, 110, 8, 118, 3, 121, 1, 122)
11	199	22	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, (89, 144, 34, 178, 13, 191, 5, 196, 2, 198, 1)
12	322	48	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, (144, 233, 55, 288, 21, 309, 8, 317, 3, 320, 1, 321)
13	521	26	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
14	843	56	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233
15	1364	30	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377
16	2207	64	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610
17	3571	34	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987
18	5778	72	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
19	9349	38	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584
20	15127	80	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181
21	24476	42	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765
22	39603	88	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946
23	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
24	103682	96	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657

Для четного k цикл имеет два нуля. Для нечетного k цикл имеет только один ноль, а вторая половина цикла, которая, конечно, равна части слева от 0, состоит из попеременно чисел F (2m + 1) и n — F (2m)., при уменьшении m.

Количество нулей в цикле

Количество вхождений 0 в цикл равно 1, 2 или 4. Пусть p будет числом после первого 0 после комбинации 0, 1. Пусть расстояние между нулями равно q.

• В цикле один 0, очевидно, если p = 1. Это возможно, только если q четно или n равно 1 или 2.
• В противном случае в цикле два нуля, если p ≡ 1. Это возможно, только если q четно.
• В противном случае в цикле четыре нуля. Это так, если q нечетно, а n не равно 1 или 2.

Для обобщенных последовательностей Фибоначчи (удовлетворяющих тому же рекуррентному соотношению, но с другими начальными значениями, например числами Люка) число вхождений 0 за цикл равно 0, 1, 2 или 4.

Отношение периода Пизано n и количества нулей по модулю n в цикле дает ранг появления или точку входа Фибоначчи n. То есть наименьший индекс k такой, что n делит F (k). Это:

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,… (последовательность A001177 в OEIS )

В статье Renault количество нулей называется «порядком» F mod m, обозначенным ω (m) { displaystyle omega (m)}, а «ранг явления» называется «рангом» и обозначается α (m) { displaystyle alpha (m)}.

Согласно согласно гипотезе Уолла α (pe) = pe — 1 α (p) { displaystyle alpha (p ^ {e}) = p ^ {e-1} alpha (p)}. Если m { displaystyle m}имеет разложение на простые множители m = p 1 e 1 p 2 e 2… pnen { displaystyle m = p_ {1 } ^ {e_ {1}} p_ {2} ^ {e_ {2}} dots p_ {n} ^ {e_ {n}}}, тогда α (м) = lcm ⁡ (α (п 1 е 1), α (п 2 е 2),…, α (pnen)) { displaystyle alpha (m) = operatorname {lcm} ( alpha (p_ {1} ^ {e_ { 1}}), alpha (p_ {2} ^ {e_ {2}}), dots, alpha (p_ {n} ^ {e_ {n}}))}.

Gen

периоды Пизано из чисел Пелла (или 2-числа Фибоначчи) равны

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,… (последовательность A175181 в OEIS )

периоды Пизано 3-числа Фибоначчи:

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,… (последовательность A175182 в OEIS )

периоды Пизано из Числа Якобсталя (или (1,2) -числа Фибоначчи) равны

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,… (последовательность A175286 в OEIS )

периоды Пизано из (1, 3) -Ню Фибоначчи mbers:

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,… (последовательность A175291 в OEIS )

периоды Пизано из чисел Трибоначчи (или трехступенчатые числа Фибоначчи) равны

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,… (последовательность A046738 в OEIS )

периоды Пизано из чисел Тетраначчи (или 4-ступенчатые числа Фибоначчи) равны

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,… (seque nce A106295 в OEIS )

См. также обобщения чисел Фибоначчи.

Теория чисел

Периоды Пизано могут быть проанализированы с помощью теории алгебраических чисел.

Пусть π k (n) { displaystyle pi _ {k} (n)}будет n-м периодом Пизано последовательности k-Фибоначчи F k (n) (k может быть любым натуральным числом, эти последовательности определены как F k (0) = 0, F k (1) = 1, и для любого натурального числа n>1, F k (n) = kF k (n − 1) + F k (n − 2)). Если m и n взаимно просты, то π k (m ⋅ n) = lcm (π k (m), π k (n)), { displaystyle pi _ {k} ( m cdot n) = mathrm {lcm} ( pi _ {k} (m), pi _ {k} (n)),}по китайской теореме об остатках : два числа конгруэнтны по модулю mn тогда и только тогда, когда они конгруэнтны по модулю m и по модулю n, при условии, что последние взаимно просты. Например, π 1 (3) = 8 { displaystyle pi _ {1} (3) = 8}и π 1 (4) = 6, { displaystyle pi _ {1} (4) = 6,}, поэтому π 1 (12 = 3 ⋅ 4) = lcm (π 1 (3), π 1 (4)) = lcm (8, 6) = 24. { Displaystyle pi _ {1} (12 = 3 cdot 4) = mathrm {lcm} ( pi _ {1} (3), pi _ {1} (4)) = mathrm {lcm} (8,6) = 24.}Таким образом, достаточно вычислить периоды Пизано для простых степеней q = pn. { displaystyle q = p ^ {n}.}(Обычно π k (pn) = pn — 1 ⋅ π k (p) { displaystyle pi _ {k} (p ^ {n}) = p ^ {n-1} cdot pi _ {k} (p)}, если p не равно k- простое число Стена-Солнце-Солнце, или k-простое число Фибоначчи-Вифериха, то есть p делит F k (p — 1) или F k (p + 1), где F k — последовательность k-Фибоначчи, например, 241 — простое число 3-Стена-Солнце-Солнце, поскольку 241 делит F 3 (242).)

Для простых чисел p эти можно проанализировать с помощью формулы Бине :

F k (n) = φ kn — (k — φ k) nk 2 + 4 = φ kn — (- 1 / φ k) nk 2 + 4, { displaystyle 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 }}}, ,}где φ k { displaystyle varphi _ {k}}— kth среднее значение металла

φ k = k + к 2 + 4 2. { displaystyle varphi _ {k} = { frac {k + { sqrt {k ^ {2} +4}}} {2}}.}

Если k + 4 является квадратичным остатком, по модулю p (где p>2 и p не делит k + 4), тогда k 2 + 4, 1/2, { displaystyle { sqrt {k ^ {2} +4}}, 1 / 2,}и k / k 2 + 4 { displaystyle k / { sqrt {k ^ {2} +4}}}можно выразить как целые числа по модулю p, и, таким образом, формула Бине может быть выражена над целыми числами по модулю p, и, таким образом, период Пизано делит totient ϕ (p) = p — 1 { displaystyle phi (p) = p -1}, поскольку любая степень (например, φ kn { displaystyle varphi _ {k} ^ {n}}) имеет период деления ϕ ( p), { displaystyle phi (p),}, поскольку это порядок группы единиц по модулю p.

Для k = 1 это сначала происходит для p = 11, где 4 = 16 5 (mod 11) и 2 · 6 = 12 1 (mod 11) и 4 · 3 = 12 ≡ 1 ( mod 11), поэтому 4 = √5, 6 = 1/2 и 1 / √5 = 3, что дает φ = (1 + 4) · 6 = 30 ≡ 8 (mod 11) и сравнение

F 1 (n) ≡ 3 ⋅ (8 n — 4 n) (мод.11). { displaystyle F_ {1} left (n right) Equiv 3 cdot left (8 ^ {n} -4 ^ {n} right) { pmod {11}}.}

Другой пример, который показывает, что период может правильно делить p — 1, равен π 1 (29) = 14.

Если k + 4 не является квадратичным вычетом по модулю p, то формула Бине имеет вид вместо этого определено в поле quadratic extension (Z / p) [√k + 4], которое имеет p элементов и чья группа единиц, таким образом, имеет порядок p — 1, и, следовательно, Период Пизано делит p — 1. Например, для p = 3 π 1 (3) = 8, что равно 3 — 1 = 8; для p = 7 имеем π 1 (7) = 16, что правильно делит 7 — 1 = 48.

Этот анализ не выполняется для p = 2, а p является делителем числа свободная от квадратов часть k + 4, поскольку в этих случаях это делители нуля, поэтому нужно быть осторожным при интерпретации 1/2 или √k + 4. При p = 2 k + 4 конгруэнтно 1 mod 2 (для нечетного k), но период Пизано равен не p — 1 = 1, а скорее 3 (на самом деле, это также 3 для четного k). Поскольку p делит бесквадратную часть k + 4, период Пизано равен π k (k + 4) = p — p = p (p — 1), что не делит p — 1 или p — 1.

Целочисленные последовательности Фибоначчи по модулю n

Можно рассмотреть целочисленные последовательности Фибоначчи и взять их по модулю n, или, иначе говоря, рассмотреть последовательности Фибоначчи в кольце Z/nZ. Период является делителем числа π (n). Число вхождений 0 в цикл равно 0, 1, 2 или 4. Если n не является простым числом, циклы включают те, которые являются кратными циклам для делителей. Например, для n = 10 дополнительные циклы включают циклы для n = 2, умноженные на 5, и для n = 5, умноженные на 2.

Таблица дополнительных циклов: (исходные циклы Фибоначчи исключены) ( используя X и E для десяти и одиннадцати соответственно)

n	умножает	другие циклы	количество циклов. (включая исходные циклы Фибоначчи)
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, 1451675>0, 0336 0663	022461786527 077538213472, 044832573145 055167426854	5
10	0, 02246 06628 08864 04482, 055, 2684	134718976392	6
11	0	02246473684X13476392, 0552647327808802, 0885279538, 0997516729, 0XX986391X, 14593, 18964X3257, 28X76	14
12	0, 02246X42682X 0XX8628X64X2, 033693, 0448 0884, 066, 099639	07729E873X1E 0EEX974E3257, 1347E65E437X538E761783E2, 156E5491XE98516718952794	10

Число целочисленных циклов Фибоначчи по модулю n:

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,… (последовательность A015134 в OEIS )

Notes

Ссылки

• Bloom, DM (1965), «Периодичность в обобщенном Последовательности Фибоначчи », амер. Математика. Ежемесячно, 72 (8): 856–861, doi : 10.2307 / 2315029, JSTOR 2315029, MR 0222015
• Брент, Ричард П. (1994), «О периодах обобщенных последовательностей Фибоначчи», Математика вычислений, 63 (207): 389–401, arXiv : 1004.5439, Bibcode : 1994MaCom..63..389B, doi : 10.2307 / 2153583, JSTOR 2153583, MR 1216256
• Энгстрем, HT (1931), «О последовательностях, определяемых линейными рекуррентными отношениями», Trans. Am. Математика. Soc., 33 (1): 210–218, doi : 10.1090 / S0002-9947-1931-1501585-5, JSTOR 1989467, MR 1501585
• Falcon, S.; Плаза, А. (2009), «последовательность k-Фибоначчи по модулю m», Хаос, солитоны и фракталы, 41 (1): 497–504, Bibcode : 2009CSF…. 41..497F, doi : 10.1016 / j.chaos.2008.02.014
• Фрейд, Питер; Браун, Кевин С. (1992), «Проблемы и решения: решения: E3410», Amer. Математика. Ежемесячно, 99 (3): 278–279, doi : 10.2307 / 2325076, JSTOR 2325076
• Laxton, RR (1969), «О группах линейных повторений», Duke Mathematical Journal, 36(4): 721–736, doi : 10.1215 / S0012-7094-69- 03687-4, MR 0258781
• Уолл, Д. Д. (1960), «Ряд Фибоначчи по модулю m», Amer. Математика. Ежемесячно, 67 (6): 525–532, doi : 10.2307 / 2309169, JSTOR 2309169
• Ward, Морган (1931), «Характеристическое число последовательности целых чисел, удовлетворяющих линейному рекурсивному соотношению», Trans. Am. Математика. Soc., 33 (1): 153–165, doi : 10.1090 / S0002-9947-1931-1501582-X, JSTOR 1989464
• Уорд, Морган (1933), «Арифметическая теория линейных повторяющихся рядов», Trans. Am. Математика. Soc., 35 (3): 600–628, doi : 10.1090 / S0002-9947-1933-1501705-4, JSTOR 1989851
• Цирлер, Нил (1959), «Линейные повторяющиеся последовательности», J. SIAM, 7 (1): 31–38, doi : 10.1137 / 0107003, JSTOR 2099002, MR 0101979

Внешние ссылки

Поиск периода Пизано

Даны целые числа [latex]1 leq n leq 10^{18}[/latex] и [latex]2 leq m leq 10^5[/latex], необходимо найти остаток от деления n-го числа Фибоначчи на m.

Решение

Последовательность остатков при делении чисел Фибоначчи на натуральное число периодична. Период Пизаноopen in new window — это длина периода этой последовательности.

Для нахождения остатка от деления n-го числа Фибоначчи на натуральное число m достаточно найти все числа периода Пизано для данного m, затем найти остаток от деления n на длину периода, и взять число из периода Пизано под этим номером.

Саму последовательность Фибоначчи можно не вычислять, для нахождения периода использовать только остатки.

Первые числа в периоде Пизано — 0 и 1. Длина периода не больше m * 6 (доказательство этого не нашёл).

n, m = [int(x) for x in input().split()]

def find_pisano(n, m): pisano = [] pisano.append(0)

# при делении на 1 остаток будет всегда 0
if m == 1:
    return pisano

pisano.append(1)

# при m > 0 остатки от деления первого и второго числа Фибоначчи
# всегда 0 и 1
if n <= 1:
    return pisano

n0 = 0
n1 = 1
for __ in range(m * 6):
    # для ускорения не вычисляем числа Фибоначчи полностью
    # берём только остатки по модулю m
    n0, n1 = n1, (n0 + n1) % m

    pisano.append(n1 % m)

    # Проверяем не начался ли новый период 
    # период всегда начинается с 0 и 1
    if pisano[len(pisano) - 1] == 1 \
        and pisano[len(pisano) - 2] == 0:
        break

return pisano[:-2]

pisano = find_pisano(n, m) print(pisano) print(pisano[n % len(pisano)])