Последовательность фибоначчи от 1 до 500 с: Таблица чисел Фибоначчи (первые 200 чисел)

Я собрал здесь некоторые результаты о свойствах последовательности Фибоначчи при модуле. Я создал эту страницу в попытке собрать и систематизировать множество результатов из разных источников, используя непротиворечивые обозначения. Интересующие нас объекты — это стандартная последовательность Фибоначчи $ F = 0, 1, 1, 2, 3, 5, 8, \ ldots $, а также более общая последовательность $ G = a, b, a + b, a + 2b, 2a + 3b, \ ldots $, где $ a $ и $ b $ — целые числа.Спасибо за посещение, и я надеюсь, что вы найдете эту страницу полезной.

Бесстыдная самореклама

• Renault, Последовательность Фибоначчи под различными модулями, магистерская работа, Университет Уэйк Форест, 1996.
• Ide, Renault, Силовые последовательности Фибоначчи, Fibonacci Quarterly 2012.
• Renault, Период, ранг и порядок $ (a, b) $ — последовательности Фибоначчи Mod $ m $, Математический журнал 2013
• Flanagan, Renault, Updike, Симметрии точек Фибоначчи, Mod $ m $, Fibonacci Quarterly 2014 (и играйте с этим апплетом.)

Инструменты, Столы

1. Период — Основные факты

1. Определение . Под $ F \ pmod {m} $ мы понимаем последовательность наименьших неотрицательных вычетов членов последовательности Фибоначчи, взятых по модулю $ m $. Это би-бесконечная последовательность, в которой при любых двух последовательных терминах мы можем найти термины, предшествующие и следующие за этими терминами. Пример: $ F \ pmod {3} = \ ldots, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, \ ldots $.2 $ возможных пар вычетов, и, следовательно, некоторая пара последовательных членов $ F \ pmod {m} $ должна повторяться.
2. Любая пара последовательных членов F (mod m) определяет всю последовательность как вперед, так и назад.
3. Определение . Пусть $ \ pi (m) $ обозначает период $ F \ pmod {m} $. То есть $ \ pi (m) $ — это наименьшее положительное целое число $ k $, такое что $ F_k \ эквивалента 0 $ и $ F_ {k + 1} \ эквивалента 1 \ pmod {m} $ (мы всегда берем $ F_0 = 0 $ и $ F_1 = 1 $.)
   • Для $ m = 2, 3, 4, \ ldots $ значения $ \ pi (m) $ равны $ 3, 8, 6, 20, 24, 16, 12, 24, 60, \ ldots $. [A001175]. Ниже значения $ \ pi (m) $ приведены для $ 2 \ le m \ le 3000 $.
     
     
4. Для любого целого числа $ m $ бесконечно много чисел Фибоначчи делится на $ m $.
   • Это следует из того факта, что $ 0 $ находится в последовательности Фибоначчи ($ F_0 = 0 $) и что $ F \ pmod {m} $ является периодическим.t (F_ {s} F_ {t + 1} — F_ {s + 1} F_ {t}) $, мы видим, что если $ F_s $ и $ F_t $ конгруэнтны с 0 mod $ m $, то и $ F_ {s + t} $ и $ F_ {st} $.
5. Для $ m> 2 $, $ \ pi (m) $ четно.
   • Доказательство. Пусть $ \ pi = \ pi (m) $. Взяв сравнения по модулю $ m $, мы видим, что $ F _ {\ pi} \ эквивалента 0 $, $ F _ {\ pi + 1} \ эквивалента 1 $ и $ F _ {\ pi — 1} \ эквивалента 1 $. Также $ F _ {- \ pi + 1} \ эквивалент 1 $. Предположим, что $ \ pi $ нечетно. Применяя тождество $ F _ {- t} = (-1) ^ {t + 1} F_t $, мы находим $ F _ {\ pi — 1} = -F _ {- \ pi + 1} $.n $ для $ n = 1, 2, 3, \ ldots $. [Приписывается К. С. Брауну, доказательство]
     • На графике выше вы видите, что $ \ pi (250) = 1500 $ и $ \ pi (1250) = 7500 $ выделяются.
   • Нижняя граница: учитывая модуль $ m $, пусть $ t> 0 $ выбирается так, что $ L_t \ leq m $, где $ L_t $ — это $ t $ ^-й -й номер Лукаса $ L_0 = 2, L_1 = 1 $. Тогда $ \ pi (m) \ geq 2t $. Эта нижняя граница является острой. [Catlin74]
     • Предположим, мы хотим найти оценку снизу для $ \ pi (987) $.e $ для некоторого неотрицательного целого числа $ e $.

2. Вычисление $ \ pi (m) $ на основе простой факторизации $ m $

