Leonardo number

The Leonardo numbers are a sequence of numbers given by the recurrence:
:$L(n) = \begin 1 & \mbox n = 0 \\ 1 & \mbox n = 1 \\ L(n - 1) + L(n - 2) + 1 & \mbox n > 1 \\ \end$

Edsger W. Dijkstra used them as an integral part of his smoothsort algorithm, and also analyzed them in some detail.

A Leonardo prime is a Leonardo number that's also prime.

Values

The first few Leonardo numbers are
:1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, ...

The first few Leonardo primes are
: 3, 5, 41, 67, 109, 1973, 5167, 2692537, 11405773, 126491971, 331160281, 535828591, 279167724889, 145446920496281, 28944668049352441, 5760134388741632239, 63880869269980199809, 167242286979696845953, 597222253637954133837103, ...

Modulo cycles

The Leonardo numbers form a cycle in any modulo n≥2. An easy way to see it is:
* If a pair of numbers modulo n appears twice in the sequence, then there's a cycle.
* If we assume the main statement is false, using the previous statement, then it would imply there's infinite distinct pairs of numbers between 0 and n-1, which is false since there are n² such pairs.
The cycles for n≤8 are:

The cycle always end on the pair (1,n-1), as it's the only pair which can precede the pair (1,1).

Expressions

*The following equation applies:
:$L(n)=2L(n-1)-L(n-3)$

Relation to Fibonacci numbers

The Leonardo numbers are related to the Fibonacci numbers by the relation $L(n) = 2 F(n+1) - 1, n \ge 0$.

From this relation it is straightforward to derive a closed-form expression for the Leonardo numbers, analogous to Binet's formula for the Fibonacci numbers:
:$L(n) = 2 \frac- 1 = \frac \left(\varphi^ - \psi^\right) - 1 = 2F(n+1) - 1$

where the golden ratio $\varphi = \left(1 + \sqrt 5\right)/2$ and $\psi = \left(1 - \sqrt 5\right)/2$ are the roots of the quadratic polynomial $x^2 - x - 1 = 0$.

References

External links

*

{{Classes of natural numbers

Integer sequences
Fibonacci numbers
Recurrence relations