Число Леонардо

Набор чисел, используемых в алгоритме плавной сортировки

Числа Леонардо представляют собой последовательность чисел, заданную рекуррентным соотношением:

Л ( н ) = { 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:

МодульЦиклДлина
211
31,1,0,2,0,0,1,28
41,1,33
51,1,3,0,4,0,0,1,2,4,2,2,0,3,4,3,3,2,1,420
61,1,3,5,3,3,1,58
71,1,3,5,2,1,4,6,4,4,2,0,3,4,1,616
81,1,3,5,1,76

Цикл всегда заканчивается на паре (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}

Ссылки

  1. ^ "Архив EWDijkstra: Числа Фибоначчи и числа Леонардо. (EWD 797)". www.cs.utexas.edu . Получено 11 августа 2020 г.
  2. ^ Дейкстра, Эдсгер В. Гладкая сортировка – альтернатива сортировке на месте (EWD-796a) (PDF) . Архив Э. В. Дейкстры. Центр американской истории, Техасский университет в Остине .(транскрипция)
  3. ^ "Архив EWDijkstra: Smoothsort, альтернатива сортировке in situ (EWD 796a)". www.cs.utexas.edu . Получено 11 августа 2020 г.
  4. ^ "Leonardo Number - GeeksforGeeks". www.geeksforgeeks.org . 18 октября 2017 . Получено 2022-10-08 .
  • Последовательность OEIS A001595
Retrieved from "https://en.wikipedia.org/w/index.php?title=Leonardo_number&oldid=1241888341"