This article relies excessively on references to primary sources. Please improve this article by adding secondary or tertiary sources. Find sources: "Leonardo number" – news · newspapers · books · scholar · JSTOR (July 2017) (Learn how and when to remove this message) |
The Leonardo numbers are a sequence of numbers given by the recurrence:
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, ... (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)
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:
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:
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.
- "Leonardo Number - GeeksforGeeks". www.geeksforgeeks.org. 18 October 2017. Retrieved 2022-10-08.
External links
- OEIS sequence A001595
Classes of natural numbers | |||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||