View source for Leonardo number

{{Short description|Set of numbers used in the smoothsort algorithm}}
{{primary sources|date=July 2017}}
The '''Leonardo numbers''' are a sequence of numbers given by the recurrence:
:<math> 
  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}
 </math>

[[Edsger W. Dijkstra]]<ref>{{Cite web|title=E.W.Dijkstra Archive: Fibonacci numbers and Leonardo numbers. (EWD 797)|url=http://www.cs.utexas.edu/users/EWD/transcriptions/EWD07xx/EWD797.html|access-date=2020-08-11|website=www.cs.utexas.edu}}</ref> used them as an integral part of his [[smoothsort]] [[algorithm]],<ref>{{Cite EWD|796a|Smoothsort – an alternative to sorting in situ}}</ref>  and also analyzed them in some detail.<ref>{{Cite web|title=E.W.Dijkstra Archive: Smoothsort, an alternative for sorting in situ (EWD 796a)|url=http://www.cs.utexas.edu/users/EWD/transcriptions/EWD07xx/EWD796a.html|access-date=2020-08-11|website=www.cs.utexas.edu}}</ref> <ref>{{Cite web |title=Leonardo Number - GeeksforGeeks |url=https://www.geeksforgeeks.org/leonardo-number/amp/ |access-date=2022-10-08 |website=www.geeksforgeeks.org|date=18 October 2017 }}</ref>

A '''Leonardo prime''' is a '''Leonardo number''' that is also [[Prime number|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, ... {{OEIS|id=A001595}}

The first few Leonardo primes are
:[[3]], [[5]], [[41 (number)|41]], [[67 (number)|67]], [[109 (number)|109]], 1973, 5167, 2692537, 11405773, 126491971, 331160281, 535828591, 279167724889, 145446920496281, 28944668049352441, 5760134388741632239, 63880869269980199809, 167242286979696845953, 597222253637954133837103, ... {{OEIS|id=A145912}}

==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<sup>2</sup> such pairs.
The cycles for n≤8 are:
{|class="wikitable"
|Modulo
|Cycle
|Length
|-
|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
|}
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:
:<math>L(n)=2L(n-1)-L(n-3)</math>
{{Math proof|title=Proof|proof=<math>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)</math>}}

==Relation to Fibonacci numbers==
The Leonardo numbers are related to the [[Fibonacci number]]s by the relation <math>L(n) = 2 F(n+1) - 1, n \ge 0</math>.

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:
:<math>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</math>

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

==References==
{{reflist}}

==External links==
* {{OEIS el|sequencenumber=A001595|name=|formalname=a(n) = a(n-1) + a(n-2) + 1, with a(0) = a(1) = 1}}

{{Classes of natural numbers}}

[[Category:Integer sequences]]
[[Category:Fibonacci numbers]]
[[Category:Recurrence relations]]