Числа Люка

Числа Люка́ — элементы линейной рекуррентной последовательности, заданной формулой:

$L_n=L_{n-1}+L_{n-2}$

с начальными значениями $L_0=2$ и $L_1=1$; сопряжены с числами Фибоначчи. Первые значения:

2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, …

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

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

$L_n={\phi }^n+(1-\phi {)}^n={\phi }^n+(-\phi {)}^{-n}={\left(\frac{1+\sqrt{5}}{2}\right)}^n+{\left(\frac{1-\sqrt{5}}{2}\right)}^n$,

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

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

$F_n=\frac{{\phi }^n-(1-\phi {)}^n}{\sqrt{5}}=\frac{{\phi }^n-(-\phi {)}^{-n}}{\sqrt{5}}=\frac{1}{\sqrt{5}}[{\left(\frac{1+\sqrt{5}}{2}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n]$.

Числа Люка можно также определить для отрицательных индексов по формуле $L_{-n}=(-1{)}^n{L}_n$.

Проверка простоты

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

Пример проверки числа 15: 16-е число Люка — 1364; $(1364-1)/15=90,866666\dots$, следовательно, число 15 — составное.

Пример для числа 17: 18-е число Люка равно 3571; $(3571-1)/17=120$, значит, число 17 может быть простым.

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

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

• $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_n^2=5F_n^2+4(-1{)}^n$, и при $n\to +\mathrm{\infty }$ отношение $\frac{L_n}{F_n}$ стремится к $\sqrt{5}$
• $F_{2n}=L_n{F}_n$
• $F_{n+k}+(-1{)}^k{F}_{n-k}=L_k{F}_n$
• $F_n=\frac{L_{n-1}+L_{n+1}}{5}$

Литература

• Шаблон:Статья
• Шаблон:Книга