Número de Leonardo

Los números de Leonardo son una secuencia de números dados por la recurrencia:

${\displaystyle L(n)={\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] los utilizó como parte integral de su algoritmo smoothsort ^[2] y también los analizó con cierto detalle. ^{[3] [4]}

Un primo de Leonardo es un número de Leonardo que también es primo .

Los primeros números de Leonardo son

1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, ... (secuencia A001595 en la OEIS )

Los primeros números primos de Leonardo son

3 , 5 , 41 , 67 , 109 , 1973, 5167, 2692537, 11405773, 126491971, 331160281, 535828591, 279167724889, 145446920496281, 28944668049352441, 5760134388741632239, 63880869269980199809, 167242286979696845953, 597222253637954133837103, ... (sequence A145912 in la OEIS )

Los números de Leonardo forman un ciclo en cualquier módulo n≥2. Una forma sencilla de verlo es:

• Si un par de números módulo n aparece dos veces en la secuencia, entonces hay un ciclo.
• Si asumimos que la afirmación principal es falsa, usando la afirmación anterior, entonces implicaría que hay infinitos pares distintos de números entre 0 y n-1, lo cual es falso ya que hay n ² pares de este tipo.

Los ciclos para n≤8 son:

El ciclo siempre termina en el par (1,n-1), ya que es el único par que puede preceder al par (1,1).

• Se aplica la siguiente ecuación:

${\displaystyle L(n)=2L(n-1)-L(n-3)}$

Los números de Leonardo están relacionados con los números de Fibonacci por la relación . ${\displaystyle L(n)=2F(n+1)-1,n\geq 0}$

A partir de esta relación es sencillo derivar una expresión en forma cerrada para los números de Leonardo, análoga a la fórmula de Binet para los números de Fibonacci:

${\displaystyle 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}$

donde la proporción áurea y son las raíces del polinomio cuadrático . ${\displaystyle \varphi =\left(1+{\sqrt {5}}\right)/2}$${\displaystyle \psi =\left(1-{\sqrt {5}}\right)/2}$ ${\displaystyle x^{2}-x-1=0}$

• Secuencia OEIS A001595