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

Твірною функцією чисел Перрена є

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

${\displaystyle {\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}}}$

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

${\displaystyle x^{3}-x-1=0.}$

Це рівняння має три корені. Один з цих коренів p дійсний (відомий як пластичне число). Використовуючи його і два спряжених комплексних корені q і r, можна виразити число Перрена аналогічно формулі Біне для чисел Люка:

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

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

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

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

З формул Біне можна отримати формули для G(kn) в термінах G(n-1), G(n) і G(n+1). Відомо, що

${\displaystyle {\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}}}$

Що дає систему трьох лінійних рівнянь з коефіцієнтами з поля розкладу многочлена ${\displaystyle x^{3}-x-1}$. Визначивши обернену матрицю, можна розв'язати рівняння й отримати ${\displaystyle 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]];

Нехай ${\displaystyle u=G(n-1),v=G(n),w=G(n+1)}$. Розв'язавши систему, отримаємо

${\displaystyle {\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 виникає в цих формулах як дискримінант многочлена, який задає послідовність (${\displaystyle x^{3}-x-1}$).

Це дозволяє обчислювати n-е число Перрена в арифметиці цілих чисел, використовуючи ${\displaystyle O(\log n)}$ множень.

Доведено, що всі прості p ділять P(p). Зворотне, однак, хибне — деякі складені числа n можуть ділити P(n), такі числа називаються псевдопростими числами Перрена.

Питання про існування псевдопростих чисел Перрена розглянув сам Перрен, але було невідомо, існують вони чи ні, поки Адамс (Adams) і Шанкс (Shanks) (1982) не виявили найменшого з них, 271441 = 521². Наступним стало ${\displaystyle 904631=7\times 13\times 9941}$. Відомо сімнадцять псевдопростих чисел Перрена, менших від мільярда. Джон Ґрантам (Jon Grantham) довів[1], що є нескінченно багато псевдопростих чисел Перрена.

Числа Перрена, які є простими, утворюють послідовність:

2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977, 187278659180417234321, 66241160488780141071579864797 послідовність A074788 з Онлайн енциклопедії послідовностей цілих чисел, OEIS

У травні 2006 року Вайсстайн знайшов ймовірно просте число Перрена P(263226) з 32147 знаків.