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?

Answer

We have to compute the 13-th root of an unknown number N such that 10199N<10200 so that 10199/13N1/13<10200/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 :
10200/1310199/13393,544,396,177,593possibilities

For something 'simpler' suppose known the 60000 digits of the perfect power N=k11001 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 :
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(and some tricks to distinguish the degenerate cases like 0 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 :
N1/11001284419+59.53log10N2,with N2 defined by N=N210600001 and1N2<10
this is easily obtained from N1/110011060000111001+log10(N2)110011060000111001(1+ln(10)11001log10(N2)).
A working precision of 2 digits for N2 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”

Attribution
Source : Link , Question Author : Red Banana , Answer Author : Community

Leave a Comment