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

Последовательность чисел 3,0,2,3,2,5,5,7,10,...

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

В математике числа Перрена представляют собой дважды бесконечную константно-рекурсивную целочисленную последовательность с характеристическим уравнением x ³ = x + 1. Числа Перрена имеют такое же отношение к последовательности Падована , как числа Люка к последовательности Фибоначчи .

Определение

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

${\displaystyle {\begin{aligned}P(0)&=3,\\P(1)&=0,\\P(2)&=2,\\P(n)&=P(n-2)+P(n-3){\mbox{ for }}n>2,\end{aligned}}}$

и наоборот

${\displaystyle P(n)=P(n+3)-P(n+1){\mbox{ for }}n<0.}$

Первые несколько членов в обоих направлениях:

Числа Перрена можно выразить как суммы трех исходных членов

${\displaystyle {\begin{array}{c|c|c}n&P(n)&P(-n)\\\hline 0&P(0)&...\\1&P(1)&P(2)-P(0)\\2&P(2)&-P(2)+P(1)+P(0)\\3&P(1)+P(0)&P(2)-P(1)\\4&P(2)+P(1)&P(1)-P(0)\\5&P(2)+P(1)+P(0)&-P(2)+2P(0)\\6&P(2)+2P(1)+P(0)&2P(2)-P(1)-2P(0)\\7&2P(2)+2P(1)+P(0)&-2P(2)+2P(1)+P(0)\\8&2P(2)+3P(1)+2P(0)&P(2)-2P(1)+P(0)\end{array}}}$

Первые четырнадцать простых чисел Перрина — это

История

В 1876 году последовательность и ее уравнение были впервые упомянуты Эдуардом Люка , который заметил, что индекс n делит член P(n), если n является простым числом. ^[5] В 1899 году Рауль Перрен спросил, есть ли какие-либо контрпримеры к этому свойству. ^[6] Первое число P(n), делимое на составной индекс n, было найдено только в 1982 году Уильямом Адамсом и Дэниелом Шэнксом . ^[7] Они представили подробное исследование последовательности, продолжение которого появилось четыре года спустя. ^[8]

Характеристики

Микрокосм Перрена: алгоритм времени побега применяется к карте Ньютона всей функции Перрена F(z) вокруг критической точки z = 1,225432 с шириной области просмотра 0,05320. Бассейны притяжения, исходящие из центра, соответствуют бесконечному числу действительных (слева) и комплексных корней (справа) F (z) = 0 .

Последовательность Перрена также удовлетворяет рекуррентному соотношению. Исходя из этого и определяющего рекуррентного соотношения, можно создать бесконечное количество дальнейших соотношений, например: ${\displaystyle P(n)=P(n-1)+P(n-5).}$ ${\displaystyle P(n)=P(n-3)+P(n-4)+P(n-5).}$

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

${\displaystyle {\frac {3-x^{2}}{1-x^{2}-x^{3}}}=\sum _{n=0}^{\infty }P(n)\,x^{n}}$

Последовательность связана с суммами биномиальных коэффициентов соотношением

${\displaystyle P(n)=n\times \sum _{k=\lfloor (n+2)/3\rfloor }^{\lfloor n/2\rfloor }{\binom {k}{n-2k}}/k,}$^[1]

${\displaystyle P(-n)=n\times \sum _{k=0}^{\lfloor n/3\rfloor }(-1)^{n-k}{\binom {n-2k}{k}}/(n-2k).}$

Числа Перрена можно выразить через частичные суммы

${\displaystyle {\begin{aligned}P(n+5)-2&=\sum _{k=0}^{n}P(k)\\P(2n+3)&=\sum _{k=0}^{n}P(2k)\\5-P(4-n)&=\sum _{k=0}^{n}P(-k)\\3-P(1-2n)&=\sum _{k=0}^{n}P(-2k).\end{aligned}}}$

Числа Перрена получаются как целые степени n ≥ 0 матрицы

${\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(n)\\P(n+1)\\P(n+2)\end{pmatrix}},}$

и его обратный

