Последовательность Лукаса

Не путать с последовательностью чисел Люка , которая представляет собой особую последовательность Люка.

В математике последовательности Люка $U_{n}(P,Q)$ и $V_{n}(P,Q)$ — это определенные константно-рекурсивные целочисленные последовательности , удовлетворяющие рекуррентному соотношению

$x_{n}=P\cdot x_{n-1}-Q\cdot x_{n-2}$

где $P$ и $Q$ являются фиксированными целыми числами . Любая последовательность, удовлетворяющая этому рекуррентному соотношению, может быть представлена ​​как линейная комбинация последовательностей Люка. $U_{n}(P,Q)$ и $V_{n}(P,Q).$

В более общем смысле, последовательности Лукаса $U_{n}(P,Q)$ и $V_{n}(P,Q)$ представляют последовательности полиномов в $P$ и $Q$ с целыми коэффициентами .

Известные примеры последовательностей Люка включают числа Фибоначчи , числа Мерсенна , числа Пелла , числа Люка , числа Якобсталя и надмножество чисел Ферма (см. ниже). Последовательности Лукаса названы в честь французского математика Эдуарда Люка .

Рекуррентные отношения

Даны два целочисленных параметра $P$ и $Q$, последовательности Люка первого рода $U_{n}(P,Q)$ и второго рода $V_{n}(P,Q)$ определяются рекуррентными соотношениями :

${\begin{aligned}U_{0}(P,Q)&=0,\\U_{1}(P,Q)&=1,\\U_{n}(P,Q)&=P\cdot U_{n-1}(P,Q)-Q\cdot U_{n-2}(P,Q){\mbox{ for }}n>1,\end{aligned}}$

и

${\begin{aligned}V_{0}(P,Q)&=2,\\V_{1}(P,Q)&=P,\\V_{n}(P,Q)&=P\cdot V_{n-1}(P,Q)-Q\cdot V_{n-2}(P,Q){\mbox{ for }}n>1.\end{aligned}}$

Нетрудно показать, что для $n>0$,

${\begin{aligned}U_{n}(P,Q)&={\frac {P\cdot U_{n-1}(P,Q)+V_{n-1}(P,Q)}{2}},\\V_{n}(P,Q)&={\frac {(P^{2}-4Q)\cdot U_{n-1}(P,Q)+P\cdot V_{n-1}(P,Q)}{2}}.\end{aligned}}$

Вышеупомянутые отношения можно записать в матричной форме следующим образом:

${\begin{bmatrix}U_{n}(P,Q)\\U_{n+1}(P,Q)\end{bmatrix}}={\begin{bmatrix}0&1\\-Q&P\end{bmatrix}}\cdot {\begin{bmatrix}U_{n-1}(P,Q)\\U_{n}(P,Q)\end{bmatrix}},$

${\begin{bmatrix}V_{n}(P,Q)\\V_{n+1}(P,Q)\end{bmatrix}}={\begin{bmatrix}0&1\\-Q&P\end{bmatrix}}\cdot {\begin{bmatrix}V_{n-1}(P,Q)\\V_{n}(P,Q)\end{bmatrix}},$

${\begin{bmatrix}U_{n}(P,Q)\\V_{n}(P,Q)\end{bmatrix}}={\begin{bmatrix}P/2&1/2\\(P^{2}-4Q)/2&P/2\end{bmatrix}}\cdot {\begin{bmatrix}U_{n-1}(P,Q)\\V_{n-1}(P,Q)\end{bmatrix}}.$

Примеры

Начальные члены последовательностей Лукаса $U_{n}(P,Q)$ и $V_{n}(P,Q)$ приведены в таблице:

${\begin{array}{r|l|l}n&U_{n}(P,Q)&V_{n}(P,Q)\\\hline 0&0&2\\1&1&P\\2&P&{P}^{2}-2Q\\3&{P}^{2}-Q&{P}^{3}-3PQ\\4&{P}^{3}-2PQ&{P}^{4}-4{P}^{2}Q+2{Q}^{2}\\5&{P}^{4}-3{P}^{2}Q+{Q}^{2}&{P}^{5}-5{P}^{3}Q+5P{Q}^{2}\\6&{P}^{5}-4{P}^{3}Q+3P{Q}^{2}&{P}^{6}-6{P}^{4}Q+9{P}^{2}{Q}^{2}-2{Q}^{3}\end{array}}$

Явные выражения

