Числа Люка

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

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, … (последовательность A000032 в OEIS)

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

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

L_{n} = φ^{n} + (1 - φ)^{n} = φ^{n} + (- φ)^{- n} = {(\frac{1 + \sqrt{5}}{2})}^{n} + {(\frac{1 - \sqrt{5}}{2})}^{n},

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

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

F_{n} = \frac{φ^{n} - (1 - φ)^{n}}{\sqrt{5}} = \frac{φ^{n} - (- φ)^{- n}}{\sqrt{5}} = \frac{1}{\sqrt{5}} [{(\frac{1 + \sqrt{5}}{2})}^{n} - {(\frac{1 - \sqrt{5}}{2})}^{n}] .

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

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

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

$\frac{843 - 1}{14} = 60.142857 \dots$

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

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

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

$L_{n} = F_{n - 1} + F_{n + 1} = F_{n} + 2 F_{n - 1}$
$L_{m + n} = L_{m + 1} F_{n} + L_{m} F_{n - 1}$
$L_{n}^{2} = 5 F_{n}^{2} + 4 (- 1)^{n}$ , и при стремлении $n$ к +∞ отношение $\frac{L_{n}}{F_{n}}$ стремится к $\sqrt{5} .$
$F_{2 n} = 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}$

Обобщения[править]

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

L_{- n} = (- 1)^{n} L_{n}

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

\begin{matrix} F_{n} = U_{n} (1, - 1) \\ L_{n} = V_{n} (1, - 1) \end{matrix}