Число Перрина - Perrin number
В математика, то Числа Перрина определены отношение повторения
- п(п) = п(п − 2) + п(п − 3) за п > 2,
с начальными значениями
- п(0) = 3, п(1) = 0, п(2) = 2.
Последовательность чисел Перрина начинается с
Количество разных максимальные независимые множества в п-вертекс график цикла подсчитывается пй номер Перрина для п > 1.[1][страница нужна ]
История
Эта последовательность неявно упоминалась Эдуард Лукас (1876 г.). В 1899 году эта же последовательность была прямо упомянута Франсуа Оливье Раулем Перреном.[2][страница нужна ] Наиболее подробно эта последовательность была дана Адамсом и Шанксом (1982).
Характеристики
Производящая функция
В производящая функция последовательности Перрина
Формула матрицы
Формула типа Бине
Порядковые номера Перрена можно записать в терминах степеней корней уравнения
Это уравнение имеет 3 корня; один настоящий корень п (известный как пластиковый номер ) и два комплексно сопряженных корня q и р. Учитывая эти три корня, аналог последовательности Перрина Последовательность Лукаса Формула Бине:
Поскольку величины комплексных корней q и р оба меньше единицы, степени этих корней стремятся к 0 при больших п. Для больших п формула сводится к
Эту формулу можно использовать для быстрого вычисления значений последовательности Перрина для больших n. Отношение последовательных членов в последовательности Перрина приближается к п, он же пластиковый номер, который имеет значение примерно 1,324718. Эта константа имеет такое же отношение к последовательности Перрина, как и Золотое сечение делает для Последовательность Лукаса. Подобные связи существуют и между п и Падованская последовательность, между Золотое сечение и числами Фибоначчи, а между соотношение серебра и Числа Пелла.
Формула умножения
Из формулы Бине можно получить формулу для грамм(кн) с точки зрения грамм(п−1), грамм(п) и грамм(п+1); мы знаем
что дает нам три линейных уравнения с коэффициентами над поле расщепления из ; инвертируя матрицу, мы можем решить для а затем мы можем поднять их до k-я степень и вычислите сумму.
Пример магма код:
P: = PolynomialRing (Rationals ()); S : = SplittingField (x ^ 3-x-1); P2 : = PolynomialRing (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 : = 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 в [-1..1]];
в результате, если у нас есть , тогда
Число 23 здесь возникает из дискриминанта определяющего полинома последовательности.
Это позволяет вычислить n-е число Перрина с помощью целочисленной арифметики в умножается.
Простые числа и делимость
Псевдопреступники Перрина
Доказано, что для всех простых чисел п, п разделяет п(п). Однако обратное неверно: для некоторых составные числа п, п все еще может разделить п(п). Если п обладает этим свойством, он называется «Перрин псевдопремия ".
Первые несколько псевдопреступлений Перрина:
- 271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291, 102690901, 130944133, 196075949, 214038533, 517697641, 545670533, 801123451, 855073301, 903136901, 970355431, ... (последовательность A013998 в OEIS )
Вопрос о существовании псевдопримесей Перрина рассматривался самим Перрином, но не было известно, существуют ли они, пока Адамс и Шанкс (1982) не обнаружили наименьшее из них, 271441 = 521.2; следующее по величине - 904631 = 7 x 13 x 9941. Их семнадцать меньше миллиарда;[3] Джон Грэнтэм доказал[4] что существует бесконечно много псевдопространств Перрина.
Адамс и Шанкс (1982) отметили, что простые числа также удовлетворяют условию, что п(-п) = -1 мод п. Композиты, в которых сохраняются оба свойства, называются «ограниченными псевдоперринами Перрина» (последовательность A018187 в OEIS ). Дополнительные условия могут быть применены с использованием шестиэлементной сигнатуры п который должен быть одной из трех форм (например, OEIS: A275612 и OEIS: A275613).
Хотя псевдопремы Перрина встречаются редко, они существенно пересекаются с Псевдопримеси Ферма. Это контрастирует с Лукас псевдопреступник которые антикоррелированы. Последнее условие используется для получения популярных, эффективных и более эффективных BPSW тест который не имеет известных псевдопринципов, а наименьшее из них, как известно, больше 264.
Простые числа Перрина
А Перрин Прайм это число Перрина, которое основной. Первые несколько простых чисел Перрина:
- 2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977, 187278659180417234321, 66241160488780141071579864797, ... (последовательность A074788 в OEIS )
Для этих простых чисел Перрина индекс п из п(п) является
- 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)
- ^ Кнут (2011)
- ^ (последовательность A013998 в OEIS )
- ^ Джон Грэнтэм (2010). «Существует бесконечно много псевдопреступлений Перрина» (PDF). Журнал теории чисел. 130 (5): 1117–1128. Дои:10.1016 / j.jnt.2009.11.008.
Рекомендации
- Фюреди, З. (1987). «Число максимальных независимых множеств в связных графах». Журнал теории графов. 11 (4): 463–470. Дои:10.1002 / jgt.3190110403.
- Кнут, Дональд Э. (2011). Искусство программирования, Том 4A: Комбинаторные алгоритмы, часть 1. Эддисон-Уэсли. ISBN 0201038048.
дальнейшее чтение
- Адамс, Уильям; Шанкс, Дэниел (1982). «Сильные тесты на простоту, которых недостаточно». Математика вычислений. Американское математическое общество. 39 (159): 255–300. Дои:10.2307/2007637. JSTOR 2007637. МИСТЕР 0658231.
- Перрин, Р. (1899). «Запрос 1484». L'Intermédiaire des Mathématiciens. 6: 76.
- Лукас, Э. (1878). "Теория числовых функций простого периода". Американский журнал математики. Издательство Университета Джона Хопкинса. 1 (3): 197–240. Дои: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 - это ...) - Перрино-подобная последовательность
- Тесты на первичность Перрина