Cadena de suma

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]

Ejemplos

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 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 :

norte ² = norte × norte

norte ³ = norte ² × norte

norte ⁶ = norte ³ × norte ³

norte ¹² = norte ⁶ × norte ⁶

norte ²⁴ = norte ¹² × norte ¹²

norte ³⁰ = norte ²⁴ × norte ⁶

norte ³¹ = norte ³⁰ × norte

Métodos para calcular cadenas de suma.

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] ${\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 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] ${\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

Denotemos el más pequeño para que exista una cadena de suma 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))}$,

¿Dónde está 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 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 ). ${\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 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

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

¿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 ⁶¹⁰⁶  + 2 ³⁰⁴⁸  + 2 ²⁰³²  + 2 ²⁰¹⁶  + 1 que tiene l ^* ( n ) = 6110, l ( norte ) ≤ 6109 . El n más pequeño es 12509. ${\displaystyle l^{*}}$

conjetura de Scholz

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

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

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] ${\displaystyle n\leq 5784688}$ ${\displaystyle l(2^{n}-1)=n-1+l(n)}$ ${\displaystyle n\leq 64}$

Ver también

• Cadena de suma-resta
• Cadena de suma vectorial
• cadena 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, Pedro; León, Benton; Sethi, Ravi (1981), "Computación de secuencias con cadenas de suma", SIAM Journal on Computing , 10 (3): 638–646, doi :10.1137/0210047. Varios otros artículos afirman que encontrar una cadena de suma más corta para un solo número es NP-completo, citando este artículo, pero no afirma ni prueba tal resultado.
3. Otto, Martin (2001), Cadenas de suma y resta de Brauer (PDF) , Diplomarbeit, Universidad de Paderborn, archivado desde el original (PDF) el 19 de octubre de 2013 , consultado el 19 de octubre de 2013.
4. Schönhage, Arnold (1975), "Un límite inferior para la longitud de las cadenas de suma", Informática teórica , 1 (1): 1–12, doi :10.1016/0304-3975(75)90008-0
5. chico (2004) p.169
6. Clift, Neill Michael (2011). "Cálculo de cadenas de suma óptimas" (PDF) . Informática . 91 (3): 265–284. doi : 10.1007/s00607-010-0118-8 .
7. Achim Flammenkamp, ​​Cadenas de suma más cortas

• Brauer, Alfred (1939). "Sobre cadenas de suma". Boletín de la Sociedad Matemática Estadounidense . 45 (10): 736–739. doi : 10.1090/S0002-9904-1939-07068-7 . ISSN  0002-9904. SEÑOR  0000245.
• Richard K. Guy (2004). Problemas no resueltos 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). 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"