В математике числа Перрина определяются рекуррентным соотношением
- P ( n ) = P ( n - 2) + P ( n - 3) для n > 2 ,
с начальными значениями
- P (0) = 3, P (1) = 0, P (2) = 2 .
Последовательность чисел Перрина начинается с
Количество различных максимальных независимых множеств в графе циклов с n вершинами считается n- м числом Перрина для n > 1 . [1] [ необходима страница ]
История [ править ]
Эта последовательность неявно упоминается Эдуардом Лукасом (1876 г.). В 1899 году эта же последовательность была прямо упомянута Франсуа Оливье Раулем Перреном. [2] [ необходима страница ] Наиболее подробное описание этой последовательности было дано Адамсом и Шанксом (1982).
Свойства [ править ]
Функция генерации [ править ]
Производящая функция последовательности Perrin является
Формула матрицы [ править ]
Формула Бине [ править ]
Порядковые номера Перрина можно записать в терминах степеней корней уравнения
Это уравнение имеет 3 корня; один действительный корень p (известный как пластическое число ) и два комплексно сопряженных корня q и r . Учитывая эти три корня, аналог последовательности Перрина формулы Бине последовательности Люка имеет вид
Поскольку величины комплексных корней q и r меньше 1, степени этих корней приближаются к 0 при больших n . Для больших n формула сводится к
Эту формулу можно использовать для быстрого вычисления значений последовательности Перрина для больших n. Отношение последовательных членов в последовательности Перрина приближается к p , или пластическому числу , которое имеет значение примерно 1,324718. Эта константа имеет такое же отношение к последовательности Перрина, как золотое сечение к последовательности Лукаса . Подобные связи существуют также между p и последовательностью Падована , между золотым сечением и числами Фибоначчи, а также между серебряным соотношением и числами Пелла .
Формула умножения [ править ]
Из формулы Бине мы можем получить формулу для G ( kn ) в терминах G ( n −1), G ( n ) и G ( n +1); мы знаем
что дает нам три линейных уравнений с коэффициентами над полем разложения в ; путем инвертирования матрицы, которую мы можем найти, а затем мы можем возвести их в k- ю степень и вычислить сумму.
Пример кода магмы :
P <x>: = PolynomialRing (Rationals ());S <t>: = Поле разделения (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]] ;
в результате, если мы имеем , то
Число 23 здесь возникает из дискриминанта определяющего полинома последовательности.
Это позволяет вычислить 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 2 ; следующее по величине - 904631 = 7 x 13 x 9941. Их семнадцать меньше миллиарда; [3] Джон Грэнтэм доказал [4], что существует бесконечно много псевдопростых чисел Перрина.
Адамс и Шенкс (1982) отметили, что простые числа также удовлетворяют условию P ( -p ) = -1 mod p . Композиты, в которых сохраняются оба свойства, называются «ограниченными псевдоперринами Перрина» (последовательность A018187 в OEIS ). Дополнительные условия могут применяться с использованием шестиэлементной сигнатуры n, которая должна быть одной из трех форм (например, OEIS : A275612 и OEIS : A275613 ).
Хотя псевдопремы Перрина встречаются редко, они в значительной степени пересекаются с псевдоприемниками Ферма . Это контрастирует с антикоррелированными псевдопредставлениями Лукаса . Последнее условие используется для получения популярного, эффективного и более эффективного теста BPSW, который не имеет известных псевдопринципов, а наименьшее из них, как известно, больше 2 64 .
Простые числа Перрина [ править ]
Перрин премьер является числом Перрин , который премьер . Первые несколько простых чисел Перрина:
- 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 )
Заметки [ править ]
- ^ Furedi (1987)
- ^ Кнут (2011)
- ^ (последовательность A013998 в OEIS )
- ^ Джон Грэнтэм (2010). «Существует бесконечно много псевдопреступников Перрина» (PDF) . Журнал теории чисел . 130 (5): 1117–1128. arXiv : 1903.06825 . DOI : 10.1016 / j.jnt.2009.11.008 .
Ссылки [ править ]
- Фюреди, З. (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 равно ...) - последовательность, подобная перрину.
- Тесты на первичность Перрина