Cadena de adición

En matemáticas , una cadena de sumas para calcular un entero positivo n puede estar dada por una secuencia de números naturales que comienza en 1 y termina en n , de manera que cada número de la secuencia es la suma de dos de los números anteriores. La longitud de una cadena de sumas 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

2 = 1 + 1

3 = 2 + 1

6 = 3 + 3

12 = 6 + 6

24 = 12 + 12

30 = 24 + 6

31 = 30 + 1

Las cadenas de suma se pueden usar para la exponenciación en cadena de suma . Este método permite realizar la exponenciación con exponentes enteros usando 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 la exponenciación por elevación al cuadrado :

n ² = n × n

n ³ = n ² × n

n ⁶ = n ³ × n ³

n ¹² = n ⁶ × n ⁶

n ²⁴ = n ¹² × n ¹²

n ³⁰ = n ²⁴ × n ⁶

n ³¹ = n ³⁰ × n

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 los valores de una secuencia, es NP-completa . ^{[ 2 ]} No se conoce ningún algoritmo que pueda calcular una cadena de suma mínima para un número dado con garantías de un tiempo de ejecución razonable o un bajo consumo 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, una cadena de suma para el número${\displaystyle n}$se obtiene recursivamente, a partir de una cadena de suma para${\displaystyle n'=\lfloor n/2\rfloor }$. Si${\displaystyle n}$es par, se puede obtener en una sola suma adicional, como${\displaystyle n=n'+n'}$. Si${\displaystyle n}$es extraño, este método utiliza dos sumas para obtenerlo, calculando${\displaystyle n-1=n'+n'}$y luego añadir uno. ^{[ 3 ]}

El método factorial para encontrar cadenas de suma se basa en la factorización prima del número${\displaystyle n}$estar representado. Si${\displaystyle n}$tiene un número${\displaystyle p}$como uno de sus factores principales, entonces una cadena adicional para${\displaystyle n}$se puede obtener comenzando con una cadena para${\displaystyle n/p}$y luego concatenarle una cadena para${\displaystyle p}$, modificado multiplicando cada uno de sus números por${\displaystyle n/p}$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${\displaystyle m}$(independientemente de si divide o no)${\displaystyle n}$), construyendo recursivamente una cadena para${\displaystyle \lfloor n/m\rfloor }$, concatenando una cadena para${\displaystyle m}$(modificado de la misma manera que arriba) para obtener${\displaystyle m\lfloor n/m\rfloor }$y luego sumar el resto. Refinamientos adicionales de estas ideas conducen a una familia de métodos llamados métodos de ventana deslizante . ^{[ 3 ]}

Dejar${\displaystyle l(n)}$denota el más pequeño${\displaystyle s}$de modo que exista una cadena adicional de longitud${\displaystyle s}$que calcula${\displaystyle n}$Se sabe que $${\displaystyle \log _{2}n+\log _{2}\nu (n)-2.13\leq l(n)\leq \log _{2}n+\nu (n)-1,}$$$${\displaystyle l(n)\leq \log _{2}n+{\bigl (}1+o(1){\bigr )}{\frac {\log _{2}n}{\log _{2}\log _{2}n}},}$$ dónde${\displaystyle \nu (n)}$es el peso de Hamming (el número de unos) de la expansión binaria de${\displaystyle n}$. ^{[ 4 ]}

Se puede obtener una cadena adicional para${\displaystyle 2n}$de una cadena de adición para${\displaystyle n}$al incluir una suma adicional${\displaystyle 2n=n+n}$de lo cual se deduce la desigualdad${\displaystyle l(2n)\leq l(n)+1}$sobre las longitudes de las cadenas para${\displaystyle n}$y${\displaystyle 2n}$Sin embargo, esto no siempre es una igualdad, ya que en algunos casos${\displaystyle 2n}$puede tener una cadena más corta que la obtenida de esta manera. Por ejemplo,${\displaystyle l(382)=l(191)=11}$, observado por Knuth. ^{[ 5 ]} Incluso es posible que${\displaystyle 2n}$tener una cadena más corta que${\displaystyle n}$, de modo que${\displaystyle l(2n)<l(n)}$; el más pequeño${\displaystyle n}$por qué sucede esto es${\displaystyle n=375494703}$, ^{[ 6 ]} que es seguido por${\displaystyle 602641031}$,${\displaystyle 619418303}$y así sucesivamente (secuencia A230528 en el OEIS ) .

Una cadena de Brauer o cadena de suma en estrella 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

l ^* (2 ^norte −1) ≤ norte − 1 + l ^* ( norte )

donde​${\displaystyle l^{*}}$es la longitud de la cadena estelar más corta. ^{[ 7 ]} Para muchos valores de${\displaystyle n}$y en particular para${\displaystyle n<12509}$, son iguales: ^{[ 8 ]} l ( n )  = l ^* ( n )  . Pero Hansen demostró que hay algunos valores de n para los cuales l ( n )  ≠ l ^* ( n )  , como n  =  2 ⁶¹⁰⁶  +  2 ³⁰⁴⁸  +  2 ²⁰³²  +  2 ²⁰¹⁶  +  1 que tiene l ^* ( n )  =  6110, l ( n )  ≤  6109 . El n más pequeño de este tipo es 12509.

La conjetura de Scholz (a veces llamada conjetura de Scholz-Brauer o Brauer-Scholz , nombrada en honor a Arnold Scholz y Alfred T. Brauer), es una conjetura de 1937 que afirma que

${\displaystyle l(2^{n}-1)\leq n-1+l(n).}$

Se sabe que esta desigualdad se cumple para todos los números de Hansen, una generalización de los números de Brauer; Neill Clift comprobó mediante ordenador que todos${\displaystyle n\leq 5784688}$son Hansen (mientras que 5784689 no lo es). ^{[ 6 ]} Clift verificó además que, de hecho${\displaystyle l(2^{n}-1)=n-1+l(n)}$a pesar de${\displaystyle n\leq 64}$. ^{[ 5 ]}

• Cadena de suma y resta
• Cadena de adición vectorial
• Cadena Lucas

• Secuencia OEIS A003313 (Longitud de la cadena de adición más corta para n) . Tenga en cuenta que el "1" inicial no se cuenta (por lo que el elemento n.° 1 de la secuencia es 0).
• F. Bergeron, J. Berstel, S. Brlek "Cálculo eficiente de cadenas de suma"