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

 В теории чисел числами Перрина называются члены линейнойрекуррентной последовательности:

P(0) = 3, P(1) = 0, P(2) = 2,
 и

P(n) = P(n − 2) + P(n − 3) forn \textgreater 2.
 Последовательность чисел Перрина начинается с

 3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, ...

История


 Эта последовательность была упомянута Эдвардом Лукасом (Édouard Lucas) в1876-м. В 1899-м ту же самую последовательность использовал в явном видеПеррин. Наиболее глубокое изучение этой последовательности было сделаноАдамсом (Adams) и Шанксом (Shanks) (1982).

Свойства


Производящаяфункция


 Производящей функцией чисел Перрина является
G(P(n);x)=3x21x2x3.

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


(010001110)n(302)=(P(n)P(n+1)P(n+2))

Аналог формулыБине


 Последовательность чисел Перрина может быть записана в терминах степеникорней характеристического уравнения
x3x1=0.
Это уравнение имеет три корня. Один из этих корнейвещественный p (известен как пластическое число) и двакомплексных сопряженных корней q и r. Используя эти трикорня, можно выразить число Перрина аналогично формуле Бине для чиселЛюка:
P(n)=pn+qn+rn.

 Поскольку абсолютные значения комплексных корней q и rменьше 1, степени этих корней будут стремиться к 0 при увеличенииn. Для больших n формула упрощается до
P(n)pn

 Эта формула может быть использована для быстрого вычисления чисел Перинадля больших n. Отношение последовательных членовпоследовательности Перина стремится к p ≈ 1.324718. Эта константаиграет ту же роль для последовательности Перина, что и золотое сечениедля чисел Люка. Аналогичная связь существует между p ипоследовательностью Падована, между золотым сечением и числамиФибоначчи, а также между серебряным сечением и числами Пелля.

Формулаумножения


 Из формул Бине мы можем получить формулы для G(kn) втерминах G(n−1), G(n) иG(n+1). Мы знаем, что
G(n1)=p1pn+q1qn+r1rnG(n)=pn+qn+rnG(n+1)=ppn+qqn+rrn

 Что дает нам систему из трех линейных уравнений с коэффициентами из поляразложения многочлена x3x1. Вычислив обратную матрицу, мы можемрешить уравнения и получить pn,qn,rn. Затем мы можем возвести встепень 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(n1),v=G(n),w=G(n+1). В результате решения системыполучим
23G(2n1)=4u2+3v2+9w2+18uv12uw4vw23G(2n)=6u2+7v22w24uv+18uw+6vw23G(2n+1)=9u2+v2+3w2+6uv4uw+14vw23G(3n1)=(4u3+2v3w3+9(uv2+vw2+wu2)+3v2w+6uvw)23G(3n)=(3u3+2v3+3w33(uv2+uw2+vw2+vu2)+6v2w+18uvw)23G(3n+1)=(v3w3+6uv2+9uw2+6vw2+9vu23wu2+6wv26uvw)

 Число 23 возникает в этих формулах как дискриминант многочлена,задающего последовательность (x3x1).
 Это позволяет вычислять n-ое число Перрина в арифметике целых чисел,используя O(logn) умножений.

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


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


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

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


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

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