${\displaystyle {\begin{pmatrix}-1&0&1\\1&0&0\\0&1&0\end{pmatrix}}^{n}{\begin{pmatrix}3\\0\\2\end{pmatrix}}={\begin{pmatrix}P(-n)\\P(1-n)\\P(2-n)\end{pmatrix}}.}$

Аналог Перрена тождества Симсона для чисел Фибоначчи задается определителем

${\displaystyle {\begin{vmatrix}P(n+2)&P(n+1)&P(n)\\P(n+1)&P(n)&P(n-1)\\P(n)&P(n-1)&P(n-2)\end{vmatrix}}=-23.}$

Число различных максимальных независимых множеств в n -вершинном циклическом графе подсчитывается с помощью n- го числа Перрена для n ≥ 2. [ ^9]

формула Бине

Функция Перрена расширяет последовательность до действительных чисел.

Решение рекуррентного уравнения можно записать в терминах корней характеристического уравнения . Если три решения представляют собой действительный корень ⁠ ⁠ (с приблизительным значением 1,324718 и известный как пластическое отношение ) и комплексно-сопряженные корни ⁠ ⁠ и ⁠ ⁠ , числа Перрена можно вычислить с помощью формулы Бине , которая также справедлива для отрицательных n . ${\displaystyle P(n)=P(n-2)+P(n-3)}$ ${\displaystyle x^{3}-x-1=0}$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle \gamma }$ ${\displaystyle P(n)=\alpha ^{n}+\beta ^{n}+\gamma ^{n},}$

Полярная форма имеет вид Поскольку формула сводится либо к первому, либо ко второму члену последовательно для больших положительных или отрицательных n , а числа с отрицательными индексами осциллируют. При условии, что α вычисляется с достаточной точностью, эти формулы можно использовать для вычисления чисел Перрена для больших n . ${\displaystyle P(n)=\alpha ^{n}+2\cos(n\,\theta ){\sqrt {\alpha ^{-n}}},}$ ${\displaystyle \theta =\arccos(-{\sqrt {\alpha ^{3}}}/2).}$ ${\displaystyle \lim _{n\to \infty }\alpha ^{-n}=0,}$

Расширение тождества дает важное правило удвоения индекса, посредством которого связываются прямая и обратная части последовательности. ${\displaystyle P^{2}(n)=(\alpha ^{n}+\beta ^{n}+\gamma ^{n})^{2}}$ ${\displaystyle P(2n)=P^{2}(n)-2P(-n),}$

Главный индекспделитП(п)

Если характеристическое уравнение последовательности записать как, то коэффициенты ⁠ ⁠ можно выразить через корни с помощью формул Виета : ${\displaystyle f(x)=x^{3}-\sigma _{1}x^{2}+\sigma _{2}x-\sigma _{3}}$ ${\displaystyle \sigma _{k}}$ ${\displaystyle \alpha ,\beta ,\gamma }$

${\displaystyle {\begin{alignedat}{3}\sigma _{1}&=\alpha +\beta +\gamma &&=0\\\sigma _{2}&=\alpha \beta +\alpha \gamma +\beta \gamma &&=-1\\\sigma _{3}&=\alpha \beta \gamma &&=1.\end{alignedat}}}$

Эти целочисленные функции являются элементарными симметричными многочленами в ${\displaystyle \alpha ,\beta ,\gamma .}$

• Основная теорема о симметричных многочленах утверждает, что каждый симметричный многочлен от комплексных корней монического ⁠ ⁠ ${\displaystyle f}$ может быть представлен как другая полиномиальная функция от целых коэффициентов ⁠ ⁠ ${\displaystyle f.}$
• Аналог теоремы Лукаса для полиномиальных коэффициентов гласит, что если ⁠ ⁠ то делится на простое число ⁠ ⁠ ${\displaystyle {\frac {p!}{i!j!k!}}}$ ${\displaystyle i,j,k<p}$ ${\displaystyle {\binom {p}{i,j,k}}}$ ${\displaystyle p.}$

Даны целые числа a, b, c и n > 0,

