Числа Люка: формула, примеры и связь с Фибоначчи

Числа Люка - последовательность целых чисел, в которой каждый член начиная с третьего равен сумме двух предыдущих. Правило знакомо по числам Фибоначчи, но начало здесь другое: и . Из-за этого получаются . Как найти член с заданным номером, почему последовательность связана с золотым сечением и что меняется при написании программы? Выберите индекс в калькуляторе и сравните результат с ручным расчётом.
Определение и первые числа
Примем нумерацию с нуля: , . Для каждого целого действует рекуррентная формула
Рекурсия задаёт новый результат через уже известные результаты. Поэтому одних только слов «сложить два предыдущих» недостаточно: нужны ещё два начальных значения. Первые шаги дают , , , затем , , и . Индекс означает девятый записанный член, поскольку отсчёт начат с нуля.
На каждом шаге для продолжения нужны только два последних числа. Важно сохранить их оба до обновления: например, из пары получаем и переходим к паре . Сама операция остаётся одинаковой, хотя значения растут. Такая зависимость от предыдущих состояний характерна и для других рекуррентных конструкций; например, числа Стирлинга первого рода строят по иному правилу и считают перестановки с заданным числом циклов.
Как вычислить число по индексу
Пусть нужно найти . Удобно записывать рядом индекс и значение, а не считать от первого видимого числа без нумерации:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|---|
| 2 | 1 | 3 | 4 | 7 | 11 | 18 | 29 | 47 |
Последний шаг - . Чтобы проверить результат, полезно пройти ещё на шаг назад: . Если перепутать начальные значения с числами Фибоначчи или принять за , все дальнейшие индексы сдвинутся, даже когда каждое сложение выполнено верно.
Калькулятор выше использует именно эти начальные условия и ограничивает индекс двадцатью: значения в этом диапазоне точно представимы обычным числовым типом JavaScript. Столбцы помогают увидеть рост, но их высота не означает постоянного приращения: разность соседних членов при равна и сама меняется.
Чем числа Люка отличаются от чисел Фибоначчи
Для чисел Фибоначчи обычно берут , и то же правило . Получается . Общее правило не делает две последовательности одинаковыми: начальные условия определяют, какую именно последовательность мы строим.
Связь тем не менее очень простая:
Например, . Равенство можно доказать индукцией. При справа стоит , а при - ; оба значения совпадают с соответствующими числами Люка. Сумма двух соседних выражений того же вида снова даёт выражение для следующего индекса по рекурсии Фибоначчи. Значит, при одинаковых двух стартовых значениях равенство сохраняется на каждом шаге.