1. $ \ pi ([m, n]) = [\ pi (m), \ pi (n)] $. Здесь $ [x, y] $ обозначает наименьшее общее кратное $ x $ и $ y $.
2. Следствие 1 . Если $ n \ mid m $, то $ \ pi (n) \ mid \ pi (m) $.{e-1} \ pi (p) $.
3. Чтобы вычислить $ \ pi (p) $, лучшее, что мы можем сделать, это предоставить некоторые условия делимости.
   • $ \ pi (2) = 3 $
   • $ \ pi (5) = 20 $
   • Если $ p \ equ \ pm 1 \ pmod {10} $, то $ \ pi (p) \ mid p — 1 $.
   • Если $ p \ equ \ pm 3 \ pmod {10} $, то $ \ pi (p) \ mid 2p + 2 $ и $ \ pi (p) \ not \ mid p + 1 $.
   Кстати, из двух соотношений делимости в последнем пункте выше следует, что $ 4 \ mid \ pi (p) $.k \ эквив I \ pmod {m} $ именно тогда, когда $ \ pi (m) \ mid k $. В следующем алгоритме $ U = \ small \ matrixb {0 & 1 \\ 1 & 1} $ и $ I = \ small \ matrixb {1 & 0 \\ 0 & 1} $. def $ \ pi (m) $: если $ m == 1 $: вернуть $ 1 $ если $ m $ простое число: $ p = m $ если $ p == 2 $: вернуть $ 3 $ если $ p == 5 $: вернуть $ 20 $ если $ p \ equ \ pm 1 $ (мод 10): $ D $ = множество четных делителей $ p — 1 $ еще: $ D $ = множество делителей $ 2p + 2 $, не являющихся делителями $ p + 1 $ найти наименьшее значение $ d $ в $ D $, такое что $ U ^ d \ эквивалент I \ pmod {p} $ (конечно, используйте модульное возведение в степень) если $ U ^ d \ эквив. I \ pmod {p ^ 2} $: напечатайте $ p $, выйдите из программы, опубликуйте статью — вы нашли простое число Wall-Sun-Sun! вернуть $ d $ еще: множитель $ m $ как $ m = p_1 ^ {e_1} p_2 ^ {e_2} \ cdots p_n ^ {e_n} $ вернуть LCM $ [p_1 ^ {e_1-1} \ pi (p_1), p_2 ^ {e_2-1} \ pi (p_2), \ ldots, p_n ^ {e_n-1} \ pi (p_n)] $

3. Ранг, множитель и порядок $ F \ pmod {m} $ — Введение

1. Вычислите период, ранг, множитель и порядок $ F \ pmod {m} $ для $ m \ lt 100 000 000 $.
2. Определение. «Ранг» в $ F \ pmod {m} $, обозначаемый как $ \ alpha (m) $, является наименее положительным целым числом $ k $ таким, что $ F_k \ эквивалента 0 \ pmod {m} $. Например, $ \ alpha (7) = 8 $, поскольку $ F_8 = 21 $, а не меньшее число Фибоначчи делится на $ 7 $. $ \ alpha (m) $ также называют «ограниченным периодом» или «рангом появления» в $ F \ pmod {m} $.
3. Определение. «Множитель» в $ F \ pmod {m} $, обозначаемый $ \ mu (m) $, является первым вычетом после первого нуля в $ F \ pmod {m} $.{\ omega} I \ эквив I \ pmod {m} $, что противоречит минимальности $ \ pi $.
   Таким образом, $ \ omega = k $ и мы имеем $ \ alpha \ omega = \ pi $.
4. Теперь у нас есть эквивалентная интерпретация $ \ omega (m) $: это число нулей в одном периоде $ F \ pmod {m} $.
5. $ \ omega (m) = 1 $, $ 2 $ или $ 4 $.
   • Какой это замечательный и любопытный факт! Один период последовательности Фибоначчи mod $ m $ всегда будет содержать 1, 2 или 4 нуля, независимо от модуля.4 \ pmod {m} $, поэтому порядок $ \ mu $, а именно $ \ omega $, должен делить 4. Готово!

4. Фактов о ранге $ F \ pmod {m} $

1. $ \ alpha ([m, n]) = [\ alpha (m), \ alpha (n)] $. Этот и другие результаты о $ \ alpha $ можно найти в [Robinson 63].
2. Следствие 1 .{Е-3} $.
3. Фактов о $ \ alpha (p) $:
   • $ \ alpha (2) = 3 $
   • $ \ alpha (5) = 5 $
   • Если $ p \ эквивалента 1 $ или $ 9 \ pmod {10} $, то $ \ alpha (p) \ mid p — 1 $.
   • Если $ p \ эквивалент 3 $ или $ 7 \ pmod {10} $, то $ \ alpha (p) \ mid p + 1 $.

5. Факты о порядке $ F \ pmod {m} $

1. Для $ p $ любого нечетного простого числа и $ e $ любого положительного целого числа $ \ omega (p ^ e) = \ omega (p) $.е) = \ omega (p) $.
2. [Винсон 63, чт. 3] Соотношение между $ \ omega (m) $ и $ \ alpha (m) $.
   • $ \ omega (m) = 4 $, если $ m> 2 $ и $ 2 \ not \ mid \ alpha (m) $.
   • $ \ omega (m) = 1 $ тогда и только тогда, когда $ 8 \ not \ mid m $ и $ 2 \ mid \ alpha (p) $, но $ 4 \ not \ mid \ alpha (p) $ для каждого нечетного простого числа $ p $, которое делит $ м $.
   • $ \ omega (m) = 2 $ для всех остальных $ m $
