¿Cuáles son las $393$ trillón de respuestas posibles al calcular $13^{th}$ ¿Raíz de un número?

Question

Alexis Lemaire se hizo famoso tras encontrar la raíz 13 de un número de 200 dígitos generado por ordenador sin calculadora. En este artículo dicen que hay "con 393 billones de respuestas posibles para elegir" . Al principio, pensé que era el número de permutaciones de dígitos para cada posible respuesta, pero esto no daría el $393$ un trillón, supongo. ¿Significa realmente algo o es sólo un malentendido por parte de los periodistas?

Answer 1

Tenemos que calcular el $13$ -raíz de un número desconocido $N$ tal que $10^{199}\le N<10^{200}$ para que $\;10^{199/13}\le N^{1/13}<10^{200/13}$ no son posibles todas las opciones, sino sólo los valores de $ 2,030,917,620,904,736\;$ a $\;2,424,462,017,082,328$ . Esto da como máximo : $$10^{200/13}-10^{199/13}\approx 393,544,396,177,593\quad\text{possibilities}$$ $$-$$ Para algo más "sencillo" supongamos que se conoce el $60000$ dígitos de la potencia perfecta $\;N=k^{11001}\;$ y tratar de encontrar el entero positivo $k$ . Notarás que $k$ sólo puede tomar los valores de $284420$ a $284478$ .

Recordando los dos últimos dígitos del $11001$ -enfermedades de $\;(284420+i)\;$ para $i$ de $0$ a $58$ : $$0, 21, 72, 23, 24, 25, 76, 27, 28, 29, 0, 31, 32, 33, 84, 75, 36, 37, 88, 39, 0, 41, 92, 43, 44, 25, 96, 47, 48, 49, 0, 51, 52, 53, 4, 75, 56, 57, 8, 59, 0, 61, 12, 63, 64, 25, 16, 67, 68, 69, 0, 71, 72, 73, 24, 75, 76, 77\quad\text{(and some tricks to distinguish the degenerate cases like $ 0 $) }$$ debería ayudarte, después de echar un vistazo inteligente a la $60000$ dígitos de la $11001$ -a la potencia, para proporcionar al instante la deseada $11001$ ¡-th root !

Pero para elegir entre $59$ no necesitamos realmente memorizar todos estos valores (ni siquiera requerir $N$ para ser una potencia perfecta). Los calculadores mentales suelen conocer su logaritmos comunes y puede utilizar : $$N^{1/11001}\approx 284419+59.53\;\log_{10}N_2,\\\quad\text{with $ N_2 $ defined by $ \,N=N_2\;10^{60000-1}\; $ and}\;\,1\le N_2<10$$ esto se obtiene fácilmente de $\;N^{1/11001}\approx 10^{\large{\frac{60000-1}{11001}+\frac{\log_{10}(N_2)}{11001}}}\approx 10^{\large{\frac{60000-1}{11001}}}\left(1+\frac{\ln(10)}{11001}\log_{10}(N_2)\right)$ .
Una precisión de trabajo de $2$ dígitos para $N_2$ debería ser suficiente mientras se sustituye $59.53$ por $60$ da un error limitado por $\,0.48$ .

Así, podemos "reducir las posibilidades" utilizando los dígitos más significativos y, sólo para una potencia perfecta, explotando los menos significativos (como explica Barry Cipra).
Debe quedar claro que todo esto no explica la velocidad de A. Lemaire y otros que utilizaron técnicas específicas como la memorización de los diferentes $13$ -raíces posibles para los primeros dígitos (específicamente para $200$ números), así como para los últimos dígitos.

Muchos de los métodos utilizados se exponen claramente en el artículo de Ron Doerfler y Miles Forster :
"El $13$ -Raíz de a $100$ -Número de dígitos" empezando por los métodos utilizados por Wim Klein (del libro de Ron Doerfler blog ). Concluyamos con algunas de sus sabias palabras:

"¿De qué sirve extraer el $13$ -raíz de $100$ ¿dígitos? "Debe ser un maldito idiota", dices.
No. Te pone en el Libro Guinness, por supuesto"

Answer 2

Esto es sólo una elaboración de la respuesta de Raymond Manzoni, abordando la pregunta del OP de si el periodista entendió algo mal.

Estos son los párrafos de la noticia (que incluye una foto de Lemaire reflexionando sobre la cifra de 200 dígitos):

Cuando la respuesta es 2.407.899.893.032.210 sabes que la pregunta es difícil.

Sin embargo, no es tan difícil que Alexis Lemaire no pueda resolverlo en su cabeza. Su reto de ayer era encontrar la raíz 13 de un número un número de 200 dígitos generado por ordenador.

Y, con 393 billones de respuestas posibles para elegir, el doctorado estudiante de doctorado lo hizo parecer casi fácil.

Los "393 billones" provienen casi con toda seguridad de una nota de prensa preparada por el patrocinador del reto; ningún periodista (excepto quizá yo) tiene el tiempo o los conocimientos necesarios para hacer ese cálculo (y probablemente me equivocaría). Dado que la raíz 13 del número de 200 dígitos era un número entero, parece bastante claro que lo que hizo el ordenador fue elegir un número (¿al azar?) $n$ tal que $10^{199}\le n^3\lt10^{200}$ para que haya $\lfloor10^{200/13}\rfloor-\lfloor10^{199/13}\rfloor\approx393$ trillones de opciones para $n$ .

Sin embargo, tal vez valga la pena señalar que $a^{13}\equiv a$ mod $10$ para todos $a$ , lo que significa que una mirada rápida al último dígito del número de 200 dígitos le indica el último dígito de la respuesta. Así que, en cierto sentido, esto reduce rápidamente el número de respuestas posibles a unas $39.3$ trillón. Y en este caso, de hecho, el número de 200 dígitos termina en una cadena de trece $0$ precedido por un $1$ lo que significa que la respuesta necesariamente termina en $10$ reduciendo así el número de posibilidades a un número "manejable". $3.9$ trillion....