Набор чисел, используемых в алгоритме плавной сортировки
Числа Леонардо представляют собой последовательность чисел, заданную рекуррентным соотношением:
Л ( н ) = { 1 если н = 0 1 если н = 1 Л ( н − 1 ) + Л ( н − 2 ) + 1 если н > 1 {\displaystyle L(n)={\begin{cases}1&{\mbox{if }}n=0\\1&{\mbox{if }}n=1\\L(n-1)+L(n-2)+1&{\mbox{if }}n>1\\\end{cases}}} Эдсгер В. Дейкстра [1] использовал их как неотъемлемую часть своего алгоритма плавной сортировки , [2] а также проанализировал их довольно подробно. [3] [4]
Простое число Леонардо — это число Леонардо, которое также является простым .
Ценности Первые несколько чисел Леонардо — это
1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, ... (последовательность A001595 в OEIS ) Первые несколько простых чисел Леонардо — это
3 , 5 , 41 , 67 , 109 , 1973, 5167, 2692537, 11405773, 126491971, 331160281, 535828591, 279167724889, 145446920496281, 28944668049352441, 5760134388741632239, 63880869269980199809, 167242286979696845953, 597222253637954133837103, ... (sequence A145912 in OEIS )
Циклы по модулю Числа Леонардо образуют цикл по любому модулю n≥2. Простой способ увидеть это:
Если пара чисел по модулю n встречается в последовательности дважды, то имеет место цикл. Если предположить, что основное утверждение ложно, используя предыдущее утверждение, то это будет означать, что существует бесконечное множество различных пар чисел между 0 и n-1, что является ложным, поскольку таких пар n 2 . Циклы для n≤8:
Модуль Цикл Длина 2 1 1 3 1,1,0,2,0,0,1,2 8 4 1,1,3 3 5 1,1,3,0,4,0,0,1,2,4,2,2,0,3,4,3,3,2,1,4 20 6 1,1,3,5,3,3,1,5 8 7 1,1,3,5,2,1,4,6,4,4,2,0,3,4,1,6 16 8 1,1,3,5,1,7 6
Цикл всегда заканчивается на паре (1,n-1), так как это единственная пара, которая может предшествовать паре (1,1).
Выражения Применяется следующее уравнение: L ( n ) = 2 L ( n − 1 ) − L ( n − 3 ) {\displaystyle L(n)=2L(n-1)-L(n-3)} Доказательство L ( n ) = L ( n − 1 ) + L ( n − 2 ) + 1 = L ( n − 1 ) + L ( n − 2 ) + 1 + L ( n − 3 ) − L ( n − 3 ) = 2 L ( n − 1 ) − L ( n − 3 ) {\displaystyle L(n)=L(n-1)+L(n-2)+1=L(n-1)+L(n-2)+1+L(n-3)-L(n-3)=2L(n-1)-L(n-3)}
Связь с числами Фибоначчи Числа Леонардо связаны с числами Фибоначчи соотношением . L ( n ) = 2 F ( n + 1 ) − 1 , n ≥ 0 {\displaystyle L(n)=2F(n+1)-1,n\geq 0}
Из этого соотношения легко вывести замкнутое выражение для чисел Леонардо, аналогичное формуле Бине для чисел Фибоначчи:
L ( n ) = 2 φ n + 1 − ψ n + 1 φ − ψ − 1 = 2 5 ( φ n + 1 − ψ n + 1 ) − 1 = 2 F ( n + 1 ) − 1 {\displaystyle L(n)=2{\frac {\varphi ^{n+1}-\psi ^{n+1}}{\varphi -\psi }}-1={\frac {2}{\sqrt {5}}}\left(\varphi ^{n+1}-\psi ^{n+1}\right)-1=2F(n+1)-1} где золотое сечение и являются корнями квадратного многочлена . φ = ( 1 + 5 ) / 2 {\displaystyle \varphi =\left(1+{\sqrt {5}}\right)/2} ψ = ( 1 − 5 ) / 2 {\displaystyle \psi =\left(1-{\sqrt {5}}\right)/2} x 2 − x − 1 = 0 {\displaystyle x^{2}-x-1=0}
Ссылки ^ "Архив EWDijkstra: Числа Фибоначчи и числа Леонардо. (EWD 797)". www.cs.utexas.edu . Получено 11 августа 2020 г. ^ Дейкстра, Эдсгер В. Гладкая сортировка – альтернатива сортировке на месте (EWD-796a) (PDF) . Архив Э. В. Дейкстры. Центр американской истории, Техасский университет в Остине . (транскрипция)^ "Архив EWDijkstra: Smoothsort, альтернатива сортировке in situ (EWD 796a)". www.cs.utexas.edu . Получено 11 августа 2020 г. ^ "Leonardo Number - GeeksforGeeks". www.geeksforgeeks.org . 18 октября 2017 . Получено 2022-10-08 .
Внешние ссылки Последовательность OEIS A001595