Cadena de adición

En matemáticas , una cadena de adición 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 sea la suma de dos números anteriores. La longitud de una cadena de adición 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]

Ejemplos

A modo de ejemplo: (1,2,3,6,12,24,30,31) es una cadena de adición 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 adición se pueden utilizar para la exponenciación de cadenas de adición . 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 adición para el exponente. Por ejemplo, la cadena de adición para 31 conduce a un método para calcular la potencia 31 de cualquier número n utilizando solo siete multiplicaciones, en lugar de las 30 multiplicaciones que se obtendrían de la multiplicación repetida, y ocho multiplicaciones con exponenciación por cuadrado :

n2 = n × n^​

n3 = n2 × n^​​

n6 = n3 × n3^​​​

n12 = n6 × n6^​​​

n24 = n12 × n12^​​​

n30 = n24 × n6^​​​

n31 = n30 × n^​​

Métodos para calcular cadenas de adición

Calcular una cadena de adición 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 adición mínima para un número dado 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 adición relativamente cortas es el método binario , similar a la exponenciación por cuadrado . En este método, una cadena de adición para el número se obtiene recursivamente, a partir de una cadena de adición 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 una. ^[3] ${\displaystyle n}$ ${\displaystyle n'=\lfloor n/2\rfloor }$ ${\displaystyle n}$ ${\displaystyle n=n'+n'}$ ${\displaystyle n}$ ${\displaystyle n-1=n'+n'}$

El método factorial para encontrar cadenas de adición se basa en la factorización prima del número que se va a representar. Si tiene un número como uno de sus factores primos, entonces se puede obtener una cadena de adición para comenzando con una cadena para , y luego concatenando sobre 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 (sin importar si divide a ), construyendo recursivamente una cadena para , concatenando una cadena para (modificada de la misma manera que antes) para obtener , y luego sumando el resto. Refinamientos adicionales de estas ideas conducen a una familia de métodos llamados métodos de ventana deslizante . ^[3] ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle n/p}$ ${\displaystyle p}$ ${\displaystyle n/p}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle \lfloor n/m\rfloor }$ ${\displaystyle m}$ ${\displaystyle m\lfloor n/m\rfloor }$

Longitud de la cadena

Sea el más pequeño de modo que exista una cadena de adición de longitud que calcule . Se sabe que ${\displaystyle l(n)}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle n}$

${\displaystyle \log _{2}(n)+\log _{2}(\nu (n))-2.13\leq l(n)\leq \log _{2}(n)+\log _{2}(n)(1+o(1))/\log _{2}(\log _{2}(n))}$,

donde es el peso de Hamming (el número de unos) de la expansión binaria de . ^[4] ${\displaystyle \nu (n)}$ ${\displaystyle n}$

Se puede obtener una cadena de adición para a partir de una cadena de adición para incluyendo una suma adicional , de la que se sigue la desigualdad sobre 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 manera. Por ejemplo, , observado por Knuth. ^[5] Incluso es posible para tener una cadena más corta que , de modo que ; el más pequeño para el que esto sucede es , ^[6] que es seguido por , , y así sucesivamente (secuencia A230528 en la OEIS ). ${\displaystyle 2n}$ ${\displaystyle n}$ ${\displaystyle 2n=n+n}$ ${\displaystyle l(2n)\leq l(n)+1}$ ${\displaystyle n}$ ${\displaystyle 2n}$ ${\displaystyle 2n}$ ${\displaystyle l(382)=l(191)=11}$ ${\displaystyle 2n}$ ${\displaystyle n}$ ${\displaystyle l(2n)<l(n)}$ ${\displaystyle n}$ ${\displaystyle n=375494703}$ ${\displaystyle 602641031}$ ${\displaystyle 619418303}$

Cadena Brauer

Una cadena de Brauer o cadena de adición en estrella es una cadena de adición 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. 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 ⁶¹⁰⁶  + 2 ³⁰⁴⁸  + 2 ²⁰³²  + 2 ²⁰¹⁶  + 1 que tiene l ^* ( n ) = 6110, l ( n ) ≤ 6109 . El n más pequeño de estos es 12509.

Conjetura de Scholz

La conjetura de Scholz (a veces llamada conjetura de Scholz-Brauer o conjetura de Brauer-Scholz ), llamada así por 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 verificó por computadora que todos son Hansen (mientras que 5784689 no lo es). ^[6] Clift verificó además que, de hecho, para todos los . ^[5] ${\displaystyle n\leq 5784688}$ ${\displaystyle l(2^{n}-1)=n-1+l(n)}$ ${\displaystyle n\leq 64}$

Véase también

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

Referencias

1. DE Knuth, El arte de la programación informática , vol. 2, "Algoritmos seminuméricos", sección 4.6.3, tercera edición, 1997
2. Downey, Peter; Leong, Benton; Sethi, Ravi (1981), "Cálculo de secuencias con cadenas de adición", SIAM Journal on Computing , 10 (3): 638–646, doi :10.1137/0210047Varios otros artículos afirman que encontrar la cadena de adición más corta para un solo número es NP-completo y citan este artículo, pero no afirman ni prueban tal resultado.
3. Otto, Martin (2001), Cadenas de adición y sustracción de Brauer (PDF) , Diplomarbeit, Universidad de Paderborn, archivado desde el original (PDF) el 2013-10-19 , consultado el 2013-10-19.
4. Schönhage, Arnold (1975), "Un límite inferior para la longitud de las cadenas de adición", Theoretical Computer Science , 1 (1): 1–12, doi :10.1016/0304-3975(75)90008-0
5. Guy (2004) pág. 169
6. Clift, Neill Michael (2011). "Cálculo de cadenas de adición óptimas" (PDF) . Computing . 91 (3): 265–284. doi : 10.1007/s00607-010-0118-8 .
7. Achim Flammenkamp, ​​Cadenas de adición más cortas

• Brauer, Alfred (1939). "Sobre cadenas de adición". Boletín de la American Mathematical Society . 45 (10): 736–739. doi : 10.1090/S0002-9904-1939-07068-7 . ISSN  0002-9904. MR  0000245.
• Richard K. Guy (2004). Problemas sin resolver en teoría de números . Springer-Verlag . ISBN 978-0-387-20860-2. OCLC  54611248. Zbl  1058.11001. Sección C6.

Enlaces externos

• http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html
• Secuencia OEIS A003313 (Longitud de la cadena de adición más corta para n). Nótese 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 adición"