Числа Люка

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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 = \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} золотое сечение.

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

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

Например, проверим, является ли число 14 простым. 14-й член ряда - это число 843.

\cfrac {843 - 1} {14} = 60.142857 \ldots

Значит, 14 - гарантированно не простое.

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

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

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

Другие свойства[править | править вики-текст]

Для n>1 величина (-\varphi)^{-n} меньше 1/2, L_n - ближайшее целое к \varphi^n или, что эквивалентно, L_n - это целая часть \varphi^n+1/2, что можно записать как \lfloor \varphi^n+1/2 \rfloor.

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

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

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

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

 \begin{matrix} F_n = U_n(1,-1) \\ L_n = V_n(1,-1) \end{matrix}