Complejidad entera

Longitud de la expresión como combinación de 1

En teoría de números , la complejidad de un número entero es el número más pequeño de unos que se puede utilizar para representarlo usando unos y cualquier número de sumas , multiplicaciones y paréntesis. Siempre está dentro de un factor constante del logaritmo del número entero dado .

Ejemplo

Por ejemplo, el número 11 se puede representar usando ocho unos:

11 = (1 + 1 + 1) × (1 + 1 + 1) + 1 + 1.

Sin embargo, no tiene representación utilizando siete o menos. Por tanto, su complejidad es 8.

Las complejidades de los números 1, 2, 3,... son

1, 2, 3, 4, 5, 5, 6, 6, 6, 7, 8, 7, 8, 8, 8, 8, 9, 8, ... (secuencia A005245 en el OEIS )

Los números más pequeños con complejidad 1, 2, 3, ... son

1, 2, 3, 4, 5, 7, 10, 11, 17, 22, 23, 41, 47, ... (secuencia A005520 en el OEIS )

Límites superior e inferior

La cuestión de expresar números enteros de esta manera fue considerada originalmente por Mahler y Popken (1953). Pidieron el mayor número con una complejidad k dada ; ^[1] más tarde, Selfridge demostró que este número es

${\displaystyle 2^{x}3^{(k-2x)/3}{\text{ where }}x=-k{\bmod {3}}.}$

Por ejemplo, cuando k = 10 , x = 2 y el número entero más grande que se puede expresar usando diez unidades es 2 ²  3 ² = 36 . Su expresión es

(1 + 1) × (1 + 1) × (1 + 1 + 1) × (1 + 1 + 1).

Por tanto, la complejidad de un número entero n es al menos 3 log ₃  n . La complejidad de n es como máximo 3 log ₂  n (aproximadamente 4,755 log ₃  n ): se puede encontrar una expresión de esta longitud para n aplicando el método de Horner a la representación binaria de n . ^[2] Casi todos los números enteros tienen una representación cuya longitud está limitada por un logaritmo con un factor constante más pequeño, 3,529 log ₃  n . ^[3]

Algoritmos y contraejemplos

Las complejidades de todos los números enteros hasta cierto umbral N se pueden calcular en el tiempo total O ( N  ^1,222911236 ) . ^[4]

Se han utilizado algoritmos para calcular la complejidad de los números enteros para refutar varias conjeturas sobre la complejidad. En particular, no es necesariamente cierto que la expresión óptima para un número n se obtenga restando uno de n o expresando n como el producto de dos factores más pequeños. El ejemplo más pequeño de un número cuya expresión óptima no es de esta forma es 353942783. Es un número primo y, por tanto, también refuta una conjetura de Richard K. Guy de que la complejidad de todo número primo p es uno más la complejidad de p − 1 . ^[5] De hecho, se puede demostrar que . Además, Venecia Wang dio algunos ejemplos interesantes, es decir , , , pero . ^[6] ${\displaystyle \|p\|=\|p-1\|=63}$ ${\displaystyle \|743\times 2\|=\|743\|=22}$ ${\displaystyle \|166571\times 3\|=\|166571\|=39}$ ${\displaystyle \|97103\times 5\|=\|97103\|=38}$ ${\displaystyle \|23^{2}\|=20}$ ${\displaystyle 2\|23\|=22}$

Referencias

1. Mahler, K .; Popken, J. (1953), "Sobre un problema de máximos en aritmética", Nieuw Archief voor Wiskunde , 1 : 1–15, SEÑOR  0053986.
2. Guy, Richard K. (1986), "Algunas secuencias sospechosamente simples", Problemas sin resolver, American Mathematical Monthly , 93 (3): 186–190, doi :10.2307/2323338, JSTOR  2323338, MR  1540817.
3. Shriver, Christopher E. (2015), Aplicaciones del análisis de la cadena de Markov a la complejidad de enteros , arXiv : 1511.07842 , Bibcode :2015arXiv151107842S.
4. Cordwell, K.; Epstein, A.; Hemmady, A.; Molinero, S.; Palsson, E.; Sharma, A.; Steinerberger, S.; Vu, Y. (2017), Sobre algoritmos para calcular la complejidad de enteros , arXiv : 1706.08424 , Bibcode :2017arXiv170608424C
5. Fuller, Martin N. (1 de febrero de 2008), Programa para calcular A005245, A005520, A005421, OEIS , consultado el 13 de diciembre de 2015.
6. Wang, Venecia (octubre de 2012), "Un contraejemplo de la conjetura prima de expresar números usando solo unos", Journal of Number Theory , 133 (2), JNT: 391–397, doi : 10.1016/j.jnt.2012.08. 003.

enlaces externos

• Weisstein, Eric W. "Complejidad entera". MundoMatemático .