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

Простые числа Фибоначчи
Количество известных терминов	15
Предполагаемый нет. терминов	бесконечный
Первые сроки	2 , 3 , 5 , 13 , 89 , 233
Самый большой известный термин	Ф 6530879
ОЭИС Индекс	А001605 ; Индексы простых чисел Фибоначчи ;

Простое число Фибоначчи — это число Фибоначчи , которое является простым , типом простого числа целой последовательности.

Первые простые числа Фибоначчи (последовательность A005478 в OEIS ):

2 , 3 , 5 , 13 , 89 , 233 , 1597, 28657, 514229, 433494437, 2971215073, ....

Фибоначчи Известные простые числа

Нерешенная задача по математике :

Существует ли бесконечное количество простых чисел Фибоначчи?

(еще нерешенные задачи по математике)

Неизвестно, существует ли бесконечно много простых чисел Фибоначчи. При индексации, начинающейся с F ₁ = F ₂ = 1 , первые 37 индексов n , для которых F _n является простым, таковы (последовательность A001605 в OEIS ):

n = 3, 4, 5, 7, 11, 13, 17, 23, 29, 43, 47, 83, 131, 137, 359, 431, 433, 449, 509, 569, 571, 2971, 4723, 5387, 9311, 9677, 14431, 25561, 30757, 35999, 37511, 50833, 81839, 104911, 130021, 148091, 201107.

(Обратите внимание, что фактические значения F _n быстро становятся очень большими, поэтому для практичности приводятся только индексы.)

В дополнение к этим проверенным простым числам Фибоначчи несколько возможных простых чисел было найдено :

n = 397379, 433781, 590041, 593689, 604711, 931517, 1049897, 1285607, 1636007, 1803059, 1968721, 2904353, 3244369, 3340367, 4740217, 6530879. ^[2]

За исключением случая n = 4, все простые числа Фибоначчи имеют простой индекс, потому что если a делит b , то $F_{a}$ также делит $F_{b}$ (но не каждый простой индекс приводит к простому числу Фибоначчи). Другими словами, последовательность Фибоначчи является последовательностью делимости .

F _p является простым для 8 из первых 10 простых чисел p ; исключениями являются F ₂ = 1 и F ₁₉ = 4181 = 37 × 113. Однако простые числа Фибоначчи, по-видимому, становятся все реже по мере увеличения индекса. F _p является простым только для 26 из 1229 простых чисел p меньше 10 000. ^[3] Количество простых делителей в числах Фибоначчи с простым индексом составляет:

0, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 3, 2, 1, 1, 2, 2, 2, 3, 2, 2, 2, 1, 2, 4, 2, 3, 2, 2, 2, 2, 1, 1, 3, 4, 2, 4, 4, 2, 2, 3, 3, 2, 2, 4, 2, 4, 4, 2, 5, 3, 4, 3, 2, 3, 3, 4, 2, 2, 3, 4, 2, 4, 4, 4, 3, 2, 3, 5, 4, 2, 1, ... (последовательность A080345 в ОЭИС )

По состоянию на сентябрь 2023 г. ^[update], самое большое известное определенное простое число Фибоначчи - F ₂₀₁₁₀₇ с 42029 цифрами. Его премьерность доказала Майя Карпович в сентябре 2023 года. ^[4] Самое большое известное вероятное простое число Фибоначчи — F _6530879 . Его нашел Райан Проппер в августе 2022 года. ^[2]Ник Маккиннон доказал, что единственные числа Фибоначчи, которые также являются простыми числами-близнецами, — это 3, 5 и 13. ^[5]

Делимость чисел Фибоначчи [ править ]

Премьер $p$ делит $F_{p-1}$ тогда и только тогда, когда ± 1 p конгруэнтно по модулю 5 и p делит $F_{p+1}$ тогда и только тогда, когда оно конгруэнтно ±2 по модулю 5. (Для p = 5, F ₅ = 5, поэтому 5 делит F ₅ )

Числа Фибоначчи, имеющие простой индекс p, не имеют общих делителей больше 1 с предыдущими числами Фибоначчи из-за идентичности: ^[6]

