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

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

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

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

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

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

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

Повторяющиеся отношения

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

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

и

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

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

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

Примеры

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

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

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

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

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

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

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

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

${\displaystyle a+b=P\,,}$

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

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

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

Отчетливые корни

Когда ${\displaystyle D\neq 0}$, а и б различны, и можно быстро проверить, что

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

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

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

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

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

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

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

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

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

Свойства

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

Обычный производящие функции находятся

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

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

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

Если последовательности Лукаса ${\displaystyle U_{n}(P,Q)}$ и ${\displaystyle V_{n}(P,Q)}$ иметь разборчивый ${\displaystyle D=P^{2}-4Q}$, то последовательности на основе ${\displaystyle P_{2}}$ и ${\displaystyle Q_{2}}$ куда

${\displaystyle P_{2}=P+2}$

${\displaystyle Q_{2}=P+Q+1}$

имеют одинаковый дискриминант: ${\displaystyle P_{2}^{2}-4Q_{2}=(P+2)^{2}-4(P+Q+1)=P^{2}-4Q=D}$.

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

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

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

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

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

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

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

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

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

Другие свойства делимости следующие:^[1]

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

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

А главный фактор члена в последовательности Лукаса, который не делит ни одного более раннего члена в последовательности, называется примитивный.Теорема Кармайкла утверждает, что все, кроме конечного числа членов в последовательности Лукаса, имеют примитивный главный фактор.^[2] Действительно, Кармайкл (1913) показал, что если D положительный и п не 1, 2 или 6, тогда ${\displaystyle U_{n}}$ имеет примитивный простой фактор. В случае D отрицательный, глубокий результат Bilu, Hanrot, Voutier и Mignotte^[3] показывает, что если п > 30, то ${\displaystyle U_{n}}$ имеет примитивный простой фактор и определяет все случаи ${\displaystyle U_{n}}$ не имеет примитивного простого множителя.

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

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

U_п(1,−1) : Числа Фибоначчи

V_п(1,−1) : Числа Лукаса

U_п(2,−1) : Числа Пелла

V_п(2,−1) : Числа Пелла-Лукаса (сопутствующие числа Пелла)

U_п(1,−2) : Числа Якобсталя

V_п(1,−2) : Числа Якобсталя-Лукаса

U_п(3, 2) : Числа Мерсенна 2^п − 1

V_п(3, 2) : Числа формы 2^п + 1, включая Числа Ферма (Ябута 2001 ) ошибка harv: несколько целей (2 ×): CITEREFYabuta2001 (помощь).

U_п(6, 1) : Квадратный корень из квадратные треугольные числа.

U_п(Икс,−1) : Полиномы Фибоначчи

V_п(Икс,−1) : Полиномы Лукаса

U_п(2Икс, 1) : Полиномы Чебышева второго рода

V_п(2Икс, 1) : Полиномы Чебышева первого рода умноженное на 2

U_п(Икс+1, Икс) : Repunits основание Икс

V_п(Икс+1, Икс) : Икс^п + 1

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

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

Приложения

• Последовательности Люка используются в вероятностных Лукас псевдопрайм тесты, которые являются частью обычно используемых Тест на простоту Baillie-PSW.
• Последовательности Лукаса используются в некоторых методах доказательства простоты, включая Тест Лукаса-Лемера-Ризеля, а также N + 1 и гибридный N-1 / N + 1 методы, такие как методы Brillhart-Lehmer-Selfridge 1975^[4]
• LUC - это криптосистема с открытым ключом на основе последовательностей Лукаса^[5] который реализует аналоги Эль-Гамаль (ЛЮСЕЛЬГ), Диффи-Хеллман (LUCDIF) и ЮАР (LUCRSA). Шифрование сообщения в LUC вычисляется как член определенной последовательности Лукаса вместо использования модульное возведение в степень как в RSA или Diffie-Hellman. Однако в статье Bleichenbacher et al.^[6] показывает, что многие из предполагаемых преимуществ безопасности LUC над криптосистемами, основанными на модульном возведении в степень, либо отсутствуют, либо не столь существенны, как заявлено.

Смотрите также

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

Примечания

1. О таких отношениях и свойствах делимости см. (Кармайкл 1913 ), (Лемер 1930 ) или же (Рибенбойм 1996, 2.IV).
2. Ябута, М (2001). «Простое доказательство теоремы Кармайкла о примитивных делителях» (PDF). Ежеквартальный отчет Фибоначчи. 39: 439–443. Получено 4 октября 2018.
3. Билу, Юрий; Анро, Гийом; Voutier, Paul M .; Миньотт, Морис (2001). «Существование примитивных делителей чисел Лукаса и Лемера» (PDF). J. Reine Angew. Математика. 2001 (539): 75–122. Дои:10.1515 / crll.2001.080. МИСТЕР  1863855.
4. Джон Бриллхарт; Деррик Генри Лемер; Джон Селфридж (Апрель 1975 г.). "Новые критерии первичности и факторизации 2^м ± 1". Математика вычислений. 29 (130): 620–647. Дои:10.1090 / S0025-5718-1975-0384673-1. JSTOR  2005583.
5. П. Дж. Смит; М. Дж. Дж. Леннон (1993). «LUC: новая система открытых ключей». Труды Девятого IFIP Int. Symp. О компьютерной безопасности: 103–117. CiteSeerX  10.1.1.32.1835.
6. Д. Блейхенбахер; В. Босма; А. К. Ленстра (1995). «Некоторые замечания по криптосистемам на основе Лукаса» (PDF). Конспект лекций по информатике. 963: 386–396. Дои:10.1007/3-540-44750-4_31. ISBN  978-3-540-60221-7.

Рекомендации

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