Secuencia completa

En matemáticas , una sucesión de números naturales se denomina sucesión completa si cada entero positivo puede expresarse como una suma de valores de la sucesión, utilizando cada valor como máximo una vez.

Por ejemplo, la secuencia de potencias de dos (1, 2, 4, 8, ...), base del sistema numérico binario , es una secuencia 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; ₂ = 1 + 4 + 32). Esta secuencia es mínima, ya que no se puede eliminar ningún valor sin que algunos números naturales resulten imposibles de representar. Ejemplos sencillos de secuencias 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:

${\displaystyle s_{n}=\sum _{m=0}^{n}a_{m}}$.

Entonces las condiciones

${\displaystyle a_{0}=1\,}$

${\displaystyle s_{k-1}\geq a_{k}-1{\text{ para todo }}k\geq 1}$

son ambos necesarios y suficientes para que una _n sea una secuencia completa. ^{[ 1 ] [ 2 ]}

Una consecuencia de lo anterior establece que

${\displaystyle a_{0}=1\,}$

${\displaystyle 2a_{k}\geq a_{k+1}{\text{ para todo }}k\geq 0}$

son suficientes para que _n sea una secuencia completa. ^{[ 1 ]}

Sin embargo, existen 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:

• La secuencia del número 1 seguida de los números primos (estudiada por SS Pillai ^{[ 3 ]} y otros); esto se deduce del postulado de Bertrand . ^{[ 1 ]}
• La secuencia de números prácticos cuyo primer término es 1 y que contiene como subconjunto todas las demás potencias de 2. ^{[ 4 ]} (secuencia A005153 en la OEIS )
• Los números de Fibonacci , así como los números de Fibonacci con cualquier número eliminado. ^{[ 1 ]} Esto se deduce de la identidad de que la suma de los primeros n números de Fibonacci es la${\displaystyle (n+2)º}$Número de Fibonacci menos 1.

Así como las potencias de dos forman una secuencia completa debido al sistema numérico binario, cualquier secuencia completa puede usarse para codificar números enteros como cadenas de bits. La posición del bit más a la derecha se asigna al primer elemento, el más pequeño, de la secuencia; la siguiente posición a la derecha, al siguiente elemento; y así sucesivamente. Los bits establecidos en 1 se incluyen en la suma. Estas representaciones pueden no ser únicas.

• numeración de Ostrowski

• Weisstein, Eric W. "Secuencia completa" . MathWorld .