${\displaystyle (a+b+c)^{n}=\sum _{i+j+k=n}{\binom {n}{i,j,k}}a^{i}b^{j}c^{k}.}$

Переставим в симметричные одночленные слагаемые, переставляя показатели степеней i, j, k:

${\displaystyle (a+b+c)^{n}-(a^{n}+b^{n}+c^{n})=}$ ${\displaystyle \sum _{\begin{aligned}i\leq j\leq k&<n\\i+j+k&=n\end{aligned}}{\binom {n}{i,j,k}}\sum _{\pi (i,j,k)}a^{i}b^{j}c^{k}.}$

Замените простое число ⁠ ⁠ ${\displaystyle p}$ на степень ⁠ ⁠ ${\displaystyle n}$ и комплексные корни на целые числа ⁠ ⁠ и вычислите представления в терминах для всех симметричных полиномиальных функций. Например, это и сумма степени может быть выражена в коэффициентах ⁠ ⁠ с помощью рекурсивной схемы Ньютона . Из этого следует, что тождество имеет целые члены и обе стороны делятся на простое число ⁠ ⁠ ${\displaystyle \alpha ,\beta ,\gamma }$ ${\displaystyle a,b,c}$ ${\displaystyle \sigma _{1},\sigma _{2},\sigma _{3}}$ ${\displaystyle (\alpha +\beta +\gamma )^{p}}$ ${\displaystyle \sigma _{1}^{p}=0}$ ${\displaystyle \alpha ^{p}+\beta ^{p}+\gamma ^{p}=P(p)}$ ${\displaystyle \sigma _{k}}$ ${\displaystyle p.}$

Чтобы показать, что простое число ⁠ ⁠ ${\displaystyle p}$ делит ⁠ ⁠ ${\displaystyle P(-p)+1}$ в обратной последовательности, характеристическое уравнение должно быть отражено . Тогда корни являются коэффициентами , и применяются те же рассуждения. ${\displaystyle \alpha ^{-1},\beta ^{-1},\gamma ^{-1},}$ ${\displaystyle \sigma _{1}=-1,\sigma _{2}=0,\sigma _{3}=1,}$

Тест Перрина на простоту

Запрос 1484. Любопытное предложение китайского происхождения , которое является предметом запроса 1401 ^[10], предоставило бы, если бы оно было истинным, более практичный критерий, чем теорема Уилсона , для проверки того, является ли заданное число m простым или нет; достаточно было бы вычислить остатки относительно m последовательных членов рекуррентной последовательности
u _n = 3u _n−1 − 2u _n−2 с начальными значениями u ₀ = −1, u ₁ = 0. ^[11]
Я нашел другую рекуррентную последовательность, которая, кажется, обладает тем же свойством; это та, общий член которой
v _n = v _n−2 + v _n−3 с начальными значениями v ₀ = 3, v ₁ = 0, v ₂ = 2. Легко показать, что v _n делится на n, если n простое; Я проверил, вплоть до довольно больших значений n, что в противоположном случае это не так; но было бы интересно узнать, действительно ли это так, особенно потому, что последовательность v _n дает гораздо менее быстро растущие числа, чем последовательность u _n (например, для n = 17 можно найти u _n = 131070, v _n = 119), что приводит к более простым вычислениям, когда n — большое число.
То же самое доказательство, применимое к одной из последовательностей, несомненно, будет относиться и к другой, если указанное свойство верно для обеих: это только вопрос его обнаружения. ^[12]

Последовательность Перрена обладает свойством Ферма : если p — простое число , P(p) ≡ P(1) ≡ 0 (mod p) . Однако обратное неверно: некоторое составное n все еще может делить P(n) . Число с этим свойством называется псевдопростым числом Перрена .

Вопрос о существовании псевдопростых чисел Перрина рассматривался Мало и Джарденом ^[13] , но ни одно из них не было известно, пока Адамс и Шэнкс не нашли наименьшее из них, 271441 = 521 ² (число P(271441) имеет 33150 десятичных цифр). ^[14] Джон Грэнтэм позже доказал, что существует бесконечно много псевдопростых чисел Перрина. ^[15]

