цепь Лукаса
В математике цепочка Люка — это ограниченный тип цепочки сложения , названный в честь французского математика Эдуарда Люка . Это последовательность
- а 0 , а 1 , а 2 , а 3 ,...
это удовлетворяет
- а 0 = 1,
и
- для каждого k > 0: a k = a i + a j и либо a i = a j, либо | а я - а j | знак равно а м , для некоторых я , j , м < k . [1] [2]
Последовательность степеней 2 (1, 2, 4, 8, 16, ...) и последовательность Фибоначчи (с небольшой корректировкой начальной точки 1, 2, 3, 5, 8, ...) просты. примеры цепей Лукаса.
Цепи Lucas были представлены Питером Монтгомери в 1983 году. [3] Если L ( n ) — длина кратчайшей цепочки Люка для n , то Куц показал, что большинство n не имеют L < (1-ε) log φ n , где φ — золотое сечение . [1]
Ссылки
[ редактировать ]- ↑ Перейти обратно: Перейти обратно: а б Гай (2004) стр.169
- ^ Вайсштейн, Эрик В. «Лукас Чейн» . mathworld.wolfram.com . Проверено 11 августа 2020 г.
- ^ Куц (2002)
- Гай, Ричард К. (2004). Нерешенные проблемы теории чисел (3-е изд.). Спрингер-Верлаг . стр. 169–171. ISBN 978-0-387-20860-2 . Збл 1058.11001 .
- Куц, Мартин (2002). «Нижние границы для цепей Лукаса» (PDF) . СИАМ Дж. Компьютер . 31 (6): 1896–1908. дои : 10.1137/s0097539700379255 . Збл 1055.11077 .
- Монтгомери, Питер Л. (1983). «Оценка повторений формы X m+n = f(X m , X n , X m-n ) с помощью цепей Лукаса» (PS) . Неопубликовано .