viernes, 23 de octubre de 2020

Poligoriales

Los números poligoriales se definen de forma similar a los factoriales, pero en lugar de multiplicar números naturales consecutivos, lo hacen con los números poligonales.

Un número poligorial de orden k equivale al producto de los primeros números poligonales de orden k. Por ejemplo, 180 es poligorial de orden 3, porque es el producto de los cuatro primeros números triangulares: 180=1*3*6*10. 518400 lo es de orden 4, porque equivale al producto de los cuadrados 1, 4, 9, 16, 25 y 36.

En el caso de los factoriales los factores son números naturales, y no hay que calcularlos previamente al producto, pero en el caso de los poligoriales, cada factor posee su propia fórmula, que hay que evaluar. Como trabajamos con números poligonales, es útil usar la misma fórmula en todos los órdenes, aunque luego exista la posibilidad de simplificación en cada caso. Es la siguiente:


En ella k es el orden y n la longitud de un lado, que es la variable que se recorre al plantear el producto.

Con esta fórmula no es difícil encontrar una función que devuelva el valor de un poligorial de parámetros n y k:

Public Function poligorial(n, k)

Dim i, j, p

 If k < 2 Then poligorial = 1: Exit Function ‘No se definen poligonales de dos lados

p = 1 ‘Inicio del producto de poligonales

For i = 1 To n

p = p * i * (i * (k - 2) - k + 4) / 2 ‘Cada factor se evalúa con la fórmula para poligonales

Next i

poligorial = p

End Function

 

Casos particulares

A continuación recorreremos algunos órdenes, obteniendo el listado de los primeros términos y alguna propiedad o curiosidad. Comenzamos por los triangulares. Con la función de arriba, es fácil obtener esa lista de los primeros números poligoriales triangulares:


Un listado más completo lo tienes en http://oeis.org/A006472. Como en esa página figuran casi todos los casos, nos limitaremos a incluir el enlace en cada caso.

No es difícil encontrar una fórmula para el poligorial triangular:

Se puede expresar de otra forma, pero así es fácil calcularla con hoja de cálculo:

Si, por ejemplo, N figura en la celda I4, su poligorial triangular sería =FACT(I4)*FACT(I4+1)/2^I4. Puedes probarlo con cualquier elemento de la tabla:

FACT(7)*FACT(7+1)/2^7=1587600

En la dirección enlazada puedes consultar propiedades combinatorias cuya naturaleza no las hace aptas para ser tratadas con una simple hoja de cálculo.

En esa página figura una aproximación para estos poligoriales:

a(n) ~ 4*Pi*n^(2*n)/(2^n*exp(2*n)).

No es muy buena, como puedes comprobar en la siguiente tabla de comparación:


Poligoriales cuadrados

Este orden es mucho más simple en su generación que el anterior, ya que cada elemento es un producto de cuadrados consecutivos, luego es, en sí mismo, otro cuadrado, que coincide con el cuadrado de un factorial. Lo ves en la tabla:

Por tanto, su fórmula será:

El listado de los primeros junto con muchas propiedades combinatorias lo puedes consultar en http://oeis.org/A001044

 

Fórmula general en PARI

Ha llegado el momento de pensar en los poligoriales como productos de sumas, ya que los poligonales equivalen a sumas cuyos elementos tienen la expresión 1+(k-2)*(i-1). En efecto, los triangulares suman números enteros i, como 10=1+2+3+4, por lo que para k=3 suman 1+(3-2)*(i-1)=1+i-1=i. Los cuadrados suman impares: 1+3+5+7+9=25=5^2, con lo que para k=4 queda 1+(4-2)*(i-1)=1+2i-2=2i-1

