Jump to content

Leonardo number

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Sphilbrick (talk | contribs) at 15:15, 11 August 2020 (fix refs). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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]

Values

The first few Leonardo numbers are

(sequence A001595 in the OEIS)

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

  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.