Числа Люка

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

[math]\displaystyle{ L_n = L_{n-1} + L_{n-2} }[/math]

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

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

Формула общего члена

Последовательность [math]\displaystyle{ L_n }[/math] можно выразить как функцию от n:

[math]\displaystyle{ 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\, , }[/math]

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

Примечательно, что числа Фибоначчи [math]\displaystyle{ F_n }[/math] выражаются похожим образом с помощью формулы Бине:

[math]\displaystyle{ 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]. }[/math]

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

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

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

[math]\displaystyle{ \cfrac {843 - 1} {14} = 60.142857 \ldots }[/math]

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

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

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

[math]\displaystyle{ L_n = F_{n-1}+F_{n+1}=F_n+2F_{n-1} }[/math]
[math]\displaystyle{ L_{m+n} = L_{m+1}F_{n}+L_mF_{n-1} }[/math]
[math]\displaystyle{ L_n^2 = 5 F_n^2 + 4 (-1)^n }[/math], и при стремлении [math]\displaystyle{ n }[/math] к +∞ отношение [math]\displaystyle{ \frac{L_n}{F_n} }[/math] стремится к [math]\displaystyle{ \sqrt{5}. }[/math]
[math]\displaystyle{ F_{2n} = L_n F_n }[/math]
[math]\displaystyle{ F_{n+k} + (-1)^k F_{n-k} = L_k F_n }[/math]
[math]\displaystyle{ F_n = {L_{n-1}+L_{n+1} \over 5} }[/math]

Обобщения

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

[math]\displaystyle{ L_{-n} = (-1)^n L_n }[/math]

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

[math]\displaystyle{ \begin{matrix} F_n = U_n(1,-1) \\ L_n = V_n(1,-1) \end{matrix} }[/math]