# What are the 393393 trillion possible answers when computing 13th13^{th} root of a number?

Alexis Lemaire got famous after finding the 13th root of a computer-generated 200-digit number without calculator. In this article, they say that there are “with 393 trillion possible answers to choose from”. At first, I thought that it was the number of permutations of digits for each possible answer, but this wouldn’t give the $393$ trillion, I guess. Does it actually mean anything or is it just a misunderstanding on the part of the journalists?

We have to compute the $13$-th root of an unknown number $N$ such that $10^{199}\le N<10^{200}$ so that $\;10^{199/13}\le N^{1/13}<10^{200/13}$ : all the choices are not possible but only the values from $2,030,917,620,904,736\;$ to $\;2,424,462,017,082,328$. This gives at most :

For something 'simpler' suppose known the $60000$ digits of the perfect power $\;N=k^{11001}\;$ and try to find the positive integer $k$. You'll notice that $k$ can only take the values from $284420$ to $284478$.

Remembering the two last digits of the $11001$-th powers of $\;(284420+i)\;$ for $i$ from $0$ to $58$ :
should help you, after just a smart glance at the $60000$ digits of the $11001$-th power, to provide instantly the wished $11001$-th root !

But to choose between $59$ values we don't really need to memorize all these values (nor even require $N$ to be a perfect power). Mental calculators usually know their common logarithms and may use :

this is easily obtained from $\;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)$.
A working precision of $2$ digits for $N_2$ should be enough while replacing $59.53$ by $60$ gives an error bounded by $\,0.48$.

We may thus "reduce the possibilities" by using the most significant digits and, for a perfect power only, by exploiting the less significant ones (as explained by Barry Cipra).
It should be clear that all this doesn't explain the speed of A. Lemaire and others who used specific techniques like memorizing the different $13$-th roots possible for the first digits (specifically for $200$ digits numbers) as well as for the last digits.

Many of the methods used are neatly exposed in Ron Doerfler and Miles Forster article :
"The $13$-th Root of a $100$-Digit Number" starting with the methods used by Wim Klein (from Ron Doerfler's blog). Let's conclude with some of his wise words :

“What is the use of extracting the $13$-th root of $100$ digits? ’Must be a bloody idiot,’ you say.
No. It puts you in the Guinness Book, of course”