Характеристическое уравнение рекуррентного соотношения для последовательностей Люка $U_{n}(P,Q)$ и $V_{n}(P,Q)$ является:

$x^{2}-Px+Q=0\,$

Он имеет дискриминант $D=P^{2}-4Q$ и корни :

$a={\frac {P+{\sqrt {D}}}{2}}\quad {\text{and}}\quad b={\frac {P-{\sqrt {D}}}{2}}.\,$

Таким образом:

$a+b=P\,,$

$ab={\frac {1}{4}}(P^{2}-D)=Q\,,$

$a-b={\sqrt {D}}\,.$

Обратите внимание, что последовательность $a^{n}$ и последовательность $b^{n}$ также удовлетворяют рекуррентному соотношению. Однако это могут быть не целочисленные последовательности.

Различные корни

Когда $D\neq 0$, a и b различны, и можно быстро убедиться, что

$a^{n}={\frac {V_{n}+U_{n}{\sqrt {D}}}{2}}$

$b^{n}={\frac {V_{n}-U_{n}{\sqrt {D}}}{2}}.$

Отсюда следует, что члены последовательностей Люка можно выразить через a и b следующим образом:

$U_{n}={\frac {a^{n}-b^{n}}{a-b}}={\frac {a^{n}-b^{n}}{\sqrt {D}}}$

$V_{n}=a^{n}+b^{n}\,$

Повторный корень

Дело $D=0$ происходит именно тогда, когда $P=2S{\text{ and }}Q=S^{2}$ для некоторого целого числа S так, что $a=b=S$. В этом случае легко найти, что

$U_{n}(P,Q)=U_{n}(2S,S^{2})=nS^{n-1}\,$

$V_{n}(P,Q)=V_{n}(2S,S^{2})=2S^{n}.\,$

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

Генерирующие функции

Обычные производящие функции :

$\sum _{n\geq 0}U_{n}(P,Q)z^{n}={\frac {z}{1-Pz+Qz^{2}}};$

$\sum _{n\geq 0}V_{n}(P,Q)z^{n}={\frac {2-Pz}{1-Pz+Qz^{2}}}.$

Уравнения Пелла

Когда $Q=\pm 1$, последовательности Лукаса $U_{n}(P,Q)$ и $V_{n}(P,Q)$ удовлетворяют некоторым уравнениям Пелля :

$V_{n}(P,1)^{2}-D\cdot U_{n}(P,1)^{2}=4,$

$V_{2n}(P,-1)^{2}-D\cdot U_{2n}(P,-1)^{2}=4,$

$V_{2n+1}(P,-1)^{2}-D\cdot U_{2n+1}(P,-1)^{2}=-4.$

Отношения между последовательностями с разными параметрами

• Для любого числа c последовательности $U_{n}(P',Q')$ и $V_{n}(P',Q')$ с

$P'=P+2c$

$Q'=cP+Q+c^{2}$

иметь тот же дискриминант, что и $U_{n}(P,Q)$ и $V_{n}(P,Q)$:

$P'^{2}-4Q'=(P+2c)^{2}-4(cP+Q+c^{2})=P^{2}-4Q=D.$

• Для любого числа c мы также имеем

$U_{n}(cP,c^{2}Q)=c^{n-1}\cdot U_{n}(P,Q),$

$V_{n}(cP,c^{2}Q)=c^{n}\cdot V_{n}(P,Q).$

Прочие отношения

Члены последовательностей Люка удовлетворяют отношениям, которые являются обобщениями отношений между числами Фибоначчи. $F_{n}=U_{n}(1,-1)$ и числа Лукаса $L_{n}=V_{n}(1,-1)$. Например:

