Serie de Fibonacci y teorema de Zeckendorf

Serie de Fibonacci

La secuencia de Fibonacci es una sucesión infinita de números naturales en la que cada elemento se obtiene mediante la suma de los dos elementos inmediatamente anteriores a éste:

Para poder generar la secuencia, necesitamos partir, pues, de dos elementos iniciales. Éstos son el 0 y el 1:

Por lo tanto, los primeros 10 elementos (considerando el f0 = 0 como el elemento primero) de la serie serían:

 

Las aplicaciones y curiosidades de esta serie son numerosas. Para profundizar en ellas puedes distraerte con los siguientes enlaces:

• Sucesión de Fibonacci (Wikipedia ESP)
  
• Fibonacci Number (Wikipedia ENG)
• La sucesión de Fibonacci y la razón áurea (Derivando)
  

 

Teorema de Zeckendorf

Hemos comentado que la serie de Fibonacci presenta una gran cantidad de curiosidades y aplicaciones. Una de éstas es el Teorema de Zeckendorf, que en resumen nos viene a decir que cualquier número natural puede descomponerse como una suma de números naturales que pertenecen a la serie de Fibonacci no consecutivos.

Teniendo en cuenta la serie de los 10 primeros elementos de la serie de Fibonacci que hemos visto más arriba, lo que nos viene a decir el teorema de Zeckendorf podemos verlo en los siguientes ejemplos

De nuevo, para ahondar en este tema y ver explicaciones más detalladas y demostraciones, echad un ojo a los siguientes enlaces:

• Zeckendorf's Theorem (Wikipedia ENG)
  
• La sucesión de Fibonacci, el teorema de Zeckendorf y un poemario magistral (Artículo de Marta Macho Stadler para el Cuaderno de Cultura Científica de la Universidad del País Vasco)

 

Programando que es gerundio

Vamos a ver cómo programar en R un par de funciones para calcular tanto la sucesión de Fibonacci para un número dado de elementos, así como la descomposición de Zeckendorf para un numero natural cualquiera.

Los elementos de R que se van a utilizar son:

•  Vectores
• declaración:  vector <- c()
• añadir elemento (e) al vector (vector):   vector <- append(vector, e)
• ordenar vector en orden descendente:  sort(vector, decreasing = TRUE)
• subconjunto de elementos con los índices de aquellas posiciones del vector que cumplen una determinada condición:  which(vector <=> condición)
• sumatorio de elementos del vector:  sum(vector)
• longitud (número de elementos) del vector: length(vector)
  
• Bucle for:  for(i in 1:n){}
• Bloque condicional: if(condición1){}else if(condición2){}else{}
• Bucle condicional: while(condición){}
  

 

Serie de Fibonacci

Construiremos una función (fibonacci) que puede recibir tres parámetros

• items = número de elementos de la serie a generar (por defecto 8)
• n1 = valor del primer elemento de la serie (por defecto 0)
• n2 = valor del segundo elemento de la serie (por defecto 1)

La función se construye dentro de un bucle for que itera sobre i desde el valor 1 hasta el valor recibido en el parámetro items.

Los dos primeros valores de la serie, como hemos visto antes, son los valores prefijados a 0 y 1. Sin embargo, al construir la función permitiendo modificar los dos elementos iniciales nos permitirá crear variantes de la serie de Fibonacci con diferentes elementos de partida.

Es decir, para los elementos de la iteración 1 y 2, los valores serán los indicados en los parámetros n1 y n2, y para el resto de elementos (el else) se construirá mediante la suma de los dos elementos anteriores del vector: fib[i-1] + fib[i-2]

# ------------------------------------------------ # fibonacci # ------------------------------------------------ fibonacci <- function(items = 8 ,n1 = 0 ,n2 = 1) { for(i in 1:items){ if(i==1){ fib <- c(n1) } else if(i==2){ fib <- append(fib, n2) } else{ fib <- append(fib, fib[i-1]+fib[i-2]) } } return(fib) }
 

 Si probamos esta función obtenemos los siguientes resultados: 

• fibonacci(10)
•  0  1  1  2  3  5  8 13 21 34
• fibonacci(30)  
• 0      1      1      2      3      5      8     13     21     34     55     89    144    233    377    610    987   1597   2584   4181   6765  10946  17711  28657  46368  75025 121393 196418 317811 514229

Probemos a generar la secuencia de 10 elementos, pero cuyos parámetros iniciales son diferentes:

• fibonacci(10,2,3)
• 2   3   5   8  13  21  34  55  89 144

 

Descomposición según el teorema de Zeckendorf

