В теории чисел
числами Перрина называются члены линейной
рекуррентной последовательности:
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).
Свойства
Производящая
функция
Производящей функцией чисел Перрина является
G(P(n);x)=3−x21−x2−x3.
Матричное
представление
⎛⎝⎜001101010⎞⎠⎟n⎛⎝⎜302⎞⎠⎟=⎛⎝⎜P(n)P(n+1)P(n+2)⎞⎠⎟
Аналог формулы
Бине
Последовательность чисел Перрина может быть записана в терминах степени
корней характеристического уравнения
x3−x−1=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(n−1)G(n)G(n+1)===p−1pn+pn+ppn+q−1qn+qn+qqn+r−1rnrnrrn
Что дает нам систему из трех линейных уравнений с коэффициентами из поля
разложения многочлена
x3−x−1. Вычислив обратную матрицу, мы можем
решить уравнения и получить
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(n−1),v=G(n),w=G(n+1). В результате решения системы
получим
23G(2n−1)23G(2n)23G(2n+1)23G(3n−1)23G(3n)23G(3n+1)======4u2+3v2+9w2+18uv−12uw−4vw−6u2+7v2−2w2−4uv+18uw+6vw9u2+v2+3w2+6uv−4uw+14vw(−4u3+2v3−w3+9(uv2+vw2+wu2)+3v2w+6uvw)(3u3+2v3+3w3−3(uv2+uw2+vw2+vu2)+6v2w+18uvw)(v3−w3+6uv2+9uw2+6vw2+9vu2−3wu2+6wv2−6uvw)
Число 23 возникает в этих формулах как дискриминант многочлена,
задающего последовательность (
x3−x−1).
Это позволяет вычислять n-ое число Перрина в арифметике целых чисел,
используя
O(logn) умножений.
Простые и
делимость
Псевдопростые числа
Перрина
Было доказано, что все простые
p делят
P(
p).
Обратно, однако, неверно — некоторые составные числа
n могут
делить
P(
n), такие числа называются
псевдопростыми
Перрина.
Вопрос о существовании псевдопростых Перрина был рассмотрен самим
Перрином, но было неизвестно, существуют они или нет, пока Адамс (Adams)
и Шанкс (Shanks) (1982) не обнаружили наименьшее из них, 271441 =
521
2. Следующим стало
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 года.