\gcd(F_{n},F_{m})=F_{\gcd(n,m)}.

Для $n \geq 3$ F n _делит F m _тогда и только тогда, когда n делит m . ^[7]

Если мы предположим, что m — простое число p , а n меньше p , то ясно, что F _p не может иметь общих делителей с предыдущими числами Фибоначчи.

\gcd(F_{p},F_{n})=F_{\gcd(p,n)}=F_{1}=1.

Это означает, что F _p всегда будет иметь характеристические коэффициенты или сам будет простым характеристическим коэффициентом. Количество различных простых делителей каждого числа Фибоначчи можно выразить простыми словами.

F _nk кратен F _k для всех значений n и k таких, что n ≥ 1 и k ≥ 1. ^[8] Можно с уверенностью сказать, что F _nk будет иметь «по крайней мере» такое же количество различных простых делителей, что и F _k . Все Fp _{теоремы} не будут иметь множителей Fk _{, но будут} иметь «по крайней мере» одно новое характеристическое простое число из Кармайкла .

Теорема Кармайкла применима ко всем числам Фибоначчи, за исключением четырех особых случаев: $F_{1}=F_{2}=1,F_{6}=8$ и $F_{12}=144.$ Если мы посмотрим на простые множители числа Фибоначчи, то обнаружится, что по крайней мере один из них никогда раньше не появлялся в качестве множителя ни в одном из более ранних чисел Фибоначчи. Пусть π _n — количество различных простых делителей F _n . (последовательность A022307 в OEIS )

Если к | тогда

\pi _{n}\geqslant \pi _{k}+1

за исключением

\pi _{6}=\pi _{3}=1.

Если k = 1 и n — нечетное простое число, то 1 | п и

\pi _{p}\geqslant \pi _{1}+1=1.

н	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
Ф _н	1	1	2	3	5	8	13	21	34	55	89	144	233	377	610	987	1597	2584	4181	6765	10946	17711	28657	46368	75025
п _н	0	0	1	1	1	1	1	2	2	2	1	2	1	2	3	3	1	3	2	4	3	2	1	4	2

Первым шагом в нахождении характеристического фактора любого F _n является выделение простых множителей всех предыдущих чисел Фибоначчи F _k, для которых k | н . ^[9]

Оставшиеся точные частные — это простые множители, которые еще не появились.

Если p и q оба простые числа, то все множители F _pq являются характеристическими, за исключением множителей F _p и F _q .

{\begin{aligned}\gcd(F_{pq},F_{q})&=F_{\gcd(pq,q)}=F_{q}\\\gcd(F_{pq},F_{p})&=F_{\gcd(pq,p)}=F_{p}\end{aligned}}

Поэтому:

\pi _{pq}\geqslant {\begin{cases}\pi _{p}+\pi _{q}+1&p\neq q\\\pi _{p}+1&p=q\end{cases}}

Количество различных простых делителей чисел Фибоначчи с простым индексом имеет непосредственное отношение к счетной функции. (последовательность A080345 в OEIS )

п	2	3	5	7	11	13	17	19	23	29	31	37	41	43	47	53	59	61	67	71	73	79	83	89	97
π _п	0	1	1	1	1	1	1	2	1	1	2	3	2	1	1	2	2	2	3	2	2	2	1	2	4

Ранг появления [ править ]

Для простого числа p наименьший индекс u > 0 такой, что F _u делится на p, называется рангом появления (иногда называемым точкой входа Фибоначчи ) числа p и обозначается a ( p ). Ранг явления a ( p ) определен для каждого простого числа p . ^[10] Ранг явления делит период Пизано π( p ) и позволяет определить все числа Фибоначчи, делящиеся на p . ^[11]

Для делимости чисел Фибоначчи степенями простого числа: $p\geqslant 3,n\geqslant 2$ и $k\geqslant 0$

p^{n}\mid F_{a(p)kp^{n-1}}.

В частности

p^{2}\mid F_{a(p)p}.

Простые числа Стена-Солнце-Солнце [ править ]