Семнадцать псевдопростых чисел Перрена ниже 10 ⁹ — это

271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291, 102690901, 130944133, 196075949, 214038533, 517697641, 5 45670533, 801123451, 855073301, 903136901, 970355431. ^[16]

Адамс и Шэнкс отметили, что простые числа также удовлетворяют сравнению P(−p) ≡ P(−1) ≡ −1 (mod p) . Композиты, для которых выполняются оба свойства, называются ограниченными псевдопростыми числами Перрина. Существует всего девять таких чисел ниже 10 ⁹ . ^{[17] [18] [19]}

Хотя псевдопростые числа Перрена встречаются редко, они пересекаются с псевдопростыми числами Ферма . Из семнадцати приведенных выше чисел четыре также являются ферматианами с основанием 2. Напротив, псевдопростые числа Лукаса антикоррелированы. ^[20] Предположительно, объединение тестов Перрена и Лукаса должно сделать тест на простоту таким же сильным, как надежный тест BPSW , в котором нет известных псевдопростых чисел, — хотя и с более высокими вычислительными затратами.

Псевдокод

Тест простоты числа O(log n) Перрина Адамса и Шэнкса 1982 года . ^[21]

Два целочисленных массива u(3) и v(3) инициализируются наименьшими членами последовательности Перрина с положительными индексами t = 0, 1, 2 в u( ) и отрицательными индексами t = 0,−1,−2 в v( ).

Основной цикл удвоения и сложения , изначально разработанный для работы на карманном калькуляторе HP-41C , вычисляет P(n) mod n и обратное P(−n) mod n за счет шести модульных возведений в квадрат для каждого бита n .

Индексы чисел Перрена удваиваются с использованием тождества P(2t) = P ² (t) − 2P(−t) . Полученные зазоры между P(±2t) и P(±2t ± 2) закрываются применением определяющего соотношения P(t) = P(t − 2) + P(t − 3) .

Начальные значения пусть  int u(0):= 3, u(1):= 0, u(2):= 2 пусть  int v(0):= 3, v(1):=−1, v(2):= 1 Тест нечетного положительного числа n ввод  int n set  int h:= старший бит числа n для k:= h − 1 вплоть до 0  Удвоить индексы  шести чисел Перрена.  для i = 0, 1, 2 темп:= u(i)^2 − 2v(i) (mod n) v(i):= v(i)^2 − 2u(i) (mod n) u(i):= темп конецдля  Скопируйте P(2t + 2) и P(−2t − 2)  в концы массива и используйте  в операторе if ниже. и(3):= и(2) в(3):= в(2)  Перезаписать P(2t ± 2) на P(2t ± 1) темп:= u(2) − u(1) u(2):= u(0) + темп u(0):= темп  Перезаписать P(−2t ± 2) на P(−2t ± 1) темп:= v(0) − v(1) v(0):= v(2) + темп v(2):= темп  если у n установлен бит k , то  увеличьте индексы  обеих троек Перрина на 1.  для i = 0, 1, 2 и(я):= и(я + 1) v(i):= v(i + 1) конец для конец  если конецдля Результат распечатать v(2), v(1), v(0) распечатать u(0), u(1), u(2)

Последовательно P(−n − 1), P(−n), P(−n + 1) и P(n − 1), P(n), P(n + 1) (mod n) .

Если P(−n) = −1 и P(n) = 0 , то n является вероятным простым числом , то есть фактически простым числом или ограниченным псевдопростым числом Перрина.

Шэнкс и др. заметили, что для всех ограниченных псевдопростых чисел, которые они нашли, конечное состояние вышеуказанных шести регистров («сигнатура» n ) равно начальному состоянию 1,−1,3, 3,0,2. ^[22] То же самое происходит с ≈ 1 / 6 всех простых чисел, поэтому два набора не могут быть различены на основании одного только этого теста. ^[23] Для этих случаев они рекомендуют также использовать сестринскую последовательность Нараяны-Лукаса с рекуррентным соотношением A(n) = A(n − 1) + A(n − 3) и начальными значениями

