martes, 8 de septiembre de 2020

Representación de Zeckendorf


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:




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: