Числа Люка

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

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

с начальными значениями $L_{0}=2$ и $L_{1}=1$ ; сопряжены с числами Фибоначчи. Первые значения^[1]:

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

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

Последовательность $L_{n}$ можно выразить как функцию от $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}

,

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

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

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]

.

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

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

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

Пример проверки числа 15: 16-ое число Люка — 1364; $(1364-1)/{15}=90{,}866666\ldots$ , следовательно, число 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 +\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}={L_{n-1}+L_{n+1} \over 5}$