${\begin{array}{r|l}{\text{General case}}&(P,Q)=(1,-1)\\\hline (P^{2}-4Q)U_{n}={V_{n+1}-QV_{n-1}}=2V_{n+1}-PV_{n}&5F_{n}={L_{n+1}+L_{n-1}}=2L_{n+1}-L_{n}\\V_{n}=U_{n+1}-QU_{n-1}=2U_{n+1}-PU_{n}&L_{n}=F_{n+1}+F_{n-1}=2F_{n+1}-F_{n}\\U_{2n}=U_{n}V_{n}&F_{2n}=F_{n}L_{n}\\V_{2n}=V_{n}^{2}-2Q^{n}&L_{2n}=L_{n}^{2}-2(-1)^{n}\\U_{m+n}=U_{n}U_{m+1}-QU_{m}U_{n-1}={\frac {U_{m}V_{n}+U_{n}V_{m}}{2}}&F_{m+n}=F_{n}F_{m+1}+F_{m}F_{n-1}={\frac {F_{m}L_{n}+F_{n}L_{m}}{2}}\\V_{m+n}=V_{m}V_{n}-Q^{n}V_{m-n}=DU_{m}U_{n}+Q^{n}V_{m-n}&L_{m+n}=L_{m}L_{n}-(-1)^{n}L_{m-n}=5F_{m}F_{n}+(-1)^{n}L_{m-n}\\V_{n}^{2}-DU_{n}^{2}=4Q^{n}&L_{n}^{2}-5F_{n}^{2}=4(-1)^{n}\\U_{n}^{2}-U_{n-1}U_{n+1}=Q^{n-1}&F_{n}^{2}-F_{n-1}F_{n+1}=(-1)^{n-1}\\V_{n}^{2}-V_{n-1}V_{n+1}=DQ^{n-1}&L_{n}^{2}-L_{n-1}L_{n+1}=5(-1)^{n-1}\\DU_{n}=V_{n+1}-QV_{n-1}&F_{n}={\frac {L_{n+1}+L_{n-1}}{5}}\\V_{m+n}={\frac {V_{m}V_{n}+DU_{m}U_{n}}{2}}&L_{m+n}={\frac {L_{m}L_{n}+5F_{m}F_{n}}{2}}\\U_{m+n}=U_{m}V_{n}-Q^{n}U_{m-n}&F_{n+m}=F_{m}L_{n}-(-1)^{n}F_{m-n}\\2^{n-1}U_{n}={n \choose 1}P^{n-1}+{n \choose 3}P^{n-3}D+\cdots &2^{n-1}F_{n}={n \choose 1}+5{n \choose 3}+\cdots \\2^{n-1}V_{n}=P^{n}+{n \choose 2}P^{n-2}D+{n \choose 4}P^{n-4}D^{2}+\cdots &2^{n-1}L_{n}=1+5{n \choose 2}+5^{2}{n \choose 4}+\cdots \end{array}}$

Свойства делимости

Среди последствий то, что $U_{km}(P,Q)$ кратно $U_{m}(P,Q)$, т. е. последовательность $(U_{m}(P,Q))_{m\geq 1}$является последовательностью делимости . Это подразумевает, в частности, что $U_{n}(P,Q)$ может быть простым только тогда, когда n простое.Другим следствием является аналог возведения в степень возведением в квадрат , который позволяет быстро вычислить $U_{n}(P,Q)$ для больших значений n . Более того, если $\gcd(P,Q)=1$, затем $(U_{m}(P,Q))_{m\geq 1}$ является последовательностью сильной делимости .

Другие свойства делимости заключаются в следующем:

• Если $n\mid m$ странно тогда , $V_{m}$ делит $V_{n}$.
• Пусть N — целое число, относительно простое с 2 Q . Если наименьшее целое положительное число r, на которое N делит $U_{r}$ существует, то набор из n, для которого N делит $U_{n}$ в точности является набором кратных r .
• Если P и Q четные то , $U_{n},V_{n}$ всегда четные, кроме $U_{1}$.
• Если P четно, а Q нечетно, четность то $U_{n}$ то же самое, что n и $V_{n}$ всегда четный.
• Если P нечетно, а Q четно, то $U_{n},V_{n}$ всегда странны для $n=1,2,\ldots$.
• Если P и Q нечетны, то $U_{n},V_{n}$ четны тогда и только тогда, когда n кратно 3.
• Если p — нечетное простое число, то $U_{p}\equiv \left({\tfrac {D}{p}}\right),V_{p}\equiv P{\pmod {p}}$ (см. символ Лежандра ).
• Если p — нечетное простое число и делит P и Q , то p делит $U_{n}$ для каждого $n>1$.
• Если p — нечетное простое число и делит P , но не Q , то p делит $U_{n}$ тогда и только тогда, когда n четно.
• Если p — нечетное простое число и делит не P , а Q , то p никогда не делит $U_{n}$ для $n=1,2,\ldots$.
• Если p — нечетное простое число и делит не PQ, а D , то p делит $U_{n}$ тогда и только тогда, когда p делит n .
• Если p — нечетное простое число и не делит PQD , то p делит $U_{l}$, где $l=p-\left({\tfrac {D}{p}}\right)$.

