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

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

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

і

P(n) = P(n − 2) + P(n − 3) для n > 2.

Послідовність чисел Перрена починається з

3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, … (Шаблон:OEIS)

Історія

Цю послідовність згадав 1876 року Едуард Люка. В 1899 цю саму послідовність використовував у явному вигляді Перрен. Найглибше цю послідовність вивчили Адамс (Adams) і Шанкс (Shanks) (1982).

Властивості

Твірна функція

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

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

Матричне подання

${\left(\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\\ 1& 1& 0\end{array}\right)}^n\left(\begin{array}{c}3\\ 0\\ 2\end{array}\right)=\left(\begin{array}{c}P\left(n\right)\\ P(n+1)\\ P(n+2)\end{array}\right)$

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

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

$x^3-x-1=0.$

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

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

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

$P\left(n\right)\approx p^n$

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

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

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

$\begin{array}{ccccc}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)& =& p{p}^n+& q{q}^n+& r{r}^n\end{array}$

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

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

$\begin{array}{ccc}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)& =& (-4u^3+2v^3-w^3+9(u{v}^2+v{w}^2+w{u}^2)+3v^{2}w+6uvw)\\ 23G(3n)& =& (3u^3+2v^3+3w^3-3(u{v}^2+u{w}^2+v{w}^2+v{u}^2)+6v^{2}w+18uvw)\\ 23G(3n+1)& =& (v^3-w^3+6u{v}^2+9u{w}^2+6v{w}^2+9v{u}^2-3w{u}^2+6w{v}^2-6uvw)\end{array}$

Число 23 виникає в цих формулах як дискримінант многочлена, який задає послідовність ($x^3-x-1$).

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

Прості й подільність

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

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

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

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

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

2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977, 187278659180417234321, 66241160488780141071579864797 Шаблон:OEIS

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

Джерела

• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття

Посилання

• Zentrum für Hirnforschung Institut für Medizinische Kybernetik und Artificial Intelligence
• MathPages — Lucas Pseudoprimes
• MathPages — Perrin's Sequence