Sucesiones completas

En esta entrada abordaré un tema interesante, y es el de la posibilidad de que los elementos de una sucesión de números naturales, finita o infinita, generen otros números, a partir de sumas, con o sin repetición.

Ya traté ese tema en algunas entradas antiguas, como

https://hojaynumeros.blogspot.com/2010/02/frobenius-y-los-mcnuggets.html

“Frobenius y los mcnuggets”, en la que trataba el problema de las monedas necesarias para alcanzar una cantidad y el número de Frobenius.

https://hojaynumeros.blogspot.com/2012/11/descomposicion-de-un-numero-segun-una.html

En esta entrada se trataba de generar un número a partir de una lista de ellos.

En ambos casos las sucesiones eran finitas, y al sumar los elementos se podían repetir los sumandos.

También se relacionaba algo con lo que pretendo presentar ahora, la entrada sobre algoritmos voraces o codiciosos:

https://hojaynumeros.blogspot.com/2024/09/algoritmos-codiciosos-para-sumas.html

Sucesión completa

Desarrollaré aquí el tipo de sucesión más eficaz para generar todos los números naturales, el de sucesión completa.

Una sucesión de números naturales se llama completa cuando cualquier otro número natural se puede escribir como suma de elementos de esa sucesión sin repetir ninguno.

El ejemplo básico más popular es el de las potencias de 2, que da lugar al sistema binario de representación de los números. En efecto, la sucesión 1, 2, 4, 8, 16, … permite representar cualquier número como suma de algunos términos, sin repetición. La forma de conseguirlo es similar a la de los algoritmos codiciosos que traté en la entrada referenciada más arriba.

Vemos un ejemplo: representar el número 53:

Buscamos el término de la sucesión más cercano a 53 y menor que él, que es el 32, tomamos nota y restamos: 53-32=21. Reiteramos: 21-16=5, 5-4=1, con lo que obtenemos 53=32+16+4+1, que da lugar a la representación binaria 110101.

Este ejemplo nos abre camino para caracterizar las sucesiones completas. Podemos dar tres condiciones para que una sucesión sea de este tipo:

·    El primer término ha de ser 1, a₁=1

·   Aunque no es imprescindible, pero sí algo operativo, la sucesión debe presentar un orden creciente.

·    Si llamamos s_n a la suma de los n primeros términos de la sucesión, se debe cumplir: s_n-1 ≥ a_n-1 para todo n ≥ 1

La primera condición es imprescindible para poder generar todos los números y que los algoritmos tengan parada. Por ejemplo, los números pares no son completos, pues nunca pueden generar un impar.

La segunda se incluye para que tengan sentido los algoritmos.

La tercera es fundamental, porque garantiza que se pueda avanzar en descubrir sumandos hasta llegar, si es necesario al 1.

Seguimos el proceso del 53 visto más arriba. Dado el número N, deberemos encontrar el mayor elemento de la sucesión que sea menor que N, en el ejemplo 32. La diferencia 21 se ha de poder tratar del mismo modo, con lo que s_n-1 ha de ser suficiente para ello, es decir, s_n ≥ a_n-1. Piénsese en el caso 63, en el que 63-32=31, y debe poder ser generado por los elementos anteriores, es decir por s_n-1, y de ahí la condición s_n ≥ a_n-1.

Si no se cumple esta condición, la sucesión no es completa. Por ejemplo, la sucesión de potencias de cuatro, 1, 4, 16, 64, …no la cumple, y, por ejemplo, no puede generar el número 70, porque 70-64=6, y 6 no se puede formar con 1 y 4. Aquí la suma 1+4+16 no es suficiente.

La sucesión de potencias de 2 la cumple, porque s_n=2ⁿ-1, y da lugar a la representación binaria. Esto se logra porque no se admiten repeticiones en los sumandos. También es minimal, pues si eliminamos un término de ella, habrá números naturales que no se puedan representar. Por ejemplo, si elimino el 4, no podré representar el 6. Otra característica es que la representación es única, algo que no se contempla en las definiciones.

