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

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

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

Определение

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

${\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}}$

и наоборот

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

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

н	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
П (п)	3	0	2	3	2	5	5	7	10	12	17	22	29	39	51	68	90	119	...
P(−n)	...	−1	1	2	−3	4	−2	−1	5	−7	6	−1	−6	12	−13	7	5	−18	...

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

${\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}}$

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

н	2	3	4	5	6	7	10	12	20	21	24	34	38	75	...
П (п)	2	3	2	5	5	7	17	29	277	367	853	14197	43721	1442968193	...

История

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

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

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

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

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

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

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

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

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

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

${\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}}$

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

${\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}},$

и его инверсия

${\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}}.$

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

${\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 .

Формула Бине

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

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

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

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

Простой индекс p делит P (p)

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

${\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}}$

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

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

Учитывая целые числа a, b, c и n > 0,

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

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

$(a+b+c)^{n}-(a^{n}+b^{n}+c^{n})=$ $\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}.$

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

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

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

Запрос 1484. Любопытное предложение китайского происхождения , являющееся предметом запроса 1401. предоставил бы, если это правда, более практичный критерий, чем теорема Вильсона, для проверки того, является ли данное число m простым или нет; достаточно было бы вычислить остатки по m последовательных членов рекуррентной последовательности
u _n = 3u _n−1 − 2u _n−2 с начальными значениями u ₀ = −1, u ₁ = 0.
Я нашел другую повторяющуюся последовательность, которая, по-видимому, обладает тем же свойством; это тот, общий термин которого
v _n = v _n−2 + v _n−3 с начальными значениями v ₀ = 3, v ₁ = 0, v ₂ = 2. Легко показать, что v _n делится на n, если n — простое число; Я проверил, вплоть до довольно высоких значений n, что в противоположном случае это не так; но было бы интересно узнать, так ли это на самом деле, тем более что последовательность v _n дает гораздо менее быстро растущие числа, чем последовательность un ₍ при n = 17, например, можно найти un ₌ 131070, v _n = 119 ), что приводит к упрощению вычислений, когда n — большое число.
Одно и то же доказательство, применимое к одной из последовательностей, несомненно, будет иметь отношение и к другой, если заявленное свойство верно для обеих: дело лишь в его открытии.

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

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

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

271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291, 102690901, 130944133, 196075949, 214038533, 517697641, 545670533, 801123451, 855073301, 903136901, 970355431.

Адамс и Шэнкс отметили, что простые числа также удовлетворяют сравнению P(−p) ≡ P(−1) ≡ −1 (mod p) . Композиты, для которых выполняются оба свойства, называются ограниченными псевдопростыми числами Перрена. всего девять. Таких чисел меньше 10 ⁹ .

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

Псевдокод

Тест Адамса и Шэнкса на простоту O(log n) Перрина 1982 года.

Два целочисленных массива 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 ² (т) − 2P(−t) . Возникающие в результате разрывы между P(±2t) и P(±2t ± 2) закрываются применением определяющего соотношения P(t) = P(t - 2) + P(t - 3) .

Initial values
let int u(0):= 3, u(1):= 0, u(2):= 2
let int v(0):= 3, v(1):=−1, v(2):= 1
     
Test odd positive number n
input int n
     
set int h:= most significant bit of n
     
for k:= h − 1 downto 0
     
  Double the indices of
  the six Perrin numbers.
  for i = 0, 1, 2
    temp:= u(i)^2 − 2v(i) (mod n)
    v(i):= v(i)^2 − 2u(i) (mod n)
    u(i):= temp
  endfor
     
  Copy P(2t + 2) and P(−2t − 2)
  to the array ends and use
  in the if-statement below.
  u(3):= u(2)
  v(3):= v(2)
     
  Overwrite P(2t ± 2) with P(2t ± 1)
  temp:= u(2) − u(1)
  u(2):= u(0) + temp
  u(0):= temp
     
  Overwrite P(−2t ± 2) with P(−2t ± 1)
  temp:= v(0) − v(1)
  v(0):= v(2) + temp
  v(2):= temp
     
  if n has bit k set then
    Increase the indices of
    both Perrin triples by 1.
    for i = 0, 1, 2
      u(i):= u(i + 1)
      v(i):= v(i + 1)
    endfor
  endif
     
endfor
     
Result
print v(2), v(1), v(0)
print 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. То же самое происходит с ≈ 1/6 всех простых чисел , поэтому два набора нельзя различить только на основании этого теста. В этих случаях они рекомендуют также использовать сестринскую последовательность Нараяны-Лукаса с рекуррентным соотношением A(n) = A(n - 1) + A(n - 3) и начальными значениями.

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

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

temp:= u(0) + u(1)
u(0):= u(2) − temp
u(2):= temp
     
temp:= v(2) + v(1)
v(2):= v(0) − temp
v(0):= temp

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

Курц и др. не обнаружил перекрытия между нечетными псевдопростыми числами для двух последовательностей ниже 50∙10. ⁹ и предположил, что 2 277 740 968 903 = 1067179 ∙ 2134357 — это наименьшее составное число, которое может пройти оба теста.

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

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

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

Ссылки

• Лукас, Э. (1878). «Теория просто периодических числовых функций» . Американский журнал математики (на французском языке). 1 (3). Издательство Университета Джонса Хопкинса: 229–231. дои : 10.2307/2369311 . JSTOR   2369311 .
• Тарри, Г. (1898). «Вопрос 1401». Посредник математиков . 5 . Готье-Виллар и сыновья: 266–267.
• Перрен, Р. [на французском языке] (1899). «Выпуск 1484» . Посредник математиков . 6 . Готье-Виллар и сыновья: 76–77.
• Мало, Э. (1900). «Ответ на номер 1484». Посредник математиков . 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; Шанкс, Дэниел ; Уильямс, ХК (1986). «Быстрые тесты на простоту чисел меньше 50∙10 ⁹ « . Математика вычислений . 46 (174). Американское математическое общество : 691–701. doi : 10.1090/S0025-5718-1986-0829639-7 . JSTOR   2008007 .
• Фюреди, Золтан (1987). «Количество максимальных независимых множеств в связных графах». Журнал теории графов . 11 (4): 463–470. дои : 10.1002/jgt.3190110403 .
• Арно, Стивен (1991). «Заметка о псевдопростых числах Перрена» . Математика вычислений . 56 (193). Американское математическое общество : 371–376. Бибкод : 1991MaCom..56..371A . дои : 10.1090/S0025-5718-1991-1052083-9 . JSTOR   2008548 .
• Грэнтэм, Джон (2010). «Существует бесконечно много псевдопростых чисел Перрена». Журнал теории чисел . 130 (5): 1117–1128. arXiv : 1903.06825 . дои : 10.1016/j.jnt.2009.11.008 .
• Якобсен, Дана (2020). «Псевдопростые статистики и таблицы» . ntheory.org . Проверено 7 марта 2024 г. #ЛПСП Лукас-Селфридж
• Стефан, Хольгер (2020). «Миллионы псевдопростых чисел Перрена, включая несколько гигантов». arXiv : 2002.03756v1 [ math.NA ].
• Стефан, Хольгер (2019). Псевдопростые числа Перрена (данные исследования WIAS № 4). Берлин: Институт Вейерштрасса . дои : 10.20347/WIAS.DATA.4 .

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

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