Numero di Leonardo

Da Wikipedia, l'enciclopedia libera.

I numeri di Leonardo sono una sequenza di numeri dati dalla relazione:

 
  L(n):=  
  \begin{cases}
    1               & \mbox{se } n = 0; \\
    1               & \mbox{se } n = 1; \\
    L(n-1)+L(n-2)+1 & \mbox{se } n > 1. \\
   \end{cases}

Edsger W. Dijkstra[1] li ha utilizzati come parte integrante del suo algoritmo di ordinamento Smoothsort, analizzandoli anche in alcuni dettagli[2].

Essi sono legati ai numeri di Fibonacci dalla relazione L(n) = 2 * F(n+1) - 1, n \ge 0. Data la formula tipo Binet:

L(n) = 2 * \left( \frac{\Phi^{(n+1)} - \phi^{(n+1)}}{\Phi - \phi} \right) - 1 = \left( \frac{2}{\sqrt 5} \right) * (\Phi^{(n+1)} - \phi^{(n+1)}) - 1

dove \Phi=(1+\sqrt 5)/2 e \phi=(1-\sqrt 5)/2 sono le radici di x^2-x-1=0

I primi numeri di Leonardo sono[3]:

1,\;1,\;3,\;5,\;9,\;15,\;25,\;41,\;67,\;109,\;177,\;287,\;465,\;753,\;1219,\;1973,\;3193,\;5167,\;8361, \ldots

Note[modifica | modifica sorgente]

  1. ^ EWD797
  2. ^ EWD796a
  3. ^ (EN) Sequenza A001595 in On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.