Числа Люка

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

с начальными значениями и .

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

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

Формула общего члена[править | править вики-текст]

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

где золотое сечение.

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

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

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

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

Связь с числами Фибоначчи[править | править вики-текст]

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

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

Другие свойства[править | править вики-текст]

Для величина меньше 1/2, - ближайшее целое к или, что эквивалентно, - это целая часть , что можно записать как .

Обобщения[править | править вики-текст]

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

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