Cada entero positivo puede expresarse de manera única como
una suma de números distintos de Fibonacci no consecutivos. Este resultado se
denomina teorema de Zeckendorf y la secuencia de números de Fibonacci que se
suman se denomina representación de Zeckendorf. Se llaman así en honor al
médico belga y matemático aficionado E. Zeckendorf.
Para descomponer un número en sumandos de la sucesión de
Fibonacci, se ha demostrado que el mejor procedimiento es el de ir restando al
número el término de Fibonacci mayor posible, hasta llegar a una diferencia que
sea también de Fibonacci, con lo que se termina en un cero. El teorema
correspondiente afirma que siempre se llegará a este término en las
diferencias.
Puedes consultar el tema en
Está desarrollado de forma amena y resulta interesante. Aquí
nos limitaremos a la construcción del algoritmo, para lo que repasaremos
algunas técnicas y propiedades relacionadas con la famosa sucesión.
Mayor término de
Fibonacci menor que N
Hemos recordado que el procedimiento para la representación
de Zeckendorf de un número N consiste en ir tomando el mayor término de
Fibonacci posible entre los números menores o iguales que N. El problema ahora
es cómo saber si un número pertenece a la sucesión de Fibonacci o no. Existe un
criterio bastante simple, y es:
Un número N pertenece a la sucesión de Fibonacci si y sólo si 5N2+4
o 5N2-4 es un cuadrado perfecto.
Según eso, ésta puede ser la función que devuelva VERDADERO
si un número es del tipo Fibonacci y FALSO en el caso opuesto:
Public Function esfibo(n) As Boolean
'devuelve verdadero si N es de Fibonacci
Dim f As Boolean
Dim a
f = False
a = 5 * n * n + 4
If escuad(a) Then f = True
a = 5 * n * n - 4
If escuad(a) Then f = True
esfibo = f
End Function
La función escuad
ya está explicada muchas veces en este blog. Con el comando Buscar
la puedes localizar. Dada esta función, para cualquier número N podemos definir
esta otra función, antefibo, que
devuelve el mayor número de Fibonacci que podemos restar de N. Su listado puede
ser:
Function antefibo(n)
Dim i
i = n ‘Pudiera ser que N fuera de
Fibonacci, y terminaría el proceso
While Not esfibo(i)
i = i – 1 ‘Vamos bajando números
hasta encontrar el primer “Fibonacci”
Wend
antefibo = i
End Function
Con la ayuda de esta función ya es sencillo efectuar la
descomposición de Zeckendorf. El listado siguiente recoge una función que
devuelve todos los sumandos y su número de orden en la sucesión de Fibonacci:
Function zeckendorf$(n)
Dim p, q
Dim s$
s = "" ‘Contenedor para la
solución
p = n
While p > 0
q = antefibo(p) ‘Primer sumando de
Fibonacci
p = p - q
s = s + Str$(quefibo(q)) + "% " +
Str$(q) + ", " ‘Se construye la solución
Wend
If s = "" Then s = "NO"
zeckendorf = s
End Function
Con esta función se puede construir un listado de
representaciones de este tipo. Aquí puedes observar como ejemplo los números
comprendidos entre 100 y 110.
En todos ellos, el primer sumando es 89, el número de
Fibonacci número 11, y después 13, 8 o 21, hasta llegar a 1 o 2.
Hay que observar que los números de orden nunca son
consecutivos. La razón estriba en que la suma de dos términos de Fibonacci
consecutivos da lugar a otro mayor del mismo tipo, y ya habría sido elegido
antes como sumando.
Para lo que sigue, puede ser útil incluir en el resultado el
número de sumandos, para realizar clasificaciones. Por ejemplo, en el caso de
100 y 101 quedaría:
Nos informa, para futuras búsquedas, de que 100 presenta 3
sumandos, 89+8+3, y 101 presenta 4: 89+8+3+1.
En este procedimiento, el número 1, que puede definirse como
F(2) o F(1), aparece siempre como F(2). Esto es importante en algunas
propiedades de esta representación.
Si establecemos una búsqueda según el primer dígito,
podremos clasificar los números según el número de sumandos. Vemos algunos
ejemplos:
Un sumando
Si buscamos el valor de 1 como dígito inicial del resultado,
obtendremos los mismos números de Fibonacci:
Para dos sumandos
Están publicados en http://oeis.org/A179242
Para tres:
Publicados en http://oeis.org/A179243
Así podríamos continuar, pero carece de interés.
Multiplicación de
Fibonacci
La representación de Zeckendorf da lugar a un producto muy
curioso, que consiste, dados dos números representados como suma de elementos
de Fibonacci, formar la siguiente expresión:
Lo hemos escrito de forma abreviada, pero la idea es formar
un sumatorio doble en el que cada sumando sea un número de Fibonacci cuyo
índice sea la suma de los índices de cada uno de los factores.
Por ejemplo, si deseamos multiplicar 22 por 17, según las
tablas de más arriba, 22 es una suma de números de Fibonacci de índices 8 y 2,
mientras 17 se basa en 7, 4 y 2. Podemos formar una tabla de doble entrada,
sumar índices y buscar el número de Fibonacci correspondiente:
Hemos ido sumando cada par de índices, como pueden ser 7 y
8. Su suma 15 la convertimos en F(15)=610, y así vamos procediendo con cada
par. Al final, sumamos, y nos da como resultado 854.
Esta multiplicación es claramente conmutativa, pero Donald
Knuth demostró que también es asociativa.
Es un reto comprobar esto con una función más automatizada
que la propuesta en párrafos anteriores. Los resultados del tipo propuesto no
son muy útiles para multiplicar
Los sustituiremos por un formato más sencillo, en el que
solo figurarán los índices. Omitimos el listado de la nueva función multizeck(n).
Para quien tenga curiosidad, se adjunta en el Anexo.
Con esta función es fácil comprobar con Excel la propiedad
asociativa. Lo vemos en el esquema construido al efecto:
Hemos tomado como ejemplo los números 23, 25 y 28. En primer
lugar, por separado, hemos multiplicado 23 por 25 y 25 por 28, con resultados
1293 y 1573 respectivamente. Después se ha hallado el producto de ellos por el
tercero, con el mismo resultado, 80557.
ANEXO
Función
auxiliar
Function mzeck$(n)
Dim s$
Dim p, q, m
p = n
m = 0
s = ""
While p > 0
m = m + 1
q = antefibo(p)
s = s + Str$(quefibo(q)) + ","
p = p - q
Wend
mzeck = Str$(m) + "," + s
End Function
Función
Producto
Function multizeck(a, b)
Dim u(20), v(20)
Dim s$
Dim m, p, q, i, j, z
s = mzeck(a)
m = InStr(1, s, ",")
p = Val(Left$(s, m - 1))
For i = 1 To p
s = Right(s, Len(s) - m)
m = InStr(1, s, ",")
If Len(s) > 0 Then u(i) = Val(Left$(s, m
- 1))
Next i
s = mzeck(b)
m = InStr(1, s, ",")
q = Val(Left(s, m - 1))
For i = 1 To q
s = Right(s, Len(s) - m)
m = InStr(1, s, ",")
If Len(s) > 0 Then v(i) = Val(Left$(s, m
- 1))
Next i
z = 0
For i = 1 To p
For j = 1 To q
z = z + fibo(u(i) + v(j))
Next j
Next i
multizeck = z
End Function
No hay comentarios:
Publicar un comentario