Последний факт обобщает малую теорему Ферма . Эти факты используются в тесте простоты Лукаса-Лемера .Обратное утверждение последнего факта неверно, как не верно обращение малой теоремы Ферма. Существует составное n, относительно простое с D и делящее $U_{l}$, где $l=n-\left({\tfrac {D}{n}}\right)$. Такая композиция называется псевдопростым числом Люка .

Простой фактор члена последовательности Люка, который не делит ни один более ранний член последовательности, называется примитивным . Теорема Кармайкла утверждает, что все члены последовательности Люка, кроме конечного числа, имеют примитивный простой делитель. Действительно, Кармайкл (1913) показал, что если D положительно и n не равно 1, 2 или 6, то $U_{n}$ имеет примитивный простой делитель. В случае отрицательного результата D — глубокий результат Билю, Анро, Вотье и Миньотта. показывает, что если n > 30, то $U_{n}$ имеет примитивный простой делитель и определяет все случаи $U_{n}$ не имеет примитивного простого множителя.

Конкретные имена

Последовательности Люкаса для некоторых значений P и Q имеют конкретные имена:

n _: (1, −1) числа Фибоначчи

V _n (1, −1) : числа Люка

U _n (2, −1) : числа Пелла

V _n (2, −1) : числа Пела – Люкаса (дополнительные числа Пела)

U _n (1, −2) : числа Якобсталя

V _n (1, −2) : числа Якобсталя – Лукаса.

U _n (3, 2) : числа Мерсенна 2 ^н  − 1

V _n (3, 2) : Числа вида 2 ^н + 1, включающие числа Ферма

U _n (6, 1) : Квадратные корни квадратных треугольных чисел .

n _{Фибоначчи} ( x , −1) : полиномы

V _n ( x , −1) : полиномы Люка

Un _{полиномы} (2 x , 1) : Чебышева второго рода

V _n (2 x , 1) : полиномы Чебышева первого рода, умноженные на 2.

U _n ( x +1, x ) : перегруппировано по базе x.

V _n ( x +1, x ) : x ^н  + 1

Некоторые последовательности Лукаса имеют записи в Электронной энциклопедии целочисленных последовательностей :

$P\,$	$Q\,$	$U_{n}(P,Q)\,$	$V_{n}(P,Q)\,$
−1	3	ОЭИС : A214733
1	−1	ОЭИС : A000045	ОЭИС : A000032
1	1	ОЭИС : A128834	ОЭИС : A087204
1	2	ОЭИС : A107920	ОЭИС : A002249
2	−1	ОЭИС : A000129	ОЭИС : A002203
2	1	ОЭИС : A001477	ОЭИС : A007395
2	2	ОЭИС : A009545
2	3	ОЭИС : A088137
2	4	ОЭИС : A088138
2	5	ОЭИС : A045873
3	−5	ОЭИС : A015523	ОЭИС : A072263
3	−4	ОЭИС : A015521	ОЭИС : A201455
3	−3	ОЭИС : A030195	ОЭИС : A172012
3	−2	ОЭИС : A007482	ОЭИС : A206776
3	−1	ОЭИС : A006190	ОЭИС : A006497
3	1	ОЭИС : A001906	ОЭИС : A005248
3	2	ПРЕТЕНЗИЯ : A000225	ОЭИС : A000051
3	5	ОЭИС : A190959
4	−3	ОЭИС : A015530	ОЭИС : A080042
4	−2	ОЭИС : A090017
4	−1	ОЭИС : A001076	ОЭИС : A014448
4	1	ОЭИС : A001353	ОЭИС : A003500
4	2	ОЭИС : A007070	ОЭИС : A056236
4	3	ОЭИС : A003462	ОЭИС : A034472
4	4	ОЭИС : A001787
5	−3	ОЭИС : A015536
5	−2	ОЭИС : A015535
5	−1	ОЭИС : A052918	ОЭИС : A087130
5	1	ОЭИС : A004254	ОЭИС : A003501
5	4	ОЭИС : A002450	ОЭИС : A052539
6	1	ПРЕТЕНЗИЯ : A001109	ОЭИС : A003499

Приложения