Existe una condición suficiente que puede sustituir a la tercera, y es que 2a_k ≥ a_k+1 para k≥1. El ejemplo de las potencias de 2 la cumple, pero falta ver su suficiencia. Lo razonamos con el ejemplo del N=53. La primera operación fue buscar el término menor que 53 más cercano a él, y fue el 32. Restamos y nos resultó 21 para proseguir. Lo vemos en general:

N estará entre a_k y a_k+1, pero a_k+1 estará entre a_k y 2a_k, luego tendremos: a_k ≤ N ≤ a_k+1 ≤ 2a_k. Restando a_k se verificará:

0 ≤ N - a_k ≤ a_k

Por tanto, la siguiente diferencia (en el ejemplo, el 21) será menor que a_k, y se podrá seguir el algoritmo con un término menor, hasta llegar a 1.

Ejemplo reciente

En una entrada anterior vimos la sucesión “catering perezoso”, formada por los términos de fórmula

Sus primeros términos son 1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, 67, 79, 92, 106, 121, 137, 154, 172, 191, 211, 232, 254, 277, 301, 326, 352, 379, …https://oeis.org/A000124

Es evidente que cumple 2a_k ≥ a_k+1.

2a_k - a_k+1 = 2(k(k+1)/2+1)-(k+1)(k+2)/2-1 = (k+1)(k-(k+2)/2)+1 =(k+1)(k/2-1)+1, y esta diferencia es positiva o cero para k>1

Podemos afirmar que esta sucesión es completa, como se afirma en la página en la que está publicada. Según esto, cualquier número natural es suma de algunos de sus términos tomados sin repetición. He efectuado sencillas comprobaciones con mi hoja de cálculo partlista

 (Ver https://www.hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#reprenum)

He elegido el número 62 al azar, y deseo generarlo con los términos de esta sucesión 1, 2, 4, 7, 11, 16, 22, 29, 37. He concretado en la hoja que no se repitan sumandos, y me ha devuelto estos resultados:

No es de extrañar que resulten siete soluciones, porque en estos procesos no tiene que existir solución única.

 
Sucesión de Fibonacci

Esta sucesión es claramente completa. Basta recordar que es creciente y en ella a_k+1 = a_k+a_k-1, luego a_k+1 < a_k+a_k = 2a_k, que es condición suficiente para la completitud.

Existe una descomposición basada en esta propiedad, y es la de Zeckendorf, que consiste en ir restando a un número N el mayor número de Fibonacci posible. Es interesante, y acudo a ella con frecuencia. Puedes profundizar en el tema leyendo mi entrada https://hojaynumeros.blogspot.com/2020/09/representacion-de-zeckendorf.html y descubrir en qué consiste la multiplicación de Fibonacci.

Por ejemplo, esta es la representación de Zeckendorf del número 75:

75 = F(10)+F(7)+F(5)+F(3) = 55+13+5+2

No es el único desarrollo. Con nuestra herramienta Cartesius (https://www.hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#cartesius) se puede conseguir otro. Estas son las condiciones:

xrango=5 

xt=1..55    

xt=filtro(fibonacci)    

suma=75  

creciente 

no repite  

Y este el resultado:

Nos devuelve el ya conocido, 2+5+13+55, que es el desarrollo minimal, pero nos ofrece otro: 75=34+21+13+5+2

Números primos con la unidad

Si a la sucesión de números primos le adjunto a(1) = 1, resulta una sucesión completa. Es creciente, comienza en 1 y cumple que 2p(k) ≥ p(k+1). Esta afirmación se basa en el Postulado de Bertrand, que afirma, entre otras formulaciones, esta desigualdad. Por ejemplo, con la hoja partlista, podemos generar el número 35 con esta sucesión, y resulta:

Es evidente que esta descomposición da lugar a muchas soluciones distintas.

Se pueden encontrar más ejemplos de sucesiones completas, pero con estos se comprende bien el concepto. Otros que he encontrado son demasiado particulares y no son muy interesantes.