Leonardo number
![]() | This article relies too much on references to primary sources. (July 2017) |
The Leonardo numbers are a sequence of numbers given by the recurrence:
Edsger W. Dijkstra[1] used them as an integral part of his smoothsort algorithm,[2] and also analyzed them in some detail.[3]
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, ... (sequence A001595 in the OEIS)
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, ... (sequence A145912 in the OEIS)
Expressions[]
- The following equation applies:
Proof
Relation to Fibonacci numbers[]
The Leonardo numbers are related to the Fibonacci numbers by the relation .
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:
where the golden ratio and are the roots of the quadratic polynomial .
References[]
- ^ "E.W.Dijkstra Archive: Fibonacci numbers and Leonardo numbers. (EWD 797)". www.cs.utexas.edu. Retrieved 2020-08-11.
- ^ Dijkstra, Edsger W. Smoothsort – an alternative to sorting in situ (EWD-796a) (PDF). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (transcription)
- ^ "E.W.Dijkstra Archive: Smoothsort, an alternative for sorting in situ (EWD 796a)". www.cs.utexas.edu. Retrieved 2020-08-11.
External links[]
- OEIS sequence A001595
Categories:
- Integer sequences
- Fibonacci numbers
- Recurrence relations