• Последовательности Лукаса используются в вероятностных тестах псевдопростых чисел Люка , которые являются частью широко используемого теста простоты Бэйли-ПСВ .
• Последовательности Лукаса используются в некоторых методах доказательства простоты, включая тест Лукаса-Лемера-Ризеля , а также методы N+1 и гибридные методы N-1/N+1, такие как методы Brillhart-Lehmer-Selfridge 1975.
• LUC — это криптосистема с открытым ключом, основанная на последовательностях Лукаса. который реализует аналоги Эль-Гамаля (LUCELG), Диффи-Хеллмана (LUCDIF) и RSA (LUCRSA). Шифрование сообщения в LUC рассчитывается как член определенной последовательности Люка вместо использования модульного возведения в степень , как в RSA или Диффи-Хеллмана. Однако в статье Bleichenbacher et al. показывает, что многие из предполагаемых преимуществ LUC в области безопасности перед криптосистемами, основанными на модульном возведении в степень, либо отсутствуют, либо не столь существенны, как утверждается.

Программное обеспечение

Sagemath реализует $U_{n}$ и $V_{n}$ как lucas_number1() и lucas_number2(), соответственно.

См. также

• Лукас псевдопростой
• Фробениус псевдопростой
• Псевдопростое число Сомера – Лукаса

Ссылки

• Кармайкл, Р.Д. (1913), «О числовых факторах арифметических форм α ^н ±β ^н », Annals of Mathematics , 15 (1/4): 30–70, doi : 10.2307/1967797 , JSTOR   1967797.
• Лемер, Д.Х. (1930). «Расширенная теория функций Лукаса». Анналы математики . 31 (3): 419–448. Бибкод : 1930АнМат..31..419Л . дои : 10.2307/1968235 . JSTOR   1968235 .
• Уорд, Морган (1954). «Простые делители повторяющихся последовательностей второго порядка». Герцог Мат. Дж . 21 (4): 607–614. дои : 10.1215/S0012-7094-54-02163-8 . hdl : 10338.dmlcz/137477 . МР   0064073 .
• Сомер, Лоуренс (1980). «Свойства делимости первичных повторений Люка по отношению к простым числам» (PDF) . Ежеквартальный журнал Фибоначчи . 18 : 316.
• Лагариас, Дж. К. (1985). «Набор простых чисел, делящих числа Лукаса, имеет плотность 2/3». Пак. Дж. Математика . 118 (2): 449–461. CiteSeerX   10.1.1.174.660 . дои : 10.2140/pjm.1985.118.449 . МР   0789184 .
• Ганс Ризель (1994). Простые числа и компьютерные методы факторизации . Прогресс в математике. Том. 126 (2-е изд.). Биркхойзер. стр. 107–121. ISBN  0-8176-3743-5 .
• Рибенбойм, Пауло; Макдэниел, Уэйн Л. (1996). «Квадратные члены в последовательностях Лукаса» . Дж. Теория чисел . 58 (1): 104–123. дои : 10.1006/jnth.1996.0068 .
• Джой, М.; Кискатер, Ж.-Ж. (1996). «Эффективное вычисление полных последовательностей Люка» (PDF) . Электронные письма . 32 (6): 537–538. Бибкод : 1996ElL....32..537J . дои : 10.1049/эл:19960359 . Архивировано из оригинала (PDF) 2 февраля 2015 г.
• Рибенбойм, Пауло (1996). Новая книга записей простых чисел (электронная книга). Спрингер-Верлаг , Нью-Йорк. дои : 10.1007/978-1-4612-0759-7 . ISBN  978-1-4612-0759-7 .
• Рибенбойм, Пауло (2000). Мои числа, мои друзья: популярные лекции по теории чисел . Нью-Йорк: Springer-Verlag . стр. 1–50. ISBN  0-387-98911-0 .
• Лука, Флориан (2000). «Совершенные числа Фибоначчи и Люка». Ренд. Цирк Матем. Палермо . 49 (2): 313–318. дои : 10.1007/BF02904236 . S2CID   121789033 .
• Ябута, М. (2001). «Простое доказательство теоремы Кармайкла о примитивных делителях» (PDF) . Ежеквартальный журнал Фибоначчи . 39 : 439–443.
• Бенджамин, Артур Т .; Куинн, Дженнифер Дж. (2003). Доказательства, которые действительно имеют значение: искусство комбинаторного доказательства . Математические изложения Дольчиани. Том. 27. Математическая ассоциация Америки . п. 35 . ISBN  978-0-88385-333-7 .
• Последовательность Лукаса в Энциклопедии математики .
• Вайсштейн, Эрик В. «Последовательность Лукаса» . Математический мир .
• Вэй Дай . «Последовательности Лукаса в криптографии» .