WikiSort.ru - Не сортированное

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

${\displaystyle L_{n}=L_{n-1}+L_{n-2}}$

с начальными значениями ${\displaystyle L_{0}=2}$ и ${\displaystyle L_{1}=1}$ .

Последовательность чисел Люка начинается так:

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

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

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

${\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}\,,}$

где ${\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}}$ — золотое сечение.

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

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

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

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

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

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

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

• ${\displaystyle L_{n}=F_{n-1}+F_{n+1}=F_{n}+2F_{n-1}}$
• ${\displaystyle L_{m+n}=L_{m+1}F_{n}+L_{m}F_{n-1}}$
• ${\displaystyle L_{n}^{2}=5F_{n}^{2}+4(-1)^{n}}$ , и при стремлении ${\displaystyle n}$ к +∞ отношение ${\displaystyle {\frac {L_{n}}{F_{n}}}}$ стремится к ${\displaystyle {\sqrt {5}}.}$
• ${\displaystyle F_{2n}=L_{n}F_{n}}$
• ${\displaystyle F_{n+k}+(-1)^{k}F_{n-k}=L_{k}F_{n}}$
• ${\displaystyle F_{n}={L_{n-1}+L_{n+1} \over 5}}$

Другие свойства

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

Обобщения

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

${\displaystyle L_{-n}=(-1)^{n}L_{n}}$

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

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

Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её.