En matemáticas , una cadena de suma para calcular un entero positivo n puede estar dada por una secuencia de números naturales que comienza con 1 y termina con n , de modo que cada número de la secuencia es la suma de dos números anteriores. La longitud de una cadena de suma es el número de sumas necesarias para expresar todos sus números, que es uno menos que la cardinalidad de la secuencia de números. [1]
Como ejemplo: (1,2,3,6,12,24,30,31) es una cadena de suma para 31 de longitud 7, ya que
Las cadenas de suma se pueden utilizar para la exponenciación de cadenas de suma . Este método permite realizar la exponenciación con exponentes enteros utilizando un número de multiplicaciones igual a la longitud de una cadena de suma para el exponente. Por ejemplo, la cadena de suma para 31 conduce a un método para calcular la potencia 31 de cualquier número n usando solo siete multiplicaciones, en lugar de las 30 multiplicaciones que se obtendrían con la multiplicación repetida y ocho multiplicaciones con exponenciación al cuadrado :
Calcular una cadena de suma de longitud mínima no es fácil; una versión generalizada del problema, en la que se debe encontrar una cadena que forme simultáneamente cada uno de una secuencia de valores, es NP-completa. [2] No existe ningún algoritmo conocido que pueda calcular una cadena de suma mínima para un número determinado con garantías de tiempo razonable o uso reducido de memoria. Sin embargo, se conocen varias técnicas para calcular cadenas relativamente cortas que no siempre son óptimas. [3]
Una técnica muy conocida para calcular cadenas de suma relativamente cortas es el método binario , similar a la exponenciación por elevación al cuadrado . En este método, se obtiene recursivamente una cadena de suma para el número, a partir de una cadena de suma para . Si es par, se puede obtener en una única suma adicional, como . Si es impar, este método utiliza dos sumas para obtenerlo, calculando y luego sumando uno. [3]
El método factorial para encontrar cadenas de suma se basa en la factorización prima del número a representar. Si tiene un número como uno de sus factores primos, entonces se puede obtener una cadena de suma para comenzando con una cadena para y luego concatenando en ella una cadena para , modificada multiplicando cada uno de sus números por . Las ideas del método factorial y del método binario se pueden combinar en el método m-ario de Brauer eligiendo cualquier número (independientemente de si divide a ), construyendo recursivamente una cadena para , concatenando una cadena para (modificada de la misma manera que arriba) a obtener y luego agregar el resto. Refinamientos adicionales de estas ideas conducen a una familia de métodos llamados métodos de ventana deslizante . [3]
Denotemos el más pequeño para que exista una cadena de suma de longitud que calcule . Se sabe que
¿Dónde está el peso de Hamming (el número de unos) de la expansión binaria de ? [4]
Se puede obtener una cadena de suma para a partir de una cadena de suma para incluyendo una suma adicional , de la cual se sigue la desigualdad en las longitudes de las cadenas para y . Sin embargo, esto no siempre es una igualdad, ya que en algunos casos puede tener una cadena más corta que la obtenida de esta forma. Por ejemplo , observado por Knuth. [5] Incluso es posible que for tenga una cadena más corta que , de modo que ; el más pequeño para el que sucede esto es , [6], seguido de , y así sucesivamente (secuencia A230528 en OEIS ).
Una cadena de Brauer o cadena de suma de estrellas es una cadena de suma en la que cada una de las sumas utilizadas para calcular sus números utiliza el número inmediatamente anterior. Un número de Brauer es un número para el cual una cadena de Brauer es óptima. [5]
Brauer demostró que
¿Dónde está la longitud de la cadena de estrellas más corta? Para muchos valores de n , y en particular para n < 12509 , son iguales: [7] l ( n ) = l * ( n ) . Pero Hansen demostró que hay algunos valores de n para los cuales l ( n ) ≠ l * ( n ) , como n = 2 6106 + 2 3048 + 2 2032 + 2 2016 + 1 que tiene l * ( n ) = 6110, l ( norte ) ≤ 6109 . El n más pequeño es 12509.
La conjetura de Scholz (a veces llamada conjetura de Scholz-Brauer o conjetura de Brauer-Scholz ), llamada así en honor a Arnold Scholz y Alfred T. Brauer), es una conjetura de 1937 que afirma que
Se sabe que esta desigualdad es válida para todos los números de Hansen, una generalización de los números de Brauer; Neill Clift comprobó por computadora que todos son Hansen (mientras que 5784689 no lo es). [6] Clift verificó además que, de hecho, para todos . [5]