Период Пизано - Pisano period

Сюжет первых 10 000 периодов Пизано.

В теория чисел, то пth Период Пизано, написано π(п), это период с которым последовательность из Числа Фибоначчи взятый по модулю п повторяется. Периоды Пизано названы в честь Леонардо Пизано, более известного как Фибоначчи. Существование периодических функций в числах Фибоначчи было отмечено Жозеф Луи Лагранж в 1774 г.^[1][2]

Определение

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

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 )

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

${\displaystyle F_{0}=0}$

${\displaystyle F_{1}=1}$

${\displaystyle F_{i}=F_{i-1}+F_{i-2}.}$

Для любого целое число п, последовательность чисел Фибоначчи F_я взятый по модулю п период Пизано, обозначаемый π(п), - длина периода этой последовательности. Например, последовательность чисел Фибоначчи по модулю 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, период Пизано π(п) всегда четное. Простое доказательство этого можно дать, заметив, что π(п) равен порядку Матрица Фибоначчи.

${\displaystyle \mathbf {Q} ={\begin{bmatrix}1&1\\1&0\end{bmatrix}}}$

в общая линейная группа GL₂(ℤ_п) из обратимый 2 на 2 матрицы в конечное кольцо ℤ_п из целые числа по модулю п. С Q имеет определитель −1, определитель Q^π(п) равно (−1)^π(п), и поскольку это должно быть равно 1 в ℤ_п, либо п ≤ 2 или π(п) даже.^[3]

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

Если п является основной, π(п^k) делит п^k–1 π(п). Неизвестно, если${\displaystyle \pi (p^{k})=p^{k-1}\pi (p)}$для каждого прайма п и целое число k > 1. Любое простое число п предоставление контрпример обязательно будет Стена – Солнце – Солнце премьер, и, наоборот, каждое простое число Стена – Солнце – Солнце п дает контрпример (набор k = 2).

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

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

Из них следует, что если п = 2 · 5^k тогда π(п) = 6п.

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

Если ${\displaystyle p\equiv \pm 3{\pmod {10}},}$ корни по модулю п из Икс² − Икс − 1 не принадлежат ${\displaystyle \mathbb {F} _{p}}$ (снова в силу квадратичной взаимности) и принадлежат конечное поле

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

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

Из приведенных выше результатов следует, что если п = п^k - нечетная степень простого числа такая, что π(п) > п, тогда π(п) / 4 - целое число, не превышающее п. Мультипликативность периодов Пизано означает, что

π(п) ≤ 6п, с равенством тогда и только тогда, когда п = 2 · 5^р, за р ≥ 1.^[4]

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

Столы

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

п	π (п)	количество нулей в цикле (OEIS: A001176)	цикл (OEIS: A161553)	OEIS последовательность для цикла
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

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

π (п)	+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

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

Если п = F(2k) (k ≥ 2), то π (п) = 4k; если п = F(2k + 1) (k ≥ 2), то π (п) = 8k + 4. То есть, если основанием по модулю является число Фибоначчи (≥ 3) с четным индексом, период в два раза больше индекса, а цикл имеет два нуля. Если основанием является число Фибоначчи (≥ 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, 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

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

Если п = L(2k) (k ≥ 1), то π (п) = 8k; если п = L(2k + 1) (k ≥ 1), то π (п) = 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(2м + 1) и п − F(2м), с м уменьшается.

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

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

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

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

Соотношение периода Пизано п и количество нулей по модулю п в цикле дает ранг явления или же Точка входа Фибоначчи из п. То есть наименьший индекс k такой, что п разделяет 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 )

В статье Рено количество нулей называется "порядком" F мод м, обозначенный ${\displaystyle \omega (m)}$, а «ранг явления» называется «рангом» и обозначается ${\displaystyle \alpha (m)}$.^[6]

Согласно гипотезе Уолла, ${\displaystyle \alpha (p^{e})=p^{e-1}\alpha (p)}$. Если ${\displaystyle m}$ имеет простые множители ${\displaystyle m=p_{1}^{e_{1}}p_{2}^{e_{2}}\dots p_{n}^{e_{n}}}$ тогда ${\displaystyle \alpha (m)=\operatorname {lcm} (\alpha (p_{1}^{e_{1}}),\alpha (p_{2}^{e_{2}}),\dots ,\alpha (p_{n}^{e_{n}}))}$.^[6]

Обобщения

В Периоды Пизано из Числа Пелла (или 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) -числа Фибоначчи равны

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

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

Теория чисел

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

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

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

${\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}}},\,}$ куда ${\displaystyle \varphi _{k}}$ это kth металлическое средство

${\displaystyle \varphi _{k}={\frac {k+{\sqrt {k^{2}+4}}}{2}}.}$

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

За k = 1, это сначала происходит при п = 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) и сравнение

${\displaystyle F_{1}\left(n\right)\equiv 3\cdot \left(8^{n}-4^{n}\right){\pmod {11}}.}$

Еще один пример, показывающий, что период можно правильно разделить п - 1, есть π₁(29) = 14.

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

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

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

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

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

п	кратные	другие циклы	количество циклов (включая исходные циклы Фибоначчи)
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

Количество целочисленных циклов Фибоначчи mod п находятся:

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 )

Примечания

1. Вайсштейн, Эрик В. "Период Пизано". MathWorld.
2. Об арифметических функциях, связанных с числами Фибоначчи. Acta Arithmetica XVI (1969). Проверено 22 сентября 2011 года.
3. Теорема о модулярной периодичности Фибоначчи. Теорема дня (2015). Проверено 7 января +2016.
4. Фрейд и Браун (1992)
5. Слоан, Н. Дж. А. (ред.). «Последовательность A001175: график». В Он-лайн энциклопедия целочисленных последовательностей. Фонд OEIS. График циклов по модулю от 1 до 24. Каждая строка изображения представляет различную основу по модулю. п, от 1 внизу до 24 вверху. Столбцы представляют мод числа Фибоначчи. п, из F(0) мод п слева к F(59) мод п справа. В каждой ячейке яркость указывает значение остатка, от темного для 0 до почти белого для п−1. Синие квадраты слева представляют первый период; количество синих квадратов - это число Пизано.
6. "Последовательность Фибоначчи по модулю M, Марк Рено". webspace.ship.edu. Получено 2018-08-22.

Рекомендации

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

внешняя ссылка

• Последовательность Фибоначчи по модулю m
• Исследование чисел Фибоначчи
• Последовательность Фибоначчи начинается с q, r по модулю m
• Джонсон, Роберт С., Ресурсы Фибоначчи
• Тайна Фибоначчи - Numberphile на YouTube, видео с доктором Джеймсом Граймом и Ноттингемский университет