Простое число p ≠ 2, 5 называется простым числом Фибоначчи–Вифериха или простым числом Уолла–Солнца–Солнца , если $p^{2}\mid F_{q},$ где

q=p-\left({\frac {p}{5}}\right)

и $\left({\tfrac {p}{5}}\right)$ является символом Лежандра :

\left({\frac {p}{5}}\right)={\begin{cases}1&p\equiv \pm 1{\bmod {5}}\\-1&p\equiv \pm 2{\bmod {5}}\end{cases}}

Известно, что при p ≠ 2,5 a ( p ) является делителем: ^[12]

p-\left({\frac {p}{5}}\right)={\begin{cases}p-1&p\equiv \pm 1{\bmod {5}}\\p+1&p\equiv \pm 2{\bmod {5}}\end{cases}}

Для каждого простого числа p, которое не является простым числом Уолла – Солнца – Солнца, $a(p^{2})=pa(p)$ как показано в таблице ниже:

п	2	3	5	7	11	13	17	19	23	29	31	37	41	43	47	53	59	61
а ( п )	3	4	5	8	10	7	9	18	24	14	30	19	20	44	16	27	58	15
а ( п ²)	6	12	25	56	110	91	153	342	552	406	930	703	820	1892	752	1431	3422	915

Существование простых чисел Стены-Солнца-Солнца является предположительным .

Примитивная часть Фибоначчи [ править ]

Потому что $F_{a}|F_{ab}$ , мы можем разделить любое число Фибоначчи $F_{n}$ по наименьшему общему кратному всех $F_{d}$ где $d|n$ . Результат называется примитивной частью $F_{n}$ . Примитивные части чисел Фибоначчи:

1, 1, 2, 3, 5, 4, 13, 7, 17, 11, 89, 6, 233, 29, 61, 47, 1597, 19, 4181, 41, 421, 199, 28657, 46, 15005, 521, 5777, 281, 514229, 31, 1346269, 2207, 19801, 3571, 141961, 321, 24157817, 9349, 135721, 2161, 165580141, 211, 4334944 37, 13201, 109441, ... (последовательность A061446 в OEIS )

Любые простые числа, которые делят $F_{n}$ и ни один из $F_{d}$ называются примитивными простыми факторами $F_{n}$ . Произведение примитивных простых делителей чисел Фибоначчи равно

1, 1, 2, 3, 5, 1, 13, 7, 17, 11, 89, 1, 233, 29, 61, 47, 1597, 19, 4181, 41, 421, 199, 28657, 23, 3001, 521, 5777, 281, 514229, 31, 1346269, 2207, 19801, 3571, 141961, 107, 24157817, 9349, 135721, 2161, 165580141, 211, 4334944 37, 13201, 109441, 64079, 2971215073, 1103, 598364773, 15251, ... (последовательность A178763 в OEIS )

Первый случай более чем одного примитивного простого множителя — 4181 = 37 × 113 для $F_{19}$ .

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

1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 13, 1, 1, .... (последовательность A178764 в OEIS )

Натуральные числа n, для которых $F_{n}$ имеет ровно один примитивный простой делитель

3, 4, 5, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 28, 29, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 43, 45, 47, 48, 51, 52, 54, 56, 60, 62, 63, 65, 66, 72, 74, 75, 76, 82, 83, 93, 94, 98, 105, 106, 108, 111, 112, 119, 121, 122, 123, 124, 125, 131, 132, 135, 136, 137, 140, 142, 144, 145, ... (последовательность A152012 в OEIS )

Для простого числа p когда p находится в этой последовательности тогда и только тогда, $F_{p}$ является простым числом Фибоначчи, и 2 p принадлежит этой последовательности тогда и только тогда, когда $L_{p}$ является простым числом Люка (где $L_{p}$ это $p$ число Лукаса ). Более того, 2 ^н находится в этой последовательности тогда и только тогда, когда $L_{2^{n-1}}$ является простым числом Лукаса.

Число примитивных простых делителей $F_{n}$ являются

