Interested Article - Число Перрена
- 2020-05-28
- 1
В теории чисел числами Перрена называются члены линейной рекуррентной последовательности :
- P (0) = 3, P (1) = 0, P (2) = 2,
и
- P ( n ) = P ( n − 2) + P ( n − 3) for n > 2.
Последовательность чисел Перрена начинается с
История
Эта последовательность была упомянута Эдуардом Люка́ (Édouard Lucas) в 1876-м. В 1899-м ту же самую последовательность использовал в явном виде Перрен. Наиболее глубокое изучение этой последовательности было сделано Адамсом (Adams) и Шанксом (Shanks) (1982).
Свойства
Производящая функция
Производящей функцией чисел Перрена является
Матричное представление
Аналог формулы Бине
Последовательность чисел Перрена может быть записана в терминах степени корней характеристического уравнения
Это уравнение имеет три корня. Один из этих корней p вещественный (известен как пластическое число ). Используя его и два сопряженных комплексных корня q и r , можно выразить число Перрена аналогично формуле Бине для чисел Люка :
Поскольку абсолютные значения комплексных корней q и r меньше 1, степени этих корней будут стремиться к 0 при увеличении n . Для больших n формула упрощается до
Эта формула может быть использована для быстрого вычисления чисел Перрена для больших n . Отношение последовательных членов последовательности Перрена стремится к p ≈ 1.324718. Эта константа играет ту же роль для последовательности Перрена, что и золотое сечение для чисел Люка . Аналогичная связь существует между p и последовательностью Падована , между золотым сечением и числами Фибоначчи, а также между серебряным сечением и числами Пелля .
Формула умножения
Из формул Бине мы можем получить формулы для G ( kn ) в терминах G ( n −1), G ( n ) и G ( n +1). Мы знаем, что
Что дает нам систему из трех линейных уравнений с коэффициентами из поля разложения многочлена . Вычислив обратную матрицу, мы можем решить уравнения и получить . Затем мы можем возвести в степень k все три полученных значения и посчитать сумму.
Пример программы :
P<x> := PolynomialRing(Rationals()); S<t> := SplittingField(x^3-x-1); P2<y> := PolynomialRing(S); p,q,r := Explode([r[1] : r in Roots(y^3-y-1)]); Mi:=Matrix([[1/p,1/q,1/r],[1,1,1],[p,q,r]])^(-1); T<u,v,w> := PolynomialRing(S,3); v1 := ChangeRing(Mi,T) *Matrix([[u],[v],[w]]); [p^i*v1[1,1]^3 + q^i*v1[2,1]^3 + r^i*v1[3,1]^3 : i in [-1..1]];
Положим . В результате решения системы получим
Число 23 возникает в этих формулах как дискриминант многочлена, задающего последовательность ( ).
Это позволяет вычислять n-ое число Перрена в арифметике целых чисел, используя умножений.
Простые и делимость
Псевдопростые числа Перрена
Было доказано, что все простые p делят P ( p ). Обратно, однако, неверно — некоторые составные числа n могут делить P ( n ), такие числа называются псевдопростыми числами Перрена .
Вопрос о существовании псевдопростых чисел Перрена был рассмотрен самим Перреном, но было неизвестно, существуют они или нет, пока Адамс (Adams) и Шанкс (Shanks) (1982) не обнаружили наименьшее из них, 271441 = 521 2 . Следующим стало . Известно семнадцать псевдопростых чисел Перрена, меньших миллиарда; Джон Грантам (Jon Grantham) доказал , что имеется бесконечно много псевдопростых чисел Перрена.
Простые числа Перрена
Числа Перрена, являющиеся простыми , образуют последовательность:
- 2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977, 187278659180417234321, 66241160488780141071579864797 (последовательность в OEIS )
Вайсстайн нашёл вероятно простое число Перрена P (263226) с 32147 знаками в мае 2006 года .
Примечания
- последовательность в OEIS
- Jon Grantham. (англ.) // Journal of Number Theory : journal. — 2010. — Vol. 130 , no. 5 . — P. 1117—1128 . — doi : . 17 июня 2013 года.
- Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .
Литература
- Adams, William; Shanks, Daniel. Strong primality tests that are not sufficient (англ.) // Vol. 39 , no. 159 . — P. 255—300 . — doi : . — . : journal. — American Mathematical Society, 1982. —
- Vol. 11 , no. 4 . — P. 463—470 . — doi : . The number of maximal independent sets in connected graphs (англ.) // : journal. — 1987. —
- American Journal of Mathematics : magazine. — The Johns Hopkins University Press, 1878. — Vol. 1 , n o 3 . — P. 197—240 . — doi : . — . Théorie des fonctions numériques simplement périodiques (фр.) //
- Perrin, R. Query 1484 (неопр.) // L'Intermediaire Des Mathematiciens. — 1899. — Т. 6 . — С. 76 .
Ссылки
- 2020-05-28
- 1