Según estas consideraciones, que se basan en que todo poligonal equivale a k-2 números triangulares sumados con su índice (ver mi publicación “Números y formas” - http://www.hojamat.es/publicaciones/numform.pdf), estos sumandos 1+(k-2)*(i-1) se pueden extender a todos los poligoriales. En nuestra figura lo puedes entender mejor:



En ella se observa que en cada especie de arco están incluidas (k-2)*(i-1)+1 unidades: 3*0+1, 3*1+1, 3*2+1, 3*3+1…

Según esto, la función en PARI que devuelve el poligorial(n,k) puede ser:

polygorial(n,k)={my(i,j);prod(i=1,n,sum(j=1,i,1+(k-2)*(j-1)))}

Expresa muy bien la idea de que el poligorial es un producto de sumas.

Puedes comprobar, por ejemplo:

Polygorial(6,4)=518400

Polygorial(9,3)=2571912000

 

Poligoriales pentagonales

Con la fórmula en PARI (que tiene traducción sencilla para VBASIC) ya podemos encontrar poligoriales de cualquier orden. Si hacemos k=5 obtendremos los de orden pentagonal (o pentagoriales):

1, 5, 60, 1320, 46200, 2356200, 164934000, 15173928000, 1775349576000, 257425688520000,…

Su listado y propiedades los encontrarás en http://oeis.org/A084939

 

Resto de poligoriales

Una vez conseguido un procedimiento general de obtención de términos, el resto es casuística o propiedades combinatorias no abordables con hoja de cálculo. Un texto sencillo para ampliar el tema es

https://web.archive.org/web/20140617132401/http://danieldockery.com/res/math/polygorials.pdf

En la página OEIS están incluidos más órdenes de poligoriales. A continuación se insertan algunos listados conseguidos de forma personal con nuestra función poligorial seguidos de su comprobación en OEIS:

Hexagonales

Hemos usado el código PARI

polygorial(n,k)={my(i,j);prod(i=1,n,sum(j=1,i,1+(k-2)*(j-1)))}

for(i=1,10,print1(polygorial(i,6),", "))

 

1, 6, 90, 2520, 113400, 7484400, 681080400, 81729648000, 12504636144000, 2375880867360000,…

Esta sucesión está incluida en http://oeis.org/A000680, sin destacar que se trata de poligoriales hexagonales hasta el apartado de fórmulas.

Una forma de obtener estos números es mediante la expresión

Igualmente, es fácil encontrarlos mediante la recursión a(n)=a(n-1)*C(2n,2), siendo C el número de combinaciones o un binomial (en Excel, COMBINAT). En la siguiente tabla generamos estos números mediante fórmula directa y por recursión (anterior por las combinaciones de 2n sobre 2):

Con las herramientas presentadas podríamos seguir creando poligoriales.

Heptagoriales:

1, 7, 126, 4284, 235620, 19085220, 2137544640, 316356606720, 59791398670080, 14050978687468800,… http://oeis.org/A084940

Octogoriales:

1, 8, 168, 6720, 436800, 41932800, 5577062400, 981562982400, 220851671040000, 61838467891200000,… http://oeis.org/A084941

Y así se puede seguir hasta el orden deseado. Todos tienen propiedades combinatorias interesantes, que no tienen cabida aquí.




lunes, 12 de octubre de 2020

Números de Saint-Exupéry

Reciben este nombre en la página OEIS (http://oeis.org) aquellos números que coinciden con el producto de los tres lados de una terna pitagórica. El primero, como era de esperar, es 60, que es el producto de 3, 4 y 5, elementos de la terna más sencilla que conocemos. El segundo, 480, es el producto de sus dobles, 6*8*10. Siguen infinitos de este tipo (porque también es infinito el número de ternas), y nuestro objetivo en esta entrada es analizar métodos para encontrarlos.

La idea sencilla es ir construyendo ternas y después tomar nota del producto de sus lados. El inconveniente reside en que así no podemos averiguar si un número cualquiera es de este tipo o no. Si nos preguntan si lo es 238772, no vamos a formar todas las ternas hasta llegar a él. Por eso, como en otras ocasiones, recurriremos a una función que nos responda a esa pregunta.

Algoritmo con fuerza bruta

Esta es la aproximación a un problema con la solemos comenzar en este blog. Fingimos no saber nada de la cuestión y emprendemos una búsqueda sin apoyarnos en ninguna propiedad. Usaremos la siguiente función:

Public Function Saint_Exupery(n)

Dim a, b, c, p, r

Dim s$

a = 3: b = 4: c = 5: p = 60 ‘Iniciamos valores con la terna (3, 4, 5)

s = "" ‘Recogerá soluciones

r = Sqr(n) ‘Tope de búsquedas

While a <= r And s = ""

b = a + 1 ‘Segundo cateto

p = a * b * c ‘Posible número de Saint_Exupery

While b <= r And s = ""

c = n / a / b ‘Tercer cateto

If a ^ 2 + b ^ 2 = c ^ 2 Then s = Str$(a) + Str$(b) + Str$(c) ‘Es terna pitagórica y se publica

b = b + 1

Wend

a = a + 1

Wend

Saint_Exupery = s

End Function

Con esta función podemos responder a la pregunta de si 238772 es del tipo buscado, y la respuesta es que no, porque devuelve una cadena vacía. Más adelante veremos una razón más sencilla, y es que no es múltiplo de 60.

También con ella podemos encontrar los primeros números de Saint_Exupery:

En la tabla siguiente, cada número viene acompañado de la terna de la que es producto:

 

Indirectamente, esta es una forma de ordenar ternas por el producto de sus lados.

No es este un algoritmo rápido. Para llegar a estos resultados se han necesitado 1m y 20s. Pronto veremos una simplificación.

Estos números ya están publicados en OEIS, de donde hemos obtenido su definición:

A057096                            Saint-Exupéry numbers: ordered products of the three sides of Pythagorean triangles.

60, 480, 780, 1620, 2040, 3840, 4200, 6240, 7500, 12180, 12960, 14760, 15540, 16320, 20580, 21060, 30720, 33600, 40260, 43740, 49920, 55080, 60000, 65520, 66780, 79860, 92820, 97440, 97500, 103680, 113400, 118080, 120120, 124320, 130560, 131820, 164640

(http://oeis.org/A057096)


Segundo algoritmo

En el algoritmo de fuerza bruta hemos obviado el hecho de que los lados de la terna han de ser divisores del número de Saint-Exupéry buscado. Si tenemos esto en cuenta, la búsqueda se simplifica bastante. Podemos intentar esta variante:

Public Function Saint2(n)

Dim a, b, c

jueves, 1 de octubre de 2020

Rotaciones por bloques de cifras



Unas curiosidades no muy estudiadas se producen en números cuando la mitad derecha de sus cifras se permuta con el bloque de la izquierda sin alterar el orden interno de cada bloque. Por ejemplo, 24133 es primo, pero si rotamos sus cifras por bloques, es decir, que el 33 se permuta con el 24, se convierte en 33124, que es un cuadrado. Igual le ocurre a 24547, primo, que al rotar bloques también se convierte en cuadrado: 47524.

Otros números son primos y al rotar siguen siendo primos, como 1123 y 2311. Otros permanecen cuadrados, o triangulares, y así podemos seguir recorriendo casos. Se comprende que si el número de cifras es par, la rotación es completa, y, si es impar, se deja invariante la cifra del centro. Esta operación la rotularemos como función “rotar”. Así:

ROTAR(27365)=65327
ROTAR(7654)=5476

Con la experiencia acumulada en el uso de la hoja de cálculo, no es complicado diseñar esta función “rotar”. Para ello necesitamos dos funciones que hemos usado varias veces en este blog, como son NUMCIFRAS y TROZOCIFRAS. 

Sus listados los puedes consultar en nuestra entrada 


La primera cuenta las cifras de un número, y TROZOCIFRAS devuelve las cifras del número entre dos extremos prefijados.

El listado de la función ROTAR puede ser:

function rotar(n)
dim nc,nc1,r

'rota las cifras alrededor del centro si su número es impar
nc=numcifras(n)
if nc=1 then rotar=n:exit function ‘Es de una sola cifra
if nc mod 2 = 1 then ‘Número impar de cifras
nc1=(nc+1)/2
r=trozocifras(n,1,nc1-1)*10^nc1+trozocifras(n,nc1,nc1)*10^(nc1-1)+trozocifras(n,nc1+1,nc)
else
nc1=nc/2 ‘Número par de cifras
r=trozocifras(n,1,nc1)*10^nc1+trozocifras(n,nc1+1,nc)
end if
rotar=r
end function

Así, por ejemplo:

ROTAR(198262)=262198

Lo puedes comprobar si implementas la función en tu equipo.

Búsquedas

Sobre esta operación realizaremos algunas búsquedas de curiosidades. Eliminaremos los números terminados en 0, porque llevan a resultados con números diferentes de cifras, que no resultan atractivos, y tampoco usaremos números invariantes a la operación de rotar, como puede ser 2347234. Los primeros eliminados se caracterizarán por N MOD 10 = 0, y los segundos porque ROTAR(N)=N. Los ceros interiores también pueden alterar el número de cifras, pero omitiremos esta dificultad.

Veremos a continuación algunos casos concretos:

Cuadrado que se convierte en cuadrado

Dado que en nuestras búsquedas podemos alcanzar números grandes, es útil disponer de la función ROTAR en una versión para PARI, que es el instrumento que usamos cuando la hoja de cálculo no satisface las exigencias que le imponemos. El listado que sigue se limita a traducir paso por paso el algoritmo usado para hoja de cálculo:

numcif(n)=1+logint(n,10)
cutdigit(a, p, q)=(a%10^q)\10^(p-1)
rotar(n)={my(nc=numcif(n),r=0,nc1=0);if(nc==1,r=n);
if(nc%2==1&&nc<>1,nc1=(nc+1)/2;r=cutdigit(n,1,nc1-1)*10^nc1+cutdigit(n,nc1,nc1)*10^(nc1-1)+cutdigit(n,nc1+1,nc));
if(nc%2==0,nc1=nc/2;r=cutdigit(n,1,nc1)*10^nc1+cutdigit(n,nc1+1,nc));return(r)}
for(i=10,10^8,if(issquare(i),j=rotar(i);if(i%10<>0&&j<>i&&issquare(j),print1(i,", "))))

Obtendremos:

144, 169, 441, 961, 16641, 25281, 41616, 81225, 1002001, 1004004, 1006009, 1008016, 1214404, 2253001, 2256004, 2259009, 3297856, 4004001, 4008004, 4044121, 6255001, 8567329, 9006001, 14010049, 20412324, 23242041, 32410249, 56040196, 81649296, 82410084, 92968164,…

Hemos indicado  que algunos ejemplos con ceros interiores pueden alterar el número de cifras con la función ROTAR.


Primo que se convierte en primo

En el anterior código en PARI podemos sustituir las llamadas a la función issquare por la de isprime, con lo que obtendremos resultados similares, de números primos que siguen siendo primos con una rotación de bloques. Los primeros resultados son:


13, 17, 31, 37, 71, 73, 79, 97, 107, 113, 149, 157, 167, 179, 199, 311, 337, 347, 359, 389, 701, 709, 733, 739, 743, 751, 761, 769, 907, 937, 941, 953, 967, 971, 983, 991, 1103, 1109, 1123, 1163, 1181, 1193, 1301, 1303, 1319, 1321, 1327, 1361, 1777, 1783, 1907, 1913, 1931, 1933, 1949, 1951, 1979,…

Entre ellos figura el 73, el número de Sheldon, presentado en la serie de televisión “Big Bang”. No solo se convierte en el primo 37, sino que también se intercambian sus números de orden como primos:
73=Primo(21) y 37=Primo(12).

Entre ellos también figuran años primos del siglo XX y de los siglos con número de orden par.


Caso primo-cuadrado

Volvemos al caso que presentamos en los primeros párrafos, el de los primos que se convierten en cuadrados al rotar. Al igual que en el caso anterior, bastará usar las funciones isprime y issquare en el lugar adecuado. Resultará este listado:


61, 163, 487, 691, 1621, 2137, 2179, 2467, 2953, 3631, 9601, 21157, 21319, 24001, 24133, 24547, 25087, 36559, 36637, 36901, 49411, 49801, 56101, 56527, 64303, 69997, 84631, 121579, 124669, 129769, 136309, 156217, …

Entre ellos aparecen los que solo sufren un intercambio de una cifra, como 69997.

Si seguimos jugando con las dos funciones issquare y isprime comprobaremos que la situación es reversible, como era de esperar, pero con el orden cambiado.

 Siguiendo nuestro criterio de no cansar, y habiendo repetido el procedimiento, sólo se incluyen algunos listados más por si los lectores desean reproducirlos:


Triangular - triangular

153, 351, 5565, 6105, 6555, 53956, 56953, 81003, 128778, 490545, 778128, 1252153, 1532125, 1613706, 7063161, 7401628, 7966036, 11061456, 14561106, 16287778, 22301181, 23787753, 32534211, 42113253, 44006271, 49109005, 50717556, 55466778, 67785546, 75565071, 77532378, 77781628,…

En ellos se advierte el efecto de los ceros interiores, como en 81003, que alteran el efecto de la rotación.

Oblongo – Oblongo

20306, 162006, 2504306, 22122912, 29122212, 44602362, 65068422, 84226506,…

Resultan muy pocos, pero esto es frecuente en este tipo de números.










lunes, 21 de septiembre de 2020

Producto de cifras con incremento



El día 14 de mayo de 2020, @AnecdotesMaths publicó en Twitter la siguiente igualdad:

315 = (3+4)(1+4)(5+4)

En este blog estamos atentos a desarrollos a partir de cualquier curiosidad que encontremos, por lo que dedicaremos esta entrada a las igualdades del tipo

abc… = (a+k)(b+k)(c+k)…, donde a,b, c… son cifras de un número y k una constante entera.

El subrayado del primer miembro indica que son cifras del número y no producto.

Generalizamos a continuación la igualdad leída en Twitter.

El valor de k está acotado por el 10, ya que si aumentamos esta cantidad tendríamos:

(a+10)(b+10)(c+10)…>10*10*10*…> abc… ,

Sería imposible la igualdad pedida.

Para iniciar las búsquedas, necesitamos una función que nos devuelva las cifras de un número por separado. Puedes consultar los códigos para VBasic de Excel y Calc en la siguiente entrada de este blog


Allí se explican las funciones NUMCIFRAS (número de cifras), CIFRA, (una cifra sola) y TROZOCIFRA (devuelve varias cifras)

En PARI puedes usar:

cutdigit(a, p, q)=(a%10^q)\10^(p-1)

Es equivalente a TROZOCIFRAS, ya que devuelve las cifras entre los órdenes p y q, con lo que si son iguales equivalen a una sola cifra.

Para el total de cifras, PARI permite usar esta expresión:

#Vec(Str(N))

Equivale a “cardinal del vector formado por la expresión en texto de N”

Con estas funciones, no es difícil encontrar ejemplos como los deseados.


Versión para Excel y Calc

Hemos elegido la siguiente función para encontrar los números que poseen la propiedad deseada:

Function ciframasconst(n)
Dim i, j, k, p


k = 0  ‘Esta constante, si es mayor que 0, indicará éxito
For i = 0 To 9 ‘La variable i es la constante que se suma a las cifras
p = 1 ‘Inicio del producto de cifras
For j = 1 To numcifras(n)
p = p * (cifra(n, j) + i) ‘Se construye el producto de cifras aumentadas
Next j
If p = n Then k = i ‘Si el producto coincide con el número, tomamos nota de la constante sumada
Next i
ciframasconst = k ‘Si k>0, se da la propiedad
End Function


La función devuelve la constante que se suma a las cifras, de forma que si vale 0, es señal de que no se cumple la propiedad, y, en caso contrario, devuelve el valor de la constante que se suma. En la siguiente tabla figuran los primeros números que cumplen lo pedido y, junto a ellos, la constante que se suma:

12          2
18          1
24          2
35          2
50          5
56          2
90          6
120        4
210        5
315        4
450        5
780        5
840        6
1500      5

Vemos que, efectivamente, 315 cumple la igualdad para k=4, es decir, que 315=(3+4)(1+4)(5+4)

Otro ejemplo sería el 840, que la cumple para k=6:

840=(8+6)(4+6)(0+6)=14*10*6=840

Con esta función podemos extender la búsqueda hasta donde deseemos, recordando que solo ensayamos valores de k entre 0 y 10:

Los primeros números obtenidos son:

12, 18, 24, 35, 50, 56, 90, 120, 210, 315, 450, 780, 840, 1500, 3920, 4320, 4752, 7744, 16500,
24960,…

Están ya publicados en http://oeis.org/A055482

A055482                            There exists some k>0 such that n is the product of (k + digits of n).            
12, 18, 24, 35, 50, 56, 90, 120, 210, 315, 450, 780, 840, 1500, 3920, 4320, 4752, 7744, 16500, 24960, 57915, 59400, 60480, 91728, 269500, 493920, 917280, 1293600, 2419200, 3386880, 34992000, 266378112, 317447424, 1277337600, 3714984000, 14948388000, 48697248600, 460522782720, 896168448000

Versión en PARI

El algoritmo usado se traslada fácilmente al lenguaje PARI:

cutdigit(a, p, q)=(a%10^q)\10^(p-1)
prod_cifr_inc(n,k)=my(m=#Vec(Str(n)),p=1,i);for(i=1,m,p=p*(cutdigit(n,i,i)+k));p
for(i=1,10^6,for(k=1,9,if(i==prod_cifr_inc(i,k),print1(i,", "))))

Da los mismos resultados:







Primera variante

En lugar de producto de cifras incrementadas podemos usar la suma de sus cuadrados, es decir, que se cumpla la igualdad

 abc…=(a+k)^2+(b+k)^2+(c+k)^2

La acotación para k puede ser más amplia, por ejemplo, la raíz cuadrada del número N dividido entre el número de cifras. Así, 6754 podría alcanzar la cota 41 en la base de cada sumando:

6754>4*41^2=6724

El uso de valores de k de dos cifras complicaría una cuestión que solo es lúdica, por lo que seguiremos dándole valores entre 1 y 9. Dejamos abierta una ampliación de valores.

Un pequeño cambio en la función ciframascons nos devolvería los primeros números que cumplen esta condición:

20          2
40          2
106        3
114        4
118        2
121        5
146        3
158        2
171        4
230        7
274        5
325        7
413        9
469        6
481        8

Así, 325 coincide con la suma de los cuadrados de las cifras incrementadas estas en 7 unidades:

325=(3+7)^2+(2+7)^2+(5+7)^2=100+81+144

Con cubos

Si en lugar de cuadrados usamos cubos, obtenemos este otro listado:

141        1
251        1
440        2
532        2
560        1
1036      3
1307      3
1471      3
2240      6
2313      6
2609      3
2917      3
3016      6
3878      3
4799      3

Tomamos como ejemplo 3878, que con la constante igual a 3 cumple:

3878=(3+3)^3+(8+3)^3+(7+3)^3+(8+3)^3=216+1331+1000+1331

Dejamos como ampliación de quien nos lea la búsqueda de casos distintos. Por ejemplo, se podrían usar trozos de cifras en lugar de cifras aisladas.




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