и(0):= 3, и(1):= 1, и(2):= 1v(0):= 3, v(1):= 0, v(2):=−2

Применяется то же правило удвоения, и формулы для заполнения пробелов следующие:

темп:= u(0) + u(1)u(0):= u(2) − темпu(2):= темп темп:= v(2) + v(1)v(2):= v(0) − темпv(0):= темп

Здесь n является вероятным простым числом, если A(−n) = 0 и A(n) = 1 .

Курц и др. не обнаружили перекрытия между нечетными псевдопростыми числами для двух последовательностей ниже 50∙10 ⁹ и предположили, что 2 277 740 968 903 = 10 67 179 ∙ 2134 357 — наименьшее составное число, прошедшее оба теста. ^[24]

Если также использовать рекуррентное соотношение Пелля-Лукаса третьего порядка A(n) = 2A(n − 1) + A(n − 3) , то эта граница увеличится до 4 057 052 ​​731 496 380 171 = 1424263447 ∙ 2848526893. ^[25]

Кроме того, корни правила удвоения-конгруэнтности, отличные от −1 или 3, раскрывают составные числа, такие как нетривиальные квадратные корни из 1 в тесте Миллера-Рабина . ^[26] Это уменьшает количество ограниченных псевдопростых чисел для каждой последовательности примерно на треть и особенно эффективно при обнаружении чисел Кармайкла . ^[27] ${\displaystyle x^{2}-2x\equiv 3=P(0){\pmod {n}}\,}$

Наименее сильно ограниченное псевдопростое число Перрена — 46672291, а две указанные выше границы последовательно расширяются до 173 536 465 910 671 и 79 720 990 309 209 574 421. ^[28]

Примечания

1. Sloane, N. J. A. (ред.). "Последовательность A001608 (последовательность Перрина (или последовательность Ондрея Суча): a(n) = a(n-2) + a(n-3) с a(0) = 3, a(1) = 0, a(2) = 2)". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.
2. Слоан, Н. Дж. А. (ред.). "Последовательность A078712 (Разложение ряда (-3 - 2*x)/(1 + x - x^3) по степеням x)". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.
3. Слоан, Н. Дж. А. (ред.). "Последовательность A112881 (индексы простых чисел Перрина; значения n, такие, что A001608(n) является простым числом)". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.
4. Слоан, Н. Дж. А. (ред.). "Последовательность A074788 (Простые числа в последовательности Перрена b(n+1) = b(n-1) + b(n-2) с начальными значениями b(1)=3, b(2)=0, b(3)=2)". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.
5. Лукас (1878)
6. Перрен (1899)
7. Адамс и Шэнкс (1982)
8. Курц, Шэнкс и Уильямс (1986)
9. Фюреди (1987)
10. Тарри (1898)
11. Sloane, N. J. A. (ред.). "Последовательность A000918 (a(n) = 2^n - 2)". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.
12. Перрен (1899) перевод с французского
13. Мало (1900), Жарден (1966)
14. Адамс и Шэнкс (1982, стр. 255)
15. Грэнтэм (2010), Стефан (2020)
16. Слоан, Н. Дж. А. (ред.). "Последовательность A013998 (неограниченные псевдопростые числа Перрина)". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.
17. Слоан, Н. Дж. А. (ред.). "Последовательность A018187 (ограниченные псевдопростые числа Перрина)". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.
18. Слоан, Н. Дж. А. (ред.). "Последовательность A275612 (ограниченные псевдопростые числа Перрина (определение Адамса и Шэнкса))". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.
19. Слоан, Н. Дж. А. (ред.). "Последовательность A275613 (Ограниченные псевдопростые числа Перрина (определение Грэнтэма).)". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.
20. Ни одно из 2402549 псевдопростых чисел Лукаса-Селфриджа ниже 1015 ^, перечисленных Даной Якобсен (2020), не является также псевдопростым числом Перрина.
21. Адамс и Шэнкс (1982, стр. 265, 269-270)
22. Адамс и Шэнкс (1982, стр. 275), Курц, Шэнкс и Уильямс (1986, стр. 694). Это было позже подтверждено для n < 10 ¹⁴ Стивеном Арно (1991).
23. Сигнатура действительно дает различающую информацию об оставшихся двух типах простых чисел. Например, наименьшее псевдопростое число Q-типа 50 972 694 899 204 437 633, вычисленное Хольгером Стефаном (2019), раскрывается условиями сигнатуры 14a и 14c в работе Адамса и Шэнкса (1982, стр. 257).
24. Курц, Шэнкс и Уильямс (1986, стр. 697)
25. Стефан (2019)
26. Адамс и Шэнкс (1982, стр. 280-283)
27. Реализацию расширенного теста Перрина на языке AC/C++ можно найти в последнем подразделе предыдущей версии этой статьи.
28. Стефан (2019)