Vista la función que nos permite obtener la serie de Fibonacci para un determinado número de elementos (que utilizaremos ahora), pasamos a ver cómo programar la obtención de un vector cuyos elementos representen la descomposición de Zeckendorf para un número dado.

Crearemos por tanto una función (zeckendorf) que reciba un único parámetro:

• val = valor numérico para el cual queremos obtener la descomposición de Zeckendorf

El algoritmo para obtener esta descomposición es bastante sencillo:

1. Buscamos una serie de Fibonacci cuyos elementos sean menores o iguales que el valor que queremos descomponer. Por ejemplo, si queremos obtener la descomposición del número 6, la serie (0,1,1,2,3,5,8) nos valdría, pues en este caso la descomposición de Zeckendorf para el número 6 sería (5,1), elementos presentes en la serie de Fibonacci para la longitud que hemos determinado.
2. De la serie que tenemos, buscamos el mayor número menor o igual que nuestro número a descomponer.
3. Una vez lo tenemos, restamos a nuestro número el valor de Fibonacci que hemos seleccionado.
4. Buscamos ahora el siguiente mayor valor de la serie que sea menor o igual que dicho valor resultante.
5. ... repetimos hasta que tengamos todos los valores.

Y la programación que vamos a realizar es, en esencia, esto mismo:

En un primer bucle while buscaremos una serie de Fibonacci lo suficientemente larga como para incluir el mayor elemento que sea menor o igual que nuestro número que queremos descomponer:

• Para conseguir esto, la condición de salida del bucle es que tengamos una serie (el vector fib) en el que algún elemento sea mayor que el número que estamos buscando.
• Mientras esto no se cumpla, seguiremos iterando incrementando la longitud del vector fib con la serie de Fibonacci, para el cual solicitaremos a la función fibonacci que cada vez nos devuelva una serie con 10 elementos más que la anterior. 

Una vez tenemos el vector con una serie de Fibonacci lo suficientemente grande para extraer de ella los elementos de la descomposición, realizamos otro bucle while para el cual comparamos que la suma de los elementos del vector resultante (zeck) que estamos rellenando a cada paso sea en efecto el valor del nnúmero a descomponer.

• Para poder extraer estos elementos, en cada iteración buscamos cuáles (which) elementos del vector son mayores que la cantidad restante de la suma de elementos que nos falta para obtener el valor resultado esperado.
• Este which nos devuelve un vector con los indices de las posiciones del vector consultado. Si lo ordenamos (sort) en orden descencente, el primer elemento de este vector ordenado será la posición del vector en la serie de Fibonacci que representa el siguiente elemento de la descomposición de Zeckendorf que estamos buscando.
• Tras obtener el elemento, actualizamos el valor actual de la suma y repetimos el bucle hasta obtener todos los elementos cuya suma equivalen el valor objetivo.

Aquí está el código con la función:

 # ------------------------------------------------ # zeckendorf # ------------------------------------------------ zeckendorf <- function(val) { zeck <- c() zsum = 0 fib <- fibonacci(8) n <- 1 # Encontrar serie de Fibonacci adecuada while(length(which(fib > val))==0){ fib <- fibonacci(n*10) n <- n+1 } # Obtener descomposición de Zeckendorf while(zsum < val) { zfib <- which(fib <= (val-zsum)) zfib <- sort(zfib, decreasing = TRUE) zeck <- append(zeck, fib[zfib[1]]) zsum <- zsum + fib[zfib[1]] } return(zeck) }

Pongamos a prueba nuestra función:

• zeckendorf(8)
• 8
  
• Siendo la serie de Fibonacci:  (0 1 1 2 3 5 8)
• zeckendorf(7)
• 5  2
• Siendo la serie de Fibonacci:  (0 1 1 2 3 5 8)
• zeckendorf(88)
• 610 233 34 8 3
• Siendo la serie de Fibonacci: (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610)

 

Resumen

Hemos visto dos ejemplos sencillitos que nos permiten poner en práctica la creación y manipulación de vectores, su ordenación y la consulta de sus elementos por índice.

Además, hemos puesto en práctica los tres bucles lógicos que más suelen utilizarse (for, if, while).

Como en casi cualquier problema que se programe, esta solución no es única, y puede abordarse de muchas maneras. Igualmente, en otros lenguajes de programación se puede realizar un desarrollo bastante similar en función de las funciones internas que tenga cada lenguaje para la manipulación lógica de objetos y valores, pero lo importante aquí es saber volcar un razonamiento lógico a la hora de implementar lo que queremos hacer para que la máquina nos de el resultado esperado.

Cualquier comentario, replanteamiento del código o duda es más que bienvenido.