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

 В теории чисел числами Перрина называются члены линейной рекуррентной последовательности:
 
  P(0) = 3, P(1) = 0, P(2) = 2,
  и
 
  P(n) = P(n − 2) + P(n − 3) for n \textgreater 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). Мы знаем, что
 
 Что дает нам систему из трех линейных уравнений с коэффициентами из поля разложения многочлена x3−x−1$x^3-x-1$. Вычислив обратную матрицу, мы можем решить уравнения и получить pn,qn,rn$p^n,q^n,r^n$. Затем мы можем возвести в степень k все три полученных значения и посчитать сумму.
 Пример программы в системе Magma:
 \textttP\textlessx\textgreater := PolynomialRing(Rationals);\\\textttS\textlesst\textgreater := SplittingField(x\^3-x-1); \\\textttP2\textlessy\textgreater := PolynomialRing(S);\\\textttp,q,r := Explode([r[1] : r in Roots(y\^3-y-1)]);\\\textttMi:=Matrix([[1/p,1/q,1/r],[1,1,1],[p,q,r]])\^(-1);\\\textttT\textlessu,v,w\textgreater := PolynomialRing(S,3);\\\textttv1 := ChangeRing(Mi,T) *Matrix([[u],[v],[w]]);\\\texttt[p\^i*v1[1,1]\^3 + q\^i*v1[2,1]\^3 + r\^i*v1[3,1]\^3 : i in [-1..1]];
 Положим u=G(n−1),v=G(n),w=G(n+1)$u=G(n-1),v=G(n),w=G(n+1)$. В результате решения системы получим
 
 Число 23 возникает в этих формулах как дискриминант многочлена, задающего последовательность (x3−x−1$x^3-x-1$).
 Это позволяет вычислять n-ое число Перрина в арифметике целых чисел, используя O(logn)$O(\log n)$ умножений.
 

Простые и делимость

 

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

 Было доказано, что все простые p делят P(p). Обратно, однако, неверно — некоторые составные числа n могут делить P(n), такие числа называются псевдопростыми Перрина.
 Вопрос о существовании псевдопростых Перрина был рассмотрен самим Перрином, но было неизвестно, существуют они или нет, пока Адамс (Adams) и Шанкс (Shanks) (1982) не обнаружили наименьшее из них, 271441 = 521². Следующим стало 904631=7×13×9941$904631=7\times 13\times 9941$. Известно семнадцать псевдопростых чисел Перрина, меньших миллиарда; Джон Грантам (Jon Grantham) доказал, что имеется бесконечно много псевдопростых чисел Перрина.
 

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

 Числа Перрина, являющиеся простыми, образуют последовательность:
 
  2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977, 187278659180417234321, 66241160488780141071579864797
  Вайсштайн нашел вероятно простое число Перрина P(263226) с 32147 знаками в мае 2006 года.