Числа Люка

Не следует путать с последовательностями Люка.

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

<math>L_n = L_{n-1} + L_{n-2}</math>

с начальными значениями <math>L_0 = 2</math> и <math>L_1 = 1</math>.

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

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

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

Последовательность <math>L_n</math> можно выразить как функцию от n:

<math>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> \varphi = \frac{1+\sqrt{5}}{2} </math> — золотое сечение.

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

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

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

<math>\cfrac {843 - 1} {14} = 60.142857 \ldots</math>

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

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

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

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

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

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

Обобщения

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

<math> L_{-n} = (-1)^n L_n </math>

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

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

Отрывок, характеризующий Числа Люка

– Ежели бы он мог атаковать нас, то он нынче бы это сделал, – сказал он.
– Вы, стало быть, думаете, что он бессилен, – сказал Ланжерон.
– Много, если у него 40 тысяч войска, – отвечал Вейротер с улыбкой доктора, которому лекарка хочет указать средство лечения.
– В таком случае он идет на свою погибель, ожидая нашей атаки, – с тонкой иронической улыбкой сказал Ланжерон, за подтверждением оглядываясь опять на ближайшего Милорадовича.
Но Милорадович, очевидно, в эту минуту думал менее всего о том, о чем спорили генералы.
– Ma foi, [Ей Богу,] – сказал он, – завтра всё увидим на поле сражения.
Вейротер усмехнулся опять тою улыбкой, которая говорила, что ему смешно и странно встречать возражения от русских генералов и доказывать то, в чем не только он сам слишком хорошо был уверен, но в чем уверены были им государи императоры.
– Неприятель потушил огни, и слышен непрерывный шум в его лагере, – сказал он. – Что это значит? – Или он удаляется, чего одного мы должны бояться, или он переменяет позицию (он усмехнулся). Но даже ежели бы он и занял позицию в Тюрасе, он только избавляет нас от больших хлопот, и распоряжения все, до малейших подробностей, остаются те же.
– Каким же образом?.. – сказал князь Андрей, уже давно выжидавший случая выразить свои сомнения.
Кутузов проснулся, тяжело откашлялся и оглянул генералов.
– Господа, диспозиция на завтра, даже на нынче (потому что уже первый час), не может быть изменена, – сказал он. – Вы ее слышали, и все мы исполним наш долг. А перед сражением нет ничего важнее… (он помолчал) как выспаться хорошенько.
Он сделал вид, что привстает. Генералы откланялись и удалились. Было уже за полночь. Князь Андрей вышел.

Военный совет, на котором князю Андрею не удалось высказать свое мнение, как он надеялся, оставил в нем неясное и тревожное впечатление. Кто был прав: Долгоруков с Вейротером или Кутузов с Ланжероном и др., не одобрявшими план атаки, он не знал. «Но неужели нельзя было Кутузову прямо высказать государю свои мысли? Неужели это не может иначе делаться? Неужели из за придворных и личных соображений должно рисковать десятками тысяч и моей, моей жизнью?» думал он.