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

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

$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, 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 the OEIS)

Циклы по модулю

Числа Леонардо образуют цикл по любому модулю n≥2. Простой способ увидеть это:

• Если пара чисел по модулю n встречается в последовательности дважды, значит, существует цикл.
• Если мы предположим, что основное утверждение ложно, используя предыдущее утверждение, тогда это будет означать, что существует бесконечное количество различных пар чисел между 0 и n-1, что неверно, поскольку существует n ² такие пары.

Циклы для 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)=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)=2L(n-1)-L(n-3)$

с

Числа Леонардо связаны с числами Фибоначчи соотношением $L(n)=2F(n+1)-1,n\geq 0$.

Из этого соотношения легко вывести выражение в замкнутой форме для чисел Леонардо, аналогичное формуле Бине для чисел Фибоначчи:

$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$

где золотое сечение $\varphi =\left(1+{\sqrt {5}}\right)/2$ и $\psi =\left(1-{\sqrt {5}}\right)/2$ являются корнями квадратного многочлена $x^{2}-x-1=0$.

Внешние ссылки

• OEIS A001595 Последовательность