Число Перрина - Perrin number

В математика, то Числа Перрина определены отношение повторения

п(п) = п(п − 2) + п(п − 3) за п > 2,

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

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

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

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

Количество разных максимальные независимые множества в п-вертекс график цикла подсчитывается пй номер Перрина для п > 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 ). Дополнительные условия могут быть применены с использованием шестиэлементной сигнатуры п который должен быть одной из трех форм (например, OEISA275612 и OEISA275613).

Хотя псевдопремы Перрина встречаются редко, они существенно пересекаются с Псевдопримеси Ферма. Это контрастирует с Лукас псевдопреступник которые антикоррелированы. Последнее условие используется для получения популярных, эффективных и более эффективных 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 )

Примечания

  1. ^ Фюреди (1987)
  2. ^ Кнут (2011)
  3. ^ (последовательность A013998 в OEIS )
  4. ^ Джон Грэнтэм (2010). «Существует бесконечно много псевдопреступлений Перрина» (PDF). Журнал теории чисел. 130 (5): 1117–1128. Дои:10.1016 / j.jnt.2009.11.008.

Рекомендации

дальнейшее чтение

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

внешняя ссылка