Числа Люка

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

с начальными значениями и и сопряжены с числами Фибоначчи. Эти числа названы в честь французского профессора Эдуарда Люка. Последовательность чисел Люка начинается так:

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

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

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

где золотое сечение. При n > 1 число |(−φ)n| меньше 0,5 и с ростом n всё сильнее приближается к нулю, а значит, при n > 1 числа Люка выражаются в виде где — функция округления к ближайшему целому.

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

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

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

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

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

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

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

  • , и при стремлении к +∞ отношение стремится к

Обобщения

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

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.