Ссылки

• Лукас, Э. (1878). «Теория простых периодических числовых функций». Американский журнал математики (на французском языке). 1 (3). Издательство Университета Джонса Хопкинса: 229–231. дои : 10.2307/2369311 . JSTOR  2369311.
• Тарри, Г. (1898). «Вопрос 1401». L'Intermediaire des Mathématiciens . 5 . Готье-Виллар и др.: 266–267.
• Перрен, Р. [на французском языке] (1899). «Вопрос 1484». L'Intermediaire des Mathématiciens . 6 . Готье-Виллар и дети: 76–77.
• Мало, Э. (1900). «Ответ в 1484 году». L'Intermediaire des Mathématiciens . 7 . Готье-Виллар и др.: 280–282, 312–314.
• Джарден, Дов (1966). Повторяющиеся последовательности (PDF) (2-е изд.). Иерусалим: Ривеон ЛеМатематика. стр. 86–93.
• Адамс, Уильям; Шэнкс, Дэниел (1982). «Сильные тесты на простоту, которые недостаточны». Математика вычислений . 39 (159). Американское математическое общество : 255–300. doi : 10.1090/S0025-5718-1982-0658231-9 . JSTOR  2007637.
• Курц, GC; Шэнкс, Дэниел ; Уильямс, HC (1986). «Быстрые тесты на простоту для чисел, меньших 50∙109». Математика вычислений . 46 (174). Американское математическое общество : 691–701. doi : 10.1090/S0025-5718-1986-0829639-7 . JSTOR  2008007.
• Фюреди, Золтан (1987). «Число максимальных независимых множеств в связных графах». Журнал теории графов . 11 (4): 463–470. doi :10.1002/jgt.3190110403.
• Арно, Стивен (1991). «Заметка о псевдопростых числах Перрина». Математика вычислений . 56 (193). Американское математическое общество : 371–376. Bibcode : 1991MaCom..56..371A. doi : 10.1090/S0025-5718-1991-1052083-9 . JSTOR  2008548.
• Грэнтем, Джон (2010). «Существует бесконечно много псевдопростых чисел Перрина». Журнал теории чисел . 130 (5): 1117–1128. arXiv : 1903.06825 . doi : 10.1016/j.jnt.2009.11.008.
• Якобсен, Дана (2020). "Статистика и таблицы псевдопростых чисел". ntheory.org . Получено 7 марта 2024 г. #LPSP Лукас-Селфридж
• Стефан, Хольгер (2020). «Миллионы псевдопростых чисел Перрена, включая несколько гигантов». arXiv : 2002.03756v1 [math.NA].
• Стефан, Хольгер (2019). Псевдопростые числа Перрена (Исследовательские данные WIAS № 4). Берлин: Институт Вейерштрасса . doi : 10.20347/WIAS.DATA.4 .

Внешние ссылки

• Якобсен, Дана (2016). «Тесты Перрина на простоту».
• Райт, Колин (2015). «Нахождение псевдопростых чисел Перрина».
• «Последовательность Перрена». MathPages.com .
• «Псевдопростые числа Лукаса и Перрена». MathPages.com .
• Хольцбаур, Кристиан (1997). «Псевдопростые числа Перрина».
• Турк, Ричард (2014). «Доска Перрина».