0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 3, 1, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 2, 1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 2, 1, 1, 2, 1, 1, 3, 2, 3, 2, 2, 1, 2, 1, 1, 1, 2, 2, 2, 2, 3, 1, 1, 2, 2, 2, 2, 3, 2, 2, 2, 2, 1, 1, 3, 2, 4, 1, 2, 2, 2, 2, 3, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 2, 2, 2, 2, 3, 1, 2, 1, 1, 1, 1, 1, 2, 2, 2, ... (последовательность A086597 в OEIS )

Наименее примитивные простые множители $F_{n}$ являются

1, 1, 2, 3, 5, 1, 13, 7, 17, 11, 89, 1, 233, 29, 61, 47, 1597, 19, 37, 41, 421, 199, 28657, 23, 3001, 521, 53, 281, 514229, 31, 557, 2207, 19801, 3571, 141961, 107, 73, 9349, 135721, 2161, 2789, 211, 433494437, 43, 109441, 1 39, 2971215073, 1103, 97, 101, ... (последовательность A001578 в OEIS )

Предполагается, что все простые множители $F_{n}$ примитивны, когда $n$ является простым числом. ^[13]

Числа Фибоначчи в простых последовательностях [ править ]

Хотя неизвестно, существует ли бесконечное количество простых чисел в последовательности Фибоначчи, Мелфи доказал, что существует бесконечно много простых чисел. ^[14] среди практических чисел — последовательность, подобная простым числам.

См. также [ править ]

число Лукаса

Ссылки [ править ]

^ «Простое число Фибоначчи» .
^ Перейти обратно: ^а ^б Лучшие рекорды PRP, Поиск: F(n) . Проверено 05 апреля 2018 г.
^ Слоана OEIS : A005478 , OEIS : A001605
^ «Двадцатка лучших: число Фибоначчи» . primes.utm.edu . Проверено 15 сентября 2023 г.
^ Н. Маккиннон, Задача 10844, Amer. Математика. Ежемесячно 109, (2002), с. 78
^ Пауло Рибенбойм , Мои числа, мои друзья , Springer-Verlag 2000
^ Уэллс 1986, стр.65.
^ Математическая магия чисел Фибоначчи Факторы чисел Фибоначчи
^ Джарден - Повторяющиеся последовательности, Том 1, ежеквартально по Фибоначчи, брат У. Альфред
^ (последовательность A001602 в OEIS )
^ Джон Винсон (1963). «Связь периода по модулю m с рангом появления m в последовательности Фибоначчи» (PDF) . Ежеквартальный журнал Фибоначчи . 1 : 37–45.
^ Стивен Вайда. Числа Фибоначчи и Люка и золотое сечение: теория и приложения . Дуврские книги по математике.
^ Математическая магия чисел Фибоначчи Числа Фибоначчи и простые числа
^ Джузеппе Мелфи (1995). «Опрос по практическим цифрам» (PDF) . Ренд. Сем. Мат. Турин . 53 : 347–359.

Внешние ссылки [ править ]

Вайсштейн, Эрик В. «Простое число Фибоначчи» . Математический мир .
Р. Нотт Простые числа Фибоначчи
Колдуэлл, Крис. Число Фибоначчи , простое число Фибоначчи и запись простых чисел Фибоначчи на главных страницах.
Факторизация первых 300 чисел Фибоначчи
Факторизация чисел Фибоначчи и Люка. Архивировано 19 августа 2016 г. в Wayback Machine.
Небольшая параллельная программа на Haskell для поиска вероятных простых чисел Фибоначчи на haskell.org

[1] «Простое число Фибоначчи» .

[prptop-2] Перейти обратно: ^а ^б Лучшие рекорды PRP, Поиск: F(n) . Проверено 05 апреля 2018 г.

[3] Слоана OEIS : A005478 , OEIS : A001605

[4] «Двадцатка лучших: число Фибоначчи» . primes.utm.edu . Проверено 15 сентября 2023 г.

[5] Н. Маккиннон, Задача 10844, Amer. Математика. Ежемесячно 109, (2002), с. 78

[6] Пауло Рибенбойм , Мои числа, мои друзья , Springer-Verlag 2000

