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

В математике числа Перрина определяются рекуррентным соотношением

P ( n ) = P ( n - 2) + P ( n - 3) для n > 2 ,

с начальными значениями

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

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

3 , 0 , 2 , 3, 2, 5 , 5, 7 , 10 , 12 , 17 , 22 , 29 , 39 , ... (последовательность A001608 в OEIS )

Количество различных максимальных независимых множеств в графе циклов с n вершинами считается n- м числом Перрина для n > 1 . ^{[1] [ необходима страница ]}

История [ править ]

Эта последовательность неявно упоминается Эдуардом Лукасом (1876 г.). В 1899 году эта же последовательность была прямо упомянута Франсуа Оливье Раулем Перреном. ^{[2] [ необходима страница ]} Наиболее подробное описание этой последовательности было дано Адамсом и Шанксом (1982).

Свойства [ править ]

Функция генерации [ править ]

Производящая функция последовательности Perrin является

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

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

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

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

${\ Displaystyle Р \ влево (п \ вправо) \ приблизительно {р ^ {п}}}$

Эту формулу можно использовать для быстрого вычисления значений последовательности Перрина для больших 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 ^ {п} \ конец {матрица}}}$

что дает нам три линейных уравнений с коэффициентами над полем разложения в ; путем инвертирования матрицы, которую мы можем найти, а затем возвести их в k- ю степень и вычислить сумму.${\ displaystyle x ^ {3} -x-1}$${\ displaystyle p ^ {n}, q ^ {n}, r ^ {n}}$

Пример кода магмы :

P <x>: = PolynomialRing (Rationals ());S <t>: = SplittingField (x ^ 3-x-1);P2 <y>: = Кольцо полиномов (S);p, q, r: = Explode ([r [1]: r в корнях (y ^ 3-y-1)]);Mi: = Матрица ([[1 / p, 1 / q, 1 / r], [1,1,1], [p, q, r]]) ^ (- 1);T <u, v, w>: = Кольцо полиномов (S, 3);v1: = ChangeRing (Mi, T) * Матрица ([[u], [v], [w]]);[p ^ i * v1 [1,1] ^ 3 + q ^ i * v1 [2,1] ^ 3 + r ^ i * v1 [3,1] ^ 3: i в [-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 здесь возникает из дискриминанта определяющего полинома последовательности.

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

Простые числа и делимость [ править ]

Псевдопреступники Перрина [ править ]

Было доказано, что для всех простых чисел p , p делит P ( p ). Однако обратное неверно: для некоторых составных чисел n , n все же может делить P ( n ). Если n обладает этим свойством, оно называется « псевдоперрином ».

Первые несколько псевдопреступлений Перрина:

271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291, 102690901, 130944133, 196075949, 214038533, 517697641, 545670533, 801123451, 855073301, 903136901, 970355431, ... (последовательность A013998 в OEIS )

Вопрос о существовании псевдопримеров Перрина рассматривался самим Перрином, но не было известно, существуют ли они, пока Адамс и Шанкс (1982) не обнаружили наименьшее из них, 271441 = 521 ² ; следующее по величине - 904631 = 7 x 13 x 9941. Их семнадцать меньше миллиарда; ^[3] Джон Грэнтэм доказал ^[4], что существует бесконечно много псевдопростых чисел Перрина.

Адамс и Шэнкс (1982) отметили, что простые числа также удовлетворяют условию P ( -p ) = -1 mod p . Композиты, в которых сохраняются оба свойства, называются «ограниченными псевдоперринами Перрина» (последовательность A018187 в OEIS ). Дополнительные условия могут применяться с использованием шестиэлементной сигнатуры числа n, которое должно быть одной из трех форм (например, OEIS :  A275612 и OEIS :  A275613 ).

Хотя псевдопремы Перрина встречаются редко, они в значительной степени пересекаются с псевдопреступами Ферма . Это контрастирует с антикоррелированными псевдопредставлениями Лукаса . Последнее условие используется для получения популярного, эффективного и более эффективного теста BPSW, который не имеет известных псевдопринципов, а наименьшее из них, как известно, больше 2 ⁶⁴ .

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

Перрин премьер является числом Перрин , который премьер . Первые несколько простых чисел Перрина:

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

Для этих простых чисел Perrin, индекс п из Р ( п ) является

2, 3, 4, 5, 6, 7, 10, 12, 20, 21, 24, 34, 38, 75, 122, 166, 236, 355, 356, 930, 1042, 1214, 1461, 1622, 4430, 5802, 9092, ... (последовательность A112881 в OEIS )

Создание P (n), где n - отрицательное целое число, дает аналогичное свойство относительно простоты: если n отрицательное, то P (n) простое, когда P (n) mod -n = -n - 1. Следующая последовательность представляет P (n) для всех отрицательных целых n:

-1, 1, 2, -3, 4, -2, -1, 5, -7, 6, -1, -6, 12, -13, 7, 5, -18, 25, -20, 2, 23, -43, 45, -22, -21, 66, -88, 67, -1, ... (последовательность A078712 в OEIS )

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

Ссылки [ править ]

• Фюреди, З. (1987). «Число максимальных независимых множеств в связных графах». Журнал теории графов . 11 (4): 463–470. DOI : 10.1002 / jgt.3190110403 .

• Кнут, Дональд Э. (2011). Искусство программирования , Том 4A: Комбинаторные алгоритмы, Часть 1 . Эддисон-Уэсли. ISBN 0201038048.

Дальнейшее чтение [ править ]

• Адамс, Уильям; Шанкс, Дэниел (1982). «Сильные тесты на простоту, которых недостаточно» . Математика вычислений . Американское математическое общество. 39 (159): 255–300. DOI : 10.2307 / 2007637 . JSTOR  2007637 . Руководство по ремонту  0658231 .

• Перрин, Р. (1899). «Запрос 1484». L'Intermédiaire des Mathématiciens . 6 : 76.

• Лукас, Э. (1878). "Теория числовых функций простого периода". Американский журнал математики . Издательство Университета Джона Хопкинса. 1 (3): 197–240. DOI : 10.2307 / 2369311 . JSTOR  2369311 .

Внешние ссылки [ править ]

• Zentrum für Hirnforschung Institut für Medizinische Kybernetik und Artificial Intelligence
• «Лукас Псевдопримес» . MathPages.com .
• «Последовательность Перрина» . MathPages.com .
• Последовательность OEIS A225876 (Составное n, которое делит s (n) +1, где s равно ...) - последовательность, подобная Перрину.
• Тесты на первичность Перрина