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

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

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 История
• 2 Свойства
  • 2.1 Производящая функция
  • 2.2 Матричная формула
  • 2.3 Формула типа Бине
  • 2.4 Формула умножения
• 3 Простые числа и делимость
  • 3.1 Псевдопримеры Перрина
  • 3.2 Простые числа Перрина
• 4 Примечания
• 5 Ссылки
• 6 Дополнительная литература
• 7 Внешние ссылки

Эта последовательность была косвенно упомянута Эдуардом Лукасом (1876 г.). В 1899 г. ту же последовательность явно упомянул Франсуа Оли vier Рауль Перрен. Наиболее подробно эта последовательность была дана Адамсом и Шанксом (1982).

Производящая функция

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

$G\; (P\; (n);\; x)\; =\; 3\; -\; х\; 2\; 1\; -\; х\; 2\; -\; х\; 3.\; \{\backslash \; displaystyle\; G\; (P\; (n);\; x)\; =\; \{\backslash \; frac\; \{3-x\; ^\; \{2\}\}\; \{1-x\; ^\; \{2\}\; -x\; ^\; \{3\}\}\}.\}$

Формула матрицы

$(0\; 1\; 0\; 0\; 0\; 1\; 1\; 1\; 0)\; n\; (3\; 0\; 2)\; =\; (P\; (n)\; P\; (n\; +\; 1)\; P\; (n\; +\; 2))\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{pmatrix\}\; 0\; 1\; 0\; \backslash \backslash \; 0\; 0\; 1\; \backslash \backslash \; 1\; 1\; 0\; \backslash \; end\; \{pmatrix\}\}\; ^\; \{n\}\; \{\backslash \; begin\; \{pmatrix\}\; 3\; \backslash \backslash \; 0\; \backslash \backslash \; 2\; \backslash \; end\; \{pmatrix\}\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; P\; \backslash \; left\; (n\; \backslash \; right)\; \backslash \backslash \; P\; \backslash \; left\; (n\; +\; 1\; \backslash \; right)\; \backslash \backslash \; P\; \backslash \; left\; (n\; +\; 2\; \backslash \; right)\; \backslash \; end\; \{pmatrix\}\}\}$

Формула типа Бине

Спираль из равносторонних треугольников с длинами сторон, которые соответствуют последовательности Перрина.

Порядковые номера Перрина можно записать в терминах степеней корней уравнения

$x\; 3\; -\; x\; -\; 1\; =\; 0.\; \{\backslash \; displaystyle\; x\; ^\; \{3\}\; -x-1\; =\; 0.\}$

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

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

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

$P\; (n)\; \approx \; pn\; \{\backslash \; displaystyle\; P\; \backslash \; left\; (n\; \backslash \; right)\; \backslash \; приблизительно\; \{p\; ^\; \{n\}\}\}$

Эту формулу можно использовать для быстрого вычисления значений последовательность Перрина для больших n. Отношение последовательных членов в последовательности Перрина приближается к p, также известному как пластическое число, которое имеет значение приблизительно 1,324718. Эта константа имеет такое же отношение к последовательности Перрина, как золотое сечение к последовательности Лукаса. Аналогичные связи существуют также между p и последовательностью Падована, между золотым сечением и числами Фибоначчи, а также между серебряным соотношением и числами Пелла.

Формула умножения

Из формулы Бине мы можем получить формулу для G (kn) в терминах G (n − 1), G (n) и G (n + 1); мы знаем

$G\; (n\; -\; 1)\; =\; p\; -\; 1\; pn\; +\; q\; -\; 1\; qn\; +\; r\; -\; 1\; rn\; G\; (n)\; =\; pn\; +\; qn\; +\; rn\; G\; (n\; +\; 1)\; =\; ppn\; +\; qqn\; +\; rrn\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{matrix\}\; G\; (n-1)\; =\; p\; ^\; \{-\; 1\}\; p\; ^\; \{n\}\; +\; q\; ^\; \{-\; 1\}\; q\; ^\; \{n\}\; +\; r\; ^\; \{-\; 1\}\; r\; ^\; \{n\}\; \backslash \backslash \; G\; (n)\; =\; p\; ^\; \{n\}\; +\; q\; ^\; \{n\}\; +\; r\; ^\; \{n\}\; \backslash \backslash \; G\; (n\; +\; 1)\; =\; pp\; ^\; \{n\}\; +\; qq\; ^\; \{n\}\; +\; rr\; ^\; \{\; n\}\; \backslash \; end\; \{matrix\}\}\}$

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

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

P: = PolynomialRing (Rationals ()); S : = Поле разделения (x ^ 3-x-1); P2 : = полиномиальное кольцо (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 : = кольцо полиномов (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]] ;

с результатом, что, если мы имеем $u\; =\; G\; (n\; -\; 1),\; v\; =\; G\; (n),\; w\; =\; G\; (n\; +\; 1)\; \{\backslash \; displaystyle\; u\; =\; G\; (n-\; 1),\; v\; =\; G\; (n),\; w\; =\; G\; (n\; +\; 1)\}$, тогда

$23 G (2 n - 1) = 4 u 2 + 3 v 2 + 9 w 2 + 18 uv - 12 uw - 4 vw 23 G (2 n) = - 6 u 2 + 7 v 2 - 2 w 2 - 4 uv + 18 uw + 6 vw 23 G (2 n + 1) = 9 u 2 + v 2 + 3 w 2 + 6 uv - 4 uw + 14 vw 23 G (3 n - 1) = (- 4 u 3 + 2 v 3 - w 3 + 9 (uv 2 + vw 2 + wu 2) + 3 v 2 w + 6 uvw) 23 G (3 n) = (3 u 3 + 2 v 3 + 3 w 3 - 3 (uv 2 + uw 2 + vw 2 + vu 2) + 6 v 2 w + 18 uvw) 23 G (3 n + 1) = (v 3 - w 3 + 6 uv 2 + 9 uw 2 + 6 vw 2 + 9 vu 2 - 3 wu 2 + 6 wv 2 - 6 uvw) {\ displaystyle {\ begin { матрица} 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-е число Перрина с использованием целочисленной арифметики в умножении $O\; (log\; \; n)\; \{\backslash \; displaystyle\; O\; (\backslash \; log\; n)\}$.

Псевдопростые числа Перрина

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

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

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

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

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

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

Простые числа Перрина

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

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

Для этих простых чисел Перрина индекс n для P (n) равен

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 )

• Füredi, Z. (1987). «Число максимальных независимых множеств в связных графах». Journal of Graph Theory. 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. MR 0658231.

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

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

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