Leonardotal

Från Wikipedia
Hoppa till: navigering, sök

Leonardotal är en heltalsföljd som ges av återkommande:

 
  L(n) \equiv 
  \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[1] använde dem som en integrerad del av sin släthetssorterande algoritm,[2] och har dessutom analyserat dem i detalj.[3]

Beräkning av andra ordningens återkommande förhållande rekursivt och utan memoisation kräver L(n)-beräkningar för den n:te termen i serien.

De första Leonardotalen är:

1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, 13529, 21891, 35421, 57313, 92735, 150049, 242785, 392835, 635621, 1028457, 1664079, 2692537, 4356617, 7049155, 11405773, 18454929, 29860703, 48315633, 78176337, … (talföljd A001595 i OEIS)

Relation till Fibonaccital[redigera | redigera wikitext]

Leonardotal är relaterade till Fibonaccital av relationen L(n) = 2 F(n+1) - 1, n \ge 0.

Ur denna relation är det enkelt att härleda ett uttryck i sluten form för Leonardotal, analogt med Binets formel för Fibonaccital:

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

där det gyllene snittet \varphi = \left(1 + \sqrt 5\right)/2 och \psi = \left(1 - \sqrt 5\right)/2 är rötterna till det kvadratiska polynomet x^2 - x - 1 = 0.

Källor[redigera | redigera wikitext]

Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia, Leonardo number, 22 december 2013.
  1. ^ EWD797
  2. ^ Dijkstra, Edsger W. Smoothsort – an alternative to sorting in situ (EWD-796a). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin.  (Fel i uttryck: Okänt interpunktionstecken "["xx/EWD796a.PDF original; Fel i uttryck: Okänt interpunktionstecken "["xx/EWD796a.html transcription)
  3. ^ EWD796a

Externa länkar[redigera | redigera wikitext]