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:

:

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}

Edsger W. Dijkstra{{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}} used them as an integral part of his smoothsort algorithm,{{Cite EWD|796a|Smoothsort – an alternative to sorting in situ}} and also analyzed them in some detail.{{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}}{{Cite web |title=Leonardo Number - GeeksforGeeks |url=https://www.geeksforgeeks.org/leonardo-number/ |access-date=2022-10-08 |website=www.geeksforgeeks.org|date=18 October 2017}}

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

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, ... {{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 n2 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:

:L(n)=2L(n-1)-L(n-3)

{{Math proof|title=Proof|proof=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)}}

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{\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

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.

Leonardo polynomials

The Leonardo polynomials L_{n}(x) is defined by Kalika Prasad, Munesh Kumari (2024): The Leonardo polynomials and their algebraic properties. Proc. Indian Natl. Sci. Acad. https://doi.org/10.1007/s43538-024-00348-0

:L_{n+2}(x)=xL_{n+1}(x)+L_{n}(x)+x with L_{0}(x) = 1, L_{1}(x)=2x-1.

Equivalently, in homogeneous form, the Leonardo polynomials can be writtenas

:L_{n+3}(x)= (x+1)L_{n+2}(x)-(x-1)L_{n+1}(x)-L_{n}(x):

where L_{0}(x)=1, L_{1}(x)=2x-1 and L_{2}(x)=2x^2+1.

Examples of Leonardo polynomials

:L_{0}(x)=1 \,

:L_{1}(x)=2x-1\,

:L_{2}(x)=2x^2+1\,

:L_{3}(x)=2x^3+4x-1\,

:L_{4}(x)=2x^4 + 6x^2 + 1 \,

:L_{5}(x)=2x^5+8x^3+6x-1 \,

:L_{6}(x)=2x^6+10x^4+12x^2+1\,

:L_{7}(x)=2x^7+12x^5+20x^3+8x-1 \,

:L_{8}(x)=2 x^8+14 x^6+30 x^4+20 x^2+1 \,

:L_{9}(x)=2 x^9+16 x^7+42 x^5 + 40x^3 + 10x-1 \,

:L_{10}(x)=2 x^{10}+18 x^8+56 x^6+70 x^4+30 x^2+1\,

:L_{11}(x)=2 x^{11}+20 x^9+72 x^7+112 x^5+70 x^3+12x-1 \,

Substituting x=1 in the above polynomials gives the Leonardo numbers and setting x=k gives the k-Leonardo numbers.Kalika Prasad, Munesh Kumari (2025): The generalized k-Leonardo numbers: a non-homogeneous generalization of the Fibonacci numbers, Palestine Journal of Mathematics, 14.

References

{{reflist}}

Cited

1. P. Catarino, A. Borges (2019): On Leonardo numbers. Acta Mathematica Universitatis Comenianae, 89(1), 75-86. Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1005/799

2. K. Prasad, R. Mohanty, M. Kumari, H. Mahato (2024): Some new families of generalized k-Leonardo and Gaussian Leonardo Numbers, Communications in Combinatorics and Optimization, 9 (3), 539-553. https://comb-opt.azaruniv.ac.ir/article_14544_6844cc9ba641d31cafe5358297bc0096.pdf

3. M. Kumari, K. Prasad, H. Mahato, P. Catarino (2024): On the generalized Leonardo quaternions and associated spinors, Kragujevac Journal of Mathematics 50 (3), 425-438. https://imi.pmf.kg.ac.rs/kjm/pub/kjom503/kjm_50_3-6.pdf

4. K. Prasad, H. Mahato, M. Kumari, R. Mohanty: On the generalized Leonardo Pisano octonions, National Academy Science Letters 47, 579–585. https://link.springer.com/article/10.1007/s40009-023-01291-2

5. Y. Soykan (2023): Special cases of generalized Leonardo numbers: Modified p-Leonardo, p-Leonardo-Lucas and p-Leonardo Numbers, Earthline Journal of Mathematical Sciences. https://www.preprints.org/frontend/manuscript/a700d41e884b69f92bc8eb6cf7ff1979/download_pub

6. Y. Soykan (2021): Generalized Leonardo numbers, Journal of Progressive Research in Mathematics. https://core.ac.uk/download/pdf/483697189.pdf

7. E. Tan, HH Leung (2023): ON LEONARDO p-NUMBERS, Journal of Combinatorial Number Theory. https://math.colgate.edu/~integers/x7/x7.pdf