Похожее имя встречается и в информатике: куча Фибоначчи - структура данных, а не просто список членов последовательности. Там числа помогают оценивать размеры деревьев; в нашей задаче объектом изучения служат сами члены и их формулы.
Почему сумма соседей Фибоначчи работает
Формула связи полезна не только как способ получить ответ. Она показывает, как из одной рекуррентной последовательности построить другую. Обозначим сумму двух членов Фибоначчи, стоящих по обе стороны выбранного индекса. При переходе к следующему индексу обе части этой суммы сдвигаются на один шаг вправо. Если сложить выражения для двух соседних индексов, правило Фибоначчи сворачивает их в выражение для следующего индекса. Поэтому такие суммы повторяют закон Люка.
Две первые проверки в доказательстве нужны обе: рекурсия второго порядка требует двух стартовых значений. Проверка нескольких примеров сама по себе не доказывает равенство для всех индексов, а индукционный переход объясняет, почему каждый следующий случай следует из предыдущих двух. Этот приём применим всякий раз, когда требуется сравнить две последовательности с одинаковым законом построения.
Формула через золотое сечение
Рекурсию можно решить и без последовательного сложения всех предыдущих членов. Подстановка предполагаемого решения вида приводит к уравнению . Его корни равны
Оба выражения и удовлетворяют той же рекурсии. Их сумма имеет нужные начальные значения: при получается , при - . Поэтому
Эта формула выполняется для целых . Хотя в ней есть иррациональные числа, их сумма в точности целая: это следует уже из совпадения начальных условий и рекурсии. Для больших индексов , поэтому добавка стремится к нулю. Отношение соседних членов стремится к . Например, , а : приближения лежат по разные стороны предела. Золотое сечение встречается и в обсуждении пропорций в искусстве, но существование математического отношения само по себе не доказывает, что художник его использовал.
Алгоритм и точность вычислений
Для одного числа при умеренном достаточно хранить пару , . Повторяйте обновление пары на ровно раз; после этого в окажется . При обновлений нет, поэтому ответ сразу равен двум. Такой способ делает сложений и хранит постоянное число целых переменных. Если нужна вся таблица, сохраняйте каждый результат в массиве; тогда память растёт вместе с числом записанных членов.
Оценка числа операций не равна полной оценке времени для сколь угодно больших индексов: числа растут, и сложение длинных целых требует больше работы, чем сложение машинных чисел. В JavaScript обычный тип number хранит все целые точно лишь до . Для больших индексов используйте BigInt и целочисленную рекурсию; формула с корнями при вычислениях с плавающей точкой может потерять точность из-за округления.
Для очень большого индекса матричное возведение в степень позволяет уменьшить количество матричных умножений до порядка . Однако размер самих целых чисел при этом тоже растёт. Выбор метода зависит от того, нужно ли одно значение, вся последовательность или только остаток по модулю.
Если программа должна вернуть только остаток от деления на заданное положительное число, можно после каждого сложения брать остаток. Результат будет таким же, как остаток от полного числа, поскольку остаток суммы определяется остатками слагаемых. Это позволяет не хранить само огромное число, когда задаче нужна только проверка делимости. При этом последовательность остатков со временем повторяется: возможных пар остатков конечное число, а следующая пара однозначно определяется текущей.
Рекурсивная функция, которая для каждого индекса заново вызывает себя для двух предыдущих, буквально повторяет формулу, но многократно пересчитывает одни и те же значения. Итерация с двумя переменными избегает этого повторения. Если по условию нужен именно рекурсивный код, промежуточные ответы можно запоминать; тогда важно отдельно учесть память для таблицы и вызовов.
Где встречаются числа Люка
Одна комбинаторная интерпретация связывает с размещениями на круге. Для представим цикл из вершин. Число способов выбрать множество вершин без двух соседних, включая пустой выбор, равно . Для треугольника допустимы пустое множество и три отдельных вершины: всего четыре, то есть . Для квадрата добавляются две пары противоположных вершин: . Здесь соседними считаются также первая и последняя вершины, поэтому круг нельзя без поправки заменить цепочкой.
Для произвольного цикла равенство можно получить разбиением по одной выбранной вершине. Если она не выбрана, остальные вершины образуют цепочку и выборы на ней считаются числами Фибоначчи. Если она выбрана, два её соседа исключаются и остаётся более короткая цепочка. Сумма двух случаев даёт формулу связи с Фибоначчи. Пустое множество обязательно учитывать: оно тоже не содержит пары соседних вершин. Условие про круг существенно даже тогда, когда крайние вершины изображены на рисунке далеко друг от друга.
Числа Люка встречаются и в теории чисел, но название не следует смешивать с другими именными последовательностями. Например, числа Серпинского определяются свойством составности специального выражения, а числа Шура связаны с раскрасками и монохромными тройками. Общая фамильная форма названия не означает общего способа построения.
Частые ошибки
- Забывать начальные условия. Одинаковая рекурсия с началами и задаёт разные последовательности.
- Сдвигать индекс. При принятой здесь нумерации , а ; в другом источнике начало записи может быть оформлено иначе.
- Считать отношение соседей равным золотому сечению. Для конечного индекса это рациональное приближение, а не точное значение иррационального предела.
- Округлять формулу без контроля точности. При больших ошибка вычислений с плавающей точкой может испортить целый ответ.
FAQ
Какое число Люка стоит на восьмом индексе?
При нумерации с нуля : это сумма и .
Является ли каждое число Люка простым?
Нет. Уже составное. В последовательности встречаются и простые, и составные члены.
Можно ли найти член без таблицы предыдущих?
Да, существует формула ; для точного программного расчёта больших значений подходят целочисленные алгоритмы, например матричное возведение в степень.
Коротко
Числа Люка начинаются с и , а каждый следующий член равен сумме двух предыдущих. Они подчиняются той же рекурсии, что и числа Фибоначчи, но отличаются начальными условиями; связь и формула через корни помогают переходить между представлениями.
Читайте также

Числа Фибоначчи: рекуррентная формула и примеры
Числа Фибоначчи и рекуррентная формула: начальные значения, вычисление по шагам, пример со ступеньками, вычисление членов, формула Бине и связь последовательности с золотым сечением.

Числа трибоначчи: формула и примеры вычисления
Числа трибоначчи: три начальных значения, рекуррентная формула и расчёт по шагам. Как последовательность считает пути по ступенькам и как написать эффективный алгоритм.

Дерево рекурсии: как посчитать сложность по уровням
Дерево рекурсии помогает разобрать рекуррентное соотношение: построим уровни вызовов, сложим их стоимость и найдём сложность на примерах деления задачи.

Ханойские башни и рекурсия: решение по шагам
Ханойские башни и рекурсия: разберём правила, семь ходов для трёх дисков, рекурсивный алгоритм, доказательство минимального числа ходов и его сложность.

Обходы двоичного дерева: порядки и примеры
Обходы двоичного дерева на одном примере: прямой, симметричный, обратный и по уровням. Как работают рекурсия, стек и очередь, какие результаты и сложность.

Сортировка слиянием: сложность по времени и памяти
Разбираем сложность сортировки слиянием: вывод O(n log n), число сравнений на примере, расход дополнительной памяти и условия устойчивости алгоритма при равных ключах.