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

редактировать

Период последовательности Фибоначчи по модулю целого числа

График первых 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_ {0} = 0

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

F_ {1} = 1

F i = F я - 1 + F я - 2. {\ Displaystyle F_ {i} = F_ {i-1} + F_ {i-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}}}

{\ 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) }$ ${\ 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}}}$ ${\ displaystyle p \ Equiv \ pm 1 {\ pmod {10}}}$ или $п ≡ ± 3 (mod 10) {\ displaystyle p \ Equiv \ pm 3 {\ pmod {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}}}$ ${\ displaystyle p \ Equiv \ pm 1 {\ pmod {10}}}$ , эти корни принадлежат $F p = Z / p Z {\ displaystyle \ mathbb {F} _ {p} = \ mathbb {Z} / p \ mathbb {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}},}$ ${\ displaystyle p \ Equiv \ pm 3 {\ pmod {10}},}$ корни по модулю p x - x - 1 не принадлежат $F p {\ displaystyle \ mathbb {F} _ {p}}$ $\ mathbb {F} _ {p}$ (опять же по квадратичной взаимности) и принадлежат конечному полю

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

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

Как автоморфизм Фробениуса $x ↦ xp {\ displaystyle x \ mapsto x ^ {p}}$ $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)}$ ${\ displaystyle \ omega (m)}$ , а «ранг явления» называется «рангом» и обозначается $α (m) {\ displaystyle \ alpha (m)}$ ${\ displaystyle \ alpha (m)}$ .

Согласно согласно гипотезе Уолла $α (pe) = pe - 1 α (p) {\ displaystyle \ alpha (p ^ {e}) = p ^ {e-1} \ alpha (p)}$ ${\ displaystyle \ alpha (p ^ {e}) = p ^ {e-1} \ alpha (p)}$ . Если $m {\ displaystyle m}$ $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}}}$ ${\ displaystyle m = p_ {1 } ^ {е_ {1}} р_ {2} ^ {е_ {2} } \ точки 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}}))}$ ${\ displaystyle \ alpha (m) = \ operatorname {lcm} (\ alpha (p_ {1} ^ {e_ {1}}), \ alpha (p_ {2} ^ {e_ {2}})), \ точки, \ альфа (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)}$ $\ 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)),}$ $\ pi _ {k} (m \ cdot n) = {\ mathrm {lcm}} (\ pi _ {k} (m), \ pi _ {k} (n)),$ по китайской теореме об остатках : два числа конгруэнтны по модулю mn тогда и только тогда, когда они конгруэнтны по модулю m и по модулю n, при условии, что последние взаимно просты. Например, $π 1 (3) = 8 {\ displaystyle \ pi _ {1} (3) = 8}$ $\ pi _ {1} (3) = 8$ и $π 1 (4) = 6, {\ displaystyle \ pi _ {1} (4) = 6,}$ $\ 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.}$ $\ 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}.}$ $q = p ^ {n}.$ (Обычно $π k (pn) = pn - 1 ⋅ π k (p) {\ displaystyle \ pi _ {k} (p ^ {n}) = p ^ {n-1} \ cdot \ pi _ {k} (p)}$ $\ 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 }}}, \,}

F_ {k} \ left (n \ справа) = {{\ 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}}

\ varphi _ {k}

- kth среднее значение металла

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

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

F_1 \ влево (п \ вправо) \ эквив 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

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

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