[7] Уэллс 1986, стр.65.

[8] Математическая магия чисел Фибоначчи Факторы чисел Фибоначчи

[9] Джарден - Повторяющиеся последовательности, Том 1, ежеквартально по Фибоначчи, брат У. Альфред

[10] (последовательность A001602 в OEIS )

[11] Джон Винсон (1963). «Связь периода по модулю m с рангом появления m в последовательности Фибоначчи» (PDF) . Ежеквартальный журнал Фибоначчи . 1 : 37–45.

[12] Стивен Вайда. Числа Фибоначчи и Люка и золотое сечение: теория и приложения . Дуврские книги по математике.

[13] Математическая магия чисел Фибоначчи Числа Фибоначчи и простые числа

[14] Джузеппе Мелфи (1995). «Опрос по практическим цифрам» (PDF) . Ренд. Сем. Мат. Турин . 53 : 347–359.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

v т и Классы простых чисел
По формуле	Ферма ( $2 2 н + 1$ ) Мерсенн ( $2 п - 1$ ) Двойной Мерсенн ( $2 2 п -1 - 1$ ) Вагстафф $(2 п + 1)/3$ Прот ( $k \cdot2 н + 1$ ) Факториал ( $n! \pm 1$ ) Первобытный ( $p n # \pm 1$ ) Евклид ( $p n # + 1$ ) Пифагорейский ( $4 n + 1$ ) Пьерпон ( $2 м \cdot3 н + 1$ ) Квартан ( $х 4 + и 4$ ) Солинас ( $2 м \pm 2 н \pm 1$ ) Каллен ( $n \cdot2 н + 1$ ) Вудалл ( $n \cdot2 н - 1$ ) Кубинский ( $х 3 - и 3)/(Икс - у$ ) Лейланд ( $x и + и х$ ) Сабит ( $3 \cdot 2 н - 1$ ) Уильямс ( $(b -1)\cdot b н - 1$ ) Миллс ( $⌊ А 3 н ⌋$ )
По целочисленной последовательности	Фибоначчи Лукас Пелл Ньюман–Шэнкс–Уильямс Перрин
По свойству	Виферих ( пара ) Стена–Солнце–Солнце Вулстенхолм Уилсон Удачливый удачливый Рамануджан Пиллаи Обычный Сильный Стерн Суперсингулярная (эллиптическая кривая) Суперсингулярная (теория самогона) Хороший Супер Хиггс Высокий коэффициент Уникальный
Базово -зависимый	палиндромный Эмирп Репунит $(10 н - 1)/9$ Перестановочный Круговой Усекаемый Минимальный Нежный Первобытный Полный отчет Уникальный Счастливый Себя Смарандаш-Веллин Стробограмматический двугранный тетрадный
Узоры	Твин ( $р, р + 2$ ) Двойная цепь ( $n \pm1, 2n \pm 1, 4n \pm 1, \dots$ ) Тройка ( $p, p +2 или p +4, p +6$ ) Четверка ( $р, р +2, р +6, р +8$ ) k -кортеж Двоюродный брат ( $п, р + 4$ ) Сексуальный ( $п, п + 6$ ) Чен Софи Жермен/Сейф ( $п, 2п +1$ ) Каннингем ( $п, 2 п \pm 1, 4 п \pm 3, 8 п \pm 7, ...$ ) Арифметическая прогрессия ( $p + a\cdotn, n = 0, 1, 2, 3, ...$ ) Сбалансированный ( $последовательные p - n, p, p + n$ )
По размеру	Мега (1 000 000+ цифр) Самый крупный известный список
Комплексные числа	простое число Эйзенштейна Гауссово простое число
Составные числа	Псевдопростой каталонский Эллиптический Эйлер Эйлер-Якоби Ферма Фробениус Лукас Перрин Сомер-Лукас Сильный Число Кармайкла Почти премьер Полупростые числа Сфеническое число Интерпрайм Пагубный
Связанные темы	Вероятное простое число Промышленный класс Prime Незаконный премьер Формула простых чисел Премьер-разрыв
Первые 60 простых чисел	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281
Список простых чисел