Complejidad entera

En teoría de números , la complejidad de un entero es la menor cantidad de unos que se pueden usar para representarlo usando unos y cualquier cantidad de sumas , multiplicaciones y paréntesis. Siempre está dentro de un factor constante del logaritmo del entero dado .

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 unos. Por lo 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 )

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

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

Por ejemplo, cuando k = 10 , x = 2 y el mayor entero que se puede expresar usando diez unos es ^2²³² = 36. Su ^expresión es

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

Así, 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 ): 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 enteros tienen una representación cuya longitud está acotada por un logaritmo con un factor constante menor, 3,529 log ₃ n . ^{[ 3 ]}

La complejidad${\displaystyle \|n\|}$de cada entero n hasta cierto umbral N se puede calcular en un tiempo total O ( N ^1.222911236 ) . ^{[ 4 ]} . Esto se mejoró a${\displaystyle O(n\log ^{O(1)}n)}$algoritmo de tiempo de He ^{[ 5 ]} . La complejidad de un solo entero${\displaystyle n}$También se puede calcular en tiempo sublineal de${\displaystyle O(n^{0.6514})}$.

Los algoritmos para calcular la complejidad entera se han utilizado 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 a 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 todo número primo p es uno más la complejidad de p − 1. [ ^{6 ] De} hecho, se puede demostrar que${\displaystyle \|353942783\|=\|353942782\|=63}$Además, Venecia Wang dio algunos ejemplos interesantes, es decir:${\displaystyle \|743\times 2\|=\|743\|=22}$,${\displaystyle \|166571\times 3\|=\|166571\|=39}$,${\displaystyle \|97103\times 5\|=\|97103\|=38}$,${\displaystyle \|23^{2}\|=20}$pero${\displaystyle 2\|23\|=22}$. ^{[ 7 ]}

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