Jump to content

Leonardo number

From Wikipedia, the free encyclopedia

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] [4]

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

Values

[edit]

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

[edit]

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:

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

[edit]
  • The following equation applies:
Proof

Relation to Fibonacci numbers

[edit]

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

[edit]
  1. ^ "E.W.Dijkstra Archive: Fibonacci numbers and Leonardo numbers. (EWD 797)". www.cs.utexas.edu. Retrieved 2020-08-11.
  2. ^ 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)
  3. ^ "E.W.Dijkstra Archive: Smoothsort, an alternative for sorting in situ (EWD 796a)". www.cs.utexas.edu. Retrieved 2020-08-11.
  4. ^ "Leonardo Number - GeeksforGeeks". www.geeksforgeeks.org. 18 October 2017. Retrieved 2022-10-08.
[edit]