Leonardo number

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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. ^ EWD797
  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. ^ EWD796a

External links

  • OEIS sequence A001595
Retrieved from "https://en.wikipedia.org/w/index.php?title=Leonardo_number&oldid=832696028"
This content was retrieved from Wikipedia : http://en.wikipedia.org/wiki/Leonardo_number
This page is based on the copyrighted Wikipedia article "Leonardo number"; it is used under the Creative Commons Attribution-ShareAlike 3.0 Unported License (CC-BY-SA). You may redistribute it, verbatim or modified, providing that you comply with the terms of the CC-BY-SA