3. [Винсон 63, чт.д) \ neq 2 $, если $ p \ эквивалента 21 $ или $ 29 \ pmod {40} $.
Следующие примеры показывают, что эта теорема является «полной».
• $ p \ эквивалента 1 \ pmod {40} $: $ \ omega (521) = 1 $, $ \ omega (41) = 2 $, $ \ omega (761) = 4 $.
• $ p \ эквивалент 9 \ pmod {40} $: $ \ omega (809) = 1 $, $ \ omega (409) = 2 $, $ \ omega (89) = 4 $.
• $ p \ эквивалент 21 \ pmod {40} $: $ \ omega (101) = 1 $, $ \ omega (61) = 4 $.
• $ p \ эквивалент 29 \ pmod {40} $: $ \ omega (29) = 1 $, $ \ omega (109) = 4 $.
4. На основании приведенных выше результатов Винсона мы можем найти связи между $ \ pi (m), \ omega (m) $ и $ \ alpha (m) $ для любого модуля $ m> 2 $. [Рено 96, чт. 3,35, кор. 3,38]
   • $ \ pi (m) \ эквивалент 2 \ pmod {4} \ Leftrightarrow \ omega (m) = 1 $. В этом случае $ \ alpha (m) \ эквивалент 2 \ pmod {4} $.
   • $ \ pi (m) \ эквивалент 4 \ pmod {8} \ Rightarrow \ omega (m) = 2 $ или $ 4 $. В этом случае $ \ alpha (m) \ эквивалент 2 \ pmod {4} $ или $ \ alpha (m) $ является нечетным, соответственно.
   • $ \ pi (m) \ эквивалент 0 \ pmod {8} \ Rightarrow \ omega (m) = 2 $. В этом случае $ \ alpha (m) \ эквивалент 0 \ pmod {4} $.
5. Ранее мы видели, что $ \ pi ([m, n]) = [\ pi (m), \ pi (n)] $ и $ \ alpha ([m, n]) = [\ alpha (m), \ альфа (п)] $. То же уравнение не выполняется для $ \ omega $, но на следующей диаграмме показано значение $ \ omega ([m, n]) $, заданные значения для $ \ omega (m) $ и $ \ omega (n) $. [Рено 96, чт.3,41].

   		$ \ omega (n) $
   		1	2	4
   $ \ омега (м) $	1	1	2	4, если $ m = 2 2, иначе
   	2	2	2	2
   	4	4, если $ n = $ 2 2, в противном случае	2	4

6. Взаимосвязь между $ F = 0, 1, 1, 2, 3, \ ldots $ и $ G = a, b, a + b, a + 2b, 2a + 3b, \ ldots $ Modulo $ m $

1. Теперь рассмотрим последовательности $ G $, где $ G_n = G_ {n-1} + G_ {n-2} $ и $ G_0 = a $, $ G_0 = b $ для некоторых целых чисел $ a $ и $ b $.Мы рассмотрим свойства этих последовательностей по модулю $ m $. Мы всегда будем предполагать, что $ (a, b, m) = 1 $, ведь если бы у них всех был общий фактор, мы могли бы вместо этого рассмотреть $ \ frac {a} {d} $ и $ \ frac {b} { d} $ по модулю $ \ frac {m} {d} $. Как и в случае с $ F $, последовательность $ G $ является периодической, если взять ее по модулю $ m $; Обозначим период $ G $ через $ \ pi_G (m) $. Для ясности мы можем обозначить $ \ pi (m) $ как $ \ pi_F (m) $.
2. Матрицы. Пусть $ V = \ begin {bmatrix} b-a & a \\ a & b \ end {bmatrix} = \ begin {bmatrix} G _ {- 1} & G_0 \\ G_0 & G_1 \ end {bmatrix} $.е) $.

• Пол Кэтлин, Нижняя граница периода Фибоначчи Модуло М, Фибоначчи, ежеквартально, 1974
• Амос Эрлих, О периодах последовательности Фибоначчи по модулю М., Фибоначчи, ежеквартально, 1989.
• С. Гупта, П. Рокстрох, Ф. Э. Су, Поля расщепления и периоды последовательностей Фибоначчи по модулю простых чисел, Математический журнал, 2012.
• М. С. Рено. Последовательность Фибоначчи под различными модулями. Магистерская работа, Университет Уэйк Форест, 1996.
• Д. У. Робинсон, Матрица Фибоначчи, по модулю $ m $, Квартал Фибоначчи, 1963.
• Джон Винсон, Связь периода по модулю $ m $ с рангом появления $ m $ в последовательности Фибоначчи, Fibonacci Quarterly, 1963.
• Д. Д. Уолл, ряд Фибоначчи по модулю, Американский математический месяц, 1960.