Число Перрена

В теории чисел числами Перрена называются члены линейной рекуррентной последовательности:
 P(0) = 3, P(1) = 0, P(2) = 2,
и
 P(n) = P(n − 2) + P(n − 3) for n > 2.

Последовательность чисел Перрена начинается с
 3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, ... ()

История 
Эта последовательность была упомянута Эдуардом Люка́ (É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 все три полученных значения и посчитать сумму.

Пример программы в системе Magma:

 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 = 5212.
Следующим стало .
Известно семнадцать псевдопростых чисел Перрена, меньших миллиарда;
Джон Грантам (Jon Grantham) доказал, что имеется бесконечно много псевдопростых чисел Перрена.

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

Числа Перрена, являющиеся простыми, образуют последовательность:

 2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977, 187278659180417234321, 66241160488780141071579864797 ()

Вайсстайн нашёл вероятно простое число Перрена P(263226) с 32147 знаками в мае 2006 года.

Примечания

Литература

Ссылки 
 Zentrum für Hirnforschung Institut für Medizinische Kybernetik und Artificial Intelligence
 MathPages — Lucas Pseudoprimes
 MathPages — Perrin’s Sequence

Теория чисел
Теория простых чисел
Рекурсия
Целочисленные последовательности