Числа Люка

Числа Люка задаются рекуррентной формулой

Не следует путать с последовательностями Люка.

$L_n=L_{n-<!--\; -\; -->1}+L_{n-<!--\; -\; -->2}$$L_{n}=L_{n-1}+L_{n-2}$

с начальными значениями $L_0=2$$L_{0}=2$ и $L_1=1$$L_{1}=1$ и сопряжены с числами Фибоначчи. Эти числа названы в честь французского профессора Эдуарда Люка. Последовательность чисел Люка начинается так:

2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, … (последовательность A000032 в OEIS)

Формула общего членаПравить

Последовательность $L_n$$L_{n}$  можно выразить как функцию от n:

$L_n={\mathrm{\phi <!--\; \phi \; -->}}^n+(1-<!--\; -\; -->\mathrm{\phi <!--\; \phi \; -->}{)}^n={\mathrm{\phi <!--\; \phi \; -->}}^n+(-<!--\; -\; -->\mathrm{\phi <!--\; \phi \; -->}{)}^{-<!--\; -\; -->n}={\left(\frac{1+\sqrt{5}}{2}\right)}^n+{\left(\frac{1-<!--\; -\; -->\sqrt{5}}{2}\right)}^n,$$L_{n}=\varphi ^{n}+(1-\varphi )^{n}=\varphi ^{n}+(-\varphi )^{-n}=\left({1+{\sqrt {5}} \over 2}\right)^{n}+\left({1-{\sqrt {5}} \over 2}\right)^{n}\,,$ 

где $\mathrm{\phi <!--\; \phi \; -->}=\frac{1+\sqrt{5}}{2}$$\varphi ={\frac {1+{\sqrt {5}}}{2}}$  — золотое сечение. При n > 1 число |(−φ)⁻ⁿ| меньше 0,5 и с ростом n всё сильнее приближается к нулю, а значит, при n > 1 числа Люка выражаются в виде $L_n=\lfloor <!--\; \lfloor \; -->{\mathrm{\phi <!--\; \phi \; -->}}^n\rceil <!--\; \rceil \; -->,$$L_{n}=\lfloor \varphi ^{n}\rceil ,$  где $\lfloor <!--\; \lfloor \; -->\cdot <!--\; \cdot \; -->\rceil <!--\; \rceil \; -->$$\lfloor \cdot \rceil$  — функция округления к ближайшему целому.

Примечательно, что числа Фибоначчи $F_n$$F_{n}$  выражаются похожим образом с помощью формулы Бине:

$F_n=\frac{{\mathrm{\phi <!--\; \phi \; -->}}^n-<!--\; -\; -->(1-<!--\; -\; -->\mathrm{\phi <!--\; \phi \; -->}{)}^n}{\sqrt{5}}=\frac{{\mathrm{\phi <!--\; \phi \; -->}}^n-<!--\; -\; -->(-<!--\; -\; -->\mathrm{\phi <!--\; \phi \; -->}{)}^{-<!--\; -\; -->n}}{\sqrt{5}}=\frac{1}{\sqrt{5}}\left[{\left(\frac{1+\sqrt{5}}{2}\right)}^n-<!--\; -\; -->{\left(\frac{1-<!--\; -\; -->\sqrt{5}}{2}\right)}^n\right].$$F_{n}={\frac {\varphi ^{n}-(1-\varphi )^{n}}{\sqrt {5}}}={\frac {\varphi ^{n}-(-\varphi )^{-n}}{\sqrt {5}}}={\frac {1}{\sqrt {5}}}\left[\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right].$ 

Проверка простоты числа с помощью чисел ЛюкаПравить

Числа Люка могут использоваться для проверки чисел на простоту. Чтобы проверить, является ли число p простым, возьмём (p + 1)-ое число Люка, вычтем из него единицу — и если полученное число не делится на p нацело, то p гарантированно не является простым. В противном случае число может быть как простым, так и составным и требует более тщательной проверки.

В качестве примера проверим, является ли число 14 простым. 15-ое число Люка — 843.

$\frac{843-<!--\; -\; -->1}{14}=60.142857\dots <!--\; \dots \; -->$${\cfrac {843-1}{14}}=60.142857\ldots$ 

Следовательно, число 14 явно не простое.

Связь с числами ФибоначчиПравить

Числа Люка связаны с числами Фибоначчи следующим формулами

• $L_n=F_{n-<!--\; -\; -->1}+F_{n+1}=F_n+2F_{n-<!--\; -\; -->1}$$L_{n}=F_{n-1}+F_{n+1}=F_{n}+2F_{n-1}$ 
• $L_{m+n}=L_{m+1}{F}_n+L_m{F}_{n-<!--\; -\; -->1}$$L_{m+n}=L_{m+1}F_{n}+L_{m}F_{n-1}$ 
• $L_n^2=5F_n^2+4(-<!--\; -\; -->1{)}^n$$L_{n}^{2}=5F_{n}^{2}+4(-1)^{n}$ , и при стремлении $n$$n$  к +∞ отношение $\frac{L_n}{F_n}$${\frac {L_{n}}{F_{n}}}$  стремится к $\sqrt{5}.$${\sqrt {5}}.$ 
• $F_{2n}=L_n{F}_n$$F_{2n}=L_{n}F_{n}$ 
• $F_{n+k}+(-<!--\; -\; -->1{)}^k{F}_{n-<!--\; -\; -->k}=L_k{F}_n$$F_{n+k}+(-1)^{k}F_{n-k}=L_{k}F_{n}$ 
• $F_n=\frac{L_{n-<!--\; -\; -->1}+L_{n+1}}{5}$$F_{n}={L_{n-1}+L_{n+1} \over 5}$ 

ОбобщенияПравить

Числа Люка можно также определить для отрицательных индексов по формуле:

$L_{-<!--\; -\; -->n}=(-<!--\; -\; -->1{)}^n{L}_n$$L_{-n}=(-1)^{n}L_{n}$ 

Эдуард Люка ввел понятие «обобщённых последовательностей Фибоначчи», частным случаем которых являются числа Фибоначчи и числа Люка

$\begin{array}{c}{F}_n=U_n(1,-<!--\; -\; -->1)\\ L_n=V_n(1,-<!--\; -\; -->1)\end{array}$${\begin{matrix}F_{n}=U_{n}(1,-1)\\L_{n}=V_{n}(1,-1)\end{matrix}}$