Leonardotal

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

$L(n)\equiv \{\begin{array}{cc}1& \text{if }n=0\\ 1& \text{if }n=1\\ L(n-1)+L(n-2)+1& \text{if }n>1\end{array}$

Edsger W. Dijkstra använde dem som en integrerad del av sin släthetssorterande algoritm,

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, … Mall:OEIS

Relation till Fibonaccital

Leonardotal är relaterade till Fibonaccital av relationen $L(n)=2F(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{{\phi }^{n+1}-{\psi }^{n+1}}{\phi -\psi }-1=\frac{2}{\sqrt{5}}({\phi }^{n+1}-{\psi }^{n+1})-1=2F(n+1)-1$

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

Källor

• Mall:Enwp

Externa länkar

• Mall:SloanesRef