En matemáticas , una secuencia de números naturales se llama secuencia completa si cada entero positivo puede expresarse como una suma de valores en la secuencia, utilizando cada valor como máximo una vez.
Por ejemplo, la secuencia de potencias de dos (1, 2, 4, 8, ...), la base del sistema numérico binario , es una secuencia completa; dado cualquier número natural, podemos elegir los valores correspondientes a los 1 bits en su representación binaria y sumarlos para obtener ese número (por ejemplo, 37 = 100101 2 = 1 + 4 + 32). Esta secuencia es mínima, ya que no se le puede quitar ningún valor sin hacer que algunos números naturales sean imposibles de representar. Los ejemplos simples de secuencias que no están completas incluyen los números pares , ya que sumar números pares produce sólo números pares; no se pueden formar números impares .
Condiciones de integridad
Sin pérdida de generalidad, suponga que la secuencia a n está en orden no decreciente y defina las sumas parciales de a n como:
- .
Entonces las condiciones
son necesarios y suficientes para que una n sea una secuencia completa. [1] [2]
Un corolario de lo anterior establece 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 consta del número 1 y el primer primo después de cada potencia de 2.
Otras secuencias completas
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 sigue del postulado de Bertrand . [1]
- La secuencia de números prácticos que tiene 1 como primer término y contiene todas las demás potencias de 2 como subconjunto. [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 el ( n + 2) nd número de Fibonacci menos 1 (ver Fibonacci_numbers # Second_identity ).
Aplicaciones
Así como las potencias de dos forman una secuencia completa debido al sistema numérico binario, de hecho, cualquier secuencia completa puede usarse para codificar 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; el siguiente a la derecha al siguiente miembro; y así. Los bits establecidos en 1 se incluyen en la suma. Estas representaciones pueden no ser únicas.
Codificación de Fibonacci
Por ejemplo, en el sistema aritmético de Fibonacci , basado en la secuencia de Fibonacci, el número 17 se puede codificar de seis formas diferentes:
- 110111 (F 6 + F 5 + F 3 + F 2 + F 1 = 8 + 5 + 2 + 1 + 1 = 17, forma máxima)
- 111001 (F 6 + F 5 + F 4 + F 1 = 8 + 5 + 3 + 1 = 17)
- 111010 (F 6 + F 5 + F 4 + F 2 = 8 + 5 + 3 + 1 = 17)
- 1000111 (F 7 + F 3 + F 2 + F 1 = 13 + 2 + 1 + 1 = 17)
- 1001001 (F 7 + F 4 + F 1 = 13 + 3 + 1 = 17)
- 1001010 (F 7 + F 4 + F 2 = 13 + 3 + 1 = 17, forma mínima, como se usa en la codificación de Fibonacci )
La forma máxima anterior siempre usará F 1 y siempre tendrá uno al final. La codificación completa sin el final se puede encontrar en (secuencia A104326 en la OEIS ). Al eliminar el último, la codificación de 17 anterior aparece como el término 16 de A104326. La forma mínima nunca usará F 1 y siempre tendrá un cero al final. La codificación completa sin el cero final se puede encontrar en (secuencia A014417 en la OEIS ). Esta codificación se conoce como representación de Zeckendorf .
En este sistema de numeración, 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) se pueda representar con un terminal 0 significa que siempre es posible sumar 1, y dado que, para 1 y 2 se pueden representar en la codificación de Fibonacci, la completitud sigue a la inducción .
Ver también
Referencias
- ^ a b c d Honsberger, R. Gemas matemáticas III. Washington, DC: Matemáticas. Assoc. Amer., 1985, págs. 123-128.
- ^ Marrón, JL (1961). "Nota sobre secuencias completas de números enteros". The American Mathematical Monthly . 68 (6): 557–560. doi : 10.2307 / 2311150 . JSTOR 2311150 .
- ^ SS Pillai, "Una función aritmética relativa a los números primos", Annamalai University Journal (1930), págs. 159-167.
- ^ Srinivasan, AK (1948), "Números prácticos" (PDF) , Current Science , 17 : 179–180, MR 0027799.
- ^ Stakhov, Alexey. "Las principales operaciones de la aritmética de Fibonacci" . Archivado desde el original el 24 de enero de 2013 . Consultado el 11 de septiembre de 2016 ., Museo de la Armonía y Sección Dorada . Consultado originalmente: 27 de julio de 2010.
enlaces externos
- Weisstein, Eric W. "Secuencia completa" . MathWorld .