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

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

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, ... (последовательность A001608 в OEIS)

ИсторияПравить

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

СвойстваПравить

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

Производящей функцией чисел Перрена является

\text{[math]}

G(P(n);x)={\frac {3-x^{2}}{1-x^{2}-x^{3}}}.

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

\text{[math]}

{\begin{pmatrix}0&1&0\\0&0&1\\1&1&0\end{pmatrix}}^{n}{\begin{pmatrix}3\\0\\2\end{pmatrix}}={\begin{pmatrix}P\left(n\right)\\P\left(n+1\right)\\P\left(n+2\right)\end{pmatrix}}

Аналог формулы БинеПравить

Последовательность чисел Перрена может быть записана в терминах степени корней характеристического уравнения

\text{[math]}

x^{3}-x-1=0.

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

\text{[math]}

P\left(n\right)={p^{n}}+{q^{n}}+{r^{n}}.

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

\text{[math]}

P\left(n\right)\approx {p^{n}}

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

Формула умноженияПравить

Из формул Бине мы можем получить формулы для G(kn) в терминах G(n−1), G(n) и G(n+1). Мы знаем, что

\text{[math]}

{\begin{matrix}G(n-1)&=&p^{-1}p^{n}+&q^{-1}q^{n}+&r^{-1}r^{n}\\G(n)&=&p^{n}+&q^{n}+&r^{n}\\G(n+1)&=&pp^{n}+&qq^{n}+&rr^{n}\end{matrix}}

Что дает нам систему из трех линейных уравнений с коэффициентами из поля разложения многочлена $\text{[math]}$ $\text{[math]}$ $x^{3}-x-1$ . Вычислив обратную матрицу, мы можем решить уравнения и получить $\text{[math]}$ $\text{[math]}$ $p^{n},q^{n},r^{n}$ . Затем мы можем возвести в степень 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]];

Положим $\text{[math]}$ $\text{[math]}$ $u=G(n-1),v=G(n),w=G(n+1)$ . В результате решения системы получим

\text{[math]}

{\begin{matrix}23G(2n-1)&=&4u^{2}+3v^{2}+9w^{2}+18uv-12uw-4vw\\23G(2n)&=&-6u^{2}+7v^{2}-2w^{2}-4uv+18uw+6vw\\23G(2n+1)&=&9u^{2}+v^{2}+3w^{2}+6uv-4uw+14vw\\23G(3n-1)&=&\left(-4u^{3}+2v^{3}-w^{3}+9(uv^{2}+vw^{2}+wu^{2})+3v^{2}w+6uvw\right)\\23G(3n)&=&\left(3u^{3}+2v^{3}+3w^{3}-3(uv^{2}+uw^{2}+vw^{2}+vu^{2})+6v^{2}w+18uvw\right)\\23G(3n+1)&=&\left(v^{3}-w^{3}+6uv^{2}+9uw^{2}+6vw^{2}+9vu^{2}-3wu^{2}+6wv^{2}-6uvw\right)\end{matrix}}

Число 23 возникает в этих формулах как дискриминант многочлена, задающего последовательность ( $\text{[math]}$ $\text{[math]}$ $x^{3}-x-1$ ).

Это позволяет вычислять n-ое число Перрена в арифметике целых чисел, используя $\text{[math]}$ $\text{[math]}$ $O(\log n)$ умножений.

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

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

Было доказано, что все простые p делят P(p). Обратно, однако, неверно — некоторые составные числа n могут делить P(n), такие числа называются псевдопростыми числами Перрена.

Вопрос о существовании псевдопростых чисел Перрена был рассмотрен самим Перреном, но было неизвестно, существуют они или нет, пока Адамс (Adams) и Шанкс (Shanks) (1982) не обнаружили наименьшее из них, 271441 = 521². Следующим стало $\text{[math]}$ $\text{[math]}$ $904631=7\times 13\times 9941$ . Известно семнадцать псевдопростых чисел Перрена, меньших миллиарда;^[1] Джон Грантам (Jon Grantham) доказал^[2], что имеется бесконечно много псевдопростых чисел Перрена.

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

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

2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977, 187278659180417234321, 66241160488780141071579864797 (последовательность A074788 в OEIS)

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

ПримечанияПравить

↑ последовательность A013998 в OEIS
↑ Jon Grantham. There are infinitely many Perrin pseudoprimes (англ.) // Journal of Number Theory : journal. — 2010. — Vol. 130, no. 5. — P. 1117—1128. — doi:10.1016/j.jnt.2009.11.008.
↑ Weisstein, Eric W. Perrin Sequence (англ.) на сайте Wolfram MathWorld.

ЛитератураПравить

Adams, William; Shanks, Daniel. Strong primality tests that are not sufficient (англ.) // Mathematics of Computation (англ.) (рус. : journal. — American Mathematical Society, 1982. — Vol. 39, no. 159. — P. 255—300. — doi:10.2307/2007637. — JSTOR 2007637.

Füredi, Z. (англ.) (рус.. The number of maximal independent sets in connected graphs (англ.) // Journal of Graph Theory (англ.) (рус. : journal. — 1987. — Vol. 11, no. 4. — P. 463—470. — doi:10.1002/jgt.3190110403.

Lucas, E. (англ.) (рус.. Théorie des fonctions numériques simplement périodiques (фр.) // American Journal of Mathematics : magazine. — The Johns Hopkins University Press, 1878. — Vol. 1, n^o 3. — P. 197—240. — doi:10.2307/2369311. — JSTOR 2369311.

Perrin, R. Query 1484 (неопр.) // L'Intermediaire Des Mathematiciens. — 1899. — Т. 6. — С. 76.

СсылкиПравить

[1] последовательность A013998 в OEIS

[2] Jon Grantham. There are infinitely many Perrin pseudoprimes (англ.) // Journal of Number Theory : journal. — 2010. — Vol. 130, no. 5. — P. 1117—1128. — doi:10.1016/j.jnt.2009.11.008.

[3] Weisstein, Eric W. Perrin Sequence (англ.) на сайте Wolfram MathWorld.

[1]

[2]

[3]