En matemáticas , una secuencia de números naturales se denomina secuencia completa si cada número entero positivo puede expresarse como una suma de valores en la secuencia, utilizando cada valor como máximo una vez.
Por ejemplo, la sucesión de potencias de dos (1, 2, 4, 8, ...), base del sistema de numeración binario , es una sucesión completa; dado cualquier número natural, podemos elegir los valores correspondientes a los bits 1 en su representación binaria y sumarlos para obtener ese número (p. ej. 37 = 100101 2 = 1 + 4 + 32). Esta sucesión es mínima, ya que no se le puede quitar ningún valor sin hacer que algunos números naturales sean imposibles de representar. Ejemplos sencillos de sucesiones que no son completas incluyen los números pares , ya que la suma de números pares produce solo números pares; no se puede formar ningún número impar .
Sin pérdida de generalidad, supongamos que la secuencia a n está en orden no decreciente y definamos las sumas parciales de a n como:
Entonces las condiciones
son necesarios y suficientes para que n sea una secuencia completa. [1] [2]
Un corolario de lo anterior es que
son suficientes para que una n sea una secuencia completa. [1]
Sin embargo, hay secuencias completas que no satisfacen este corolario,por ejemplo (secuencia A203074 en la OEIS ), que consiste en el número 1 y el primer primo después de cada potencia de 2.
Las secuencias completas incluyen:
De la misma manera que las potencias de dos forman una secuencia completa debido al sistema de numeración binario, de hecho, cualquier secuencia completa puede utilizarse para codificar números enteros como cadenas de bits. La posición de bit más a la derecha se asigna al primer miembro más pequeño de la secuencia; la siguiente posición más a la derecha, al siguiente miembro; y así sucesivamente. Los bits establecidos en 1 se incluyen en la suma. Estas representaciones pueden no ser únicas.
Por ejemplo, en el sistema aritmético de Fibonacci , basado en la secuencia de Fibonacci, el número 17 se puede codificar de seis maneras diferentes:
La forma máxima anterior siempre usará F 1 y siempre tendrá un cero final. La codificación completa sin el cero final se puede encontrar en (secuencia A104326 en la OEIS ). Al omitir el uno final, la codificación para 17 anterior ocurre como el término 16 de A104326. La forma mínima nunca usará F 1 y siempre tendrá un cero final. La codificación completa sin el cero final se puede encontrar en (secuencia A014417 en la OEIS ). Esta codificación se conoce como la representación Zeckendorf .
En este sistema numérico, cualquier subcadena "100" puede ser reemplazada por "011" y viceversa debido a la definición de los números de Fibonacci. [5] La aplicación continua de estas reglas traducirá del máximo al mínimo, y viceversa. El hecho de que cualquier número (mayor que 1) pueda ser representado con un 0 terminal significa que siempre es posible sumar 1, y dado que, para que 1 y 2 puedan ser representados en la codificación de Fibonacci, la completitud se sigue por inducción .
