Главная
Новости
Строительство
Ремонт
Дизайн и интерьер




13.01.2022


29.12.2021


09.12.2021


09.12.2021


08.11.2021





Яндекс.Метрика





Числа Люка

27.03.2022

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

L n = L n − 1 + L n − 2 {displaystyle L_{n}=L_{n-1}+L_{n-2}}

с начальными значениями L 0 = 2 {displaystyle L_{0}=2} и L 1 = 1 {displaystyle L_{1}=1} и сопряжены с числами Фибоначчи. Эти числа названы в честь французского профессора Эдуарда Люка. Последовательность чисел Люка начинается так:

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

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

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

L n = φ n + ( 1 − φ ) n = φ n + ( − φ ) − n = ( 1 + 5 2 ) n + ( 1 − 5 2 ) n , {displaystyle L_{n}=varphi ^{n}+(1-varphi )^{n}=varphi ^{n}+(-varphi )^{-n}=left({1+{sqrt {5}} over 2} ight)^{n}+left({1-{sqrt {5}} over 2} ight)^{n},,}

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

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

F n = φ n − ( 1 − φ ) n 5 = φ n − ( − φ ) − n 5 = 1 5 [ ( 1 + 5 2 ) n − ( 1 − 5 2 ) n ] . {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}} ight)^{n}-left({frac {1-{sqrt {5}}}{2}} ight)^{n} ight].}

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

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

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

843 − 1 14 = 60.142857 … {displaystyle {cfrac {843-1}{14}}=60.142857ldots }

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

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

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

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

Обобщения

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

L − n = ( − 1 ) n L n {displaystyle L_{-n}=(-1)^{n}L_{n}}

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

F n = U n ( 1 , − 1 ) L n = V n ( 1 , − 1 ) {displaystyle {egin{matrix}F_{n}=U_{n}(1,-1)L_{n}=V_{n}(1,-1)end{matrix}}}

Слава России! Z