Числа Люка
Числа Люка задаются рекуррентной формулой
с начальными значениями и и сопряжены с числами Фибоначчи. Эти числа названы в честь французского профессора Эдуарда Люка. Последовательность чисел Люка начинается так:
Формула общего члена
Последовательность можно выразить как функцию от n:
где — золотое сечение. При n > 1 число |(−φ)−n| меньше 0,5 и с ростом n всё сильнее приближается к нулю, а значит, при n > 1 числа Люка выражаются в виде где — функция округления к ближайшему целому.
Примечательно, что числа Фибоначчи выражаются похожим образом с помощью формулы Бине:
Проверка простоты числа с помощью чисел Люка
Числа Люка могут использоваться для проверки чисел на простоту. Чтобы проверить, является ли число p простым, возьмём (p + 1)-ое число Люка, вычтем из него единицу — и если полученное число не делится на p нацело, то p гарантированно не является простым. В противном случае число может быть как простым, так и составным и требует более тщательной проверки.
В качестве примера проверим, является ли число 14 простым. 15-ое число Люка — 843.
Следовательно, число 14 явно не простое.
Связь с числами Фибоначчи
Числа Люка связаны с числами Фибоначчи следующим формулами
- , и при стремлении к +∞ отношение стремится к
Обобщения
Числа Люка можно также определить для отрицательных индексов по формуле:
Эдуард Люка ввел понятие «обобщённых последовательностей Фибоначчи», частным случаем которых являются числа Фибоначчи и числа Люка