Complejidad de números enteros

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

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 mediante 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 puede representarse utilizando ocho unos:

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

Sin embargo, no tiene representación con siete o menos unos, por lo que 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, 9, 8, ... (secuencia A005245 en la 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 la 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). Ellos preguntaron cuál era el número más grande con una complejidad dada k ; ^[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 entero más grande que se puede expresar usando diez unos es 2 ²  3 ² = 36. Su expresión es

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

Por lo tanto, la complejidad de un entero n es al menos 3 log ₃  n . La complejidad de n es como máximo 3 log ₂  n (aproximadamente 4,755 log ₃  n ): una expresión de esta longitud para n se puede encontrar aplicando el método de Horner a la representación binaria de n . ^[2] Casi todos los 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 un cierto umbral N se pueden calcular en tiempo total O ( N  ^1,222911236 ) . ^[4]

Los algoritmos para calcular la complejidad de los números enteros se han utilizado para refutar varias conjeturas sobre la complejidad. En particular, no es necesariamente el caso que la expresión óptima para un número n se obtenga ya sea 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 lo tanto también refuta una conjetura de Richard K. Guy de que la complejidad de cada 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 cadenas de Markov a la complejidad entera , arXiv : 1511.07842 , Bibcode :2015arXiv151107842S.
4. Cordwell, K.; Epstein, A.; Hemmady, A.; Miller, S.; Palsson, E.; Sharma, A.; Steinerberger, S.; Vu, Y. (2017), Sobre algoritmos para calcular la complejidad de números 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 a la conjetura de los primos 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 .