Число Перрена
В теории чисел числами Перрена называются члены линейной рекуррентной последовательности:
- P(0) = 3, P(1) = 0, P(2) = 2,
и
- P(n) = P(n − 2) + P(n − 3) for n > 2.
Последовательность чисел Перрена начинается с
История
Эта последовательность была упомянута Эдуардом Люка́ (Édouard Lucas) в 1876-м. В 1899-м ту же самую последовательность использовал в явном виде Перрен. Наиболее глубокое изучение этой последовательности было сделано Адамсом (Adams) и Шанксом (Shanks) (1982).
Свойства
Производящая функция
Производящей функцией чисел Перрена является
- [math]\displaystyle{ G(P(n);x)=\frac{3-x^2}{1-x^2-x^3}. }[/math]
Матричное представление
- [math]\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} }[/math]
Аналог формулы Бине
Последовательность чисел Перрена может быть записана в терминах степени корней характеристического уравнения
- [math]\displaystyle{ x^3 -x -1 = 0. }[/math]
Это уравнение имеет три корня. Один из этих корней p вещественный (известен как пластическое число). Используя его и два сопряженных комплексных корня q и r, можно выразить число Перрена аналогично формуле Бине для чисел Люка:
- [math]\displaystyle{ P\left(n\right) = {p^n} + {q^n} + {r^n}. }[/math]
Поскольку абсолютные значения комплексных корней q и r меньше 1, степени этих корней будут стремиться к 0 при увеличении n. Для больших n формула упрощается до
- [math]\displaystyle{ P\left(n\right) \approx {p^n} }[/math]
Эта формула может быть использована для быстрого вычисления чисел Перрена для больших n. Отношение последовательных членов последовательности Перрена стремится к p ≈ 1.324718. Эта константа играет ту же роль для последовательности Перрена, что и золотое сечение для чисел Люка. Аналогичная связь существует между p и последовательностью Падована, между золотым сечением и числами Фибоначчи, а также между серебряным сечением и числами Пелля.
Формула умножения
Из формул Бине мы можем получить формулы для G(kn) в терминах G(n−1), G(n) и G(n+1). Мы знаем, что
- [math]\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} }[/math]
Что дает нам систему из трех линейных уравнений с коэффициентами из поля разложения многочлена [math]\displaystyle{ x^3 -x -1 }[/math]. Вычислив обратную матрицу, мы можем решить уравнения и получить [math]\displaystyle{ p^n, q^n, r^n }[/math]. Затем мы можем возвести в степень 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]];
Положим [math]\displaystyle{ u = G(n-1), v = G(n), w = G(n+1) }[/math]. В результате решения системы получим
- [math]\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^2w+6uvw\right)\\ 23G(3n)& = &\left(3u^3 + 2v^3 + 3w^3 - 3(uv^2 + uw^2 + vw^2 + vu^2) + 6v^2w + 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} }[/math]
Число 23 возникает в этих формулах как дискриминант многочлена, задающего последовательность ([math]\displaystyle{ x^3 -x -1 }[/math]).
Это позволяет вычислять n-ое число Перрена в арифметике целых чисел, используя [math]\displaystyle{ O(\log n) }[/math] умножений.
Простые и делимость
Псевдопростые числа Перрена
Было доказано, что все простые p делят P(p). Обратно, однако, неверно — некоторые составные числа n могут делить P(n), такие числа называются псевдопростыми числами Перрена.
Вопрос о существовании псевдопростых чисел Перрена был рассмотрен самим Перреном, но было неизвестно, существуют они или нет, пока Адамс (Adams) и Шанкс (Shanks) (1982) не обнаружили наименьшее из них, 271441 = 5212. Следующим стало [math]\displaystyle{ 904631 = 7 \times 13 \times 9941 }[/math]. Известно семнадцать псевдопростых чисел Перрена, меньших миллиарда;[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. — .
- 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, no 3. — P. 197—240. — doi:10.2307/2369311. — .
- Perrin, R. Query 1484 (неопр.) // L'Intermediaire Des Mathematiciens. — 1899. — Т. 6. — С. 76.
Ссылки
- Zentrum für Hirnforschung Institut für Medizinische Kybernetik und Artificial Intelligence
- MathPages — Lucas Pseudoprimes
- MathPages — Perrin’s Sequence
Для улучшения этой статьи желательно: |