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 393393 trillion, I guess. Does it actually mean anything or is it just a misunderstanding on the part of the journalists?

=================

I’ve read non-scientific articles with huge mistakes. Perhaps purposeful mistakes. They don’t really care if it’s a permutation or a combination, maybe a set. That being said, I can’t answer your question.

– O. Von Seckendorff

2 days ago

@O.VonSeckendorff Yes, I suspect it’s a mistake too.

– Oppa Hilbert Style

2 days ago

You forgot the word â€œtrillionâ€ in the title.

– Hans Lundmark

2 days ago

@HansLundmark Yes, thanks.

– Oppa Hilbert Style

2 days ago

=================

2 Answers

2

=================

We have to compute the 1313-th root of an unknown number NN such that 10199≤N<1020010^{199}\le N<10^{200} so that 10199/13≤N1/13<10200/13\;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 2,030,917,620,904,736\; to 2,424,462,017,082,328\;2,424,462,017,082,328. This gives at most : 10200/13−10199/13≈393,544,396,177,593possibilities10^{200/13}-10^{199/13}\approx 393,544,396,177,593\quad\text{possibilities} −- For something 'simpler' suppose known the 6000060000 digits of the perfect power N=k11001\;N=k^{11001}\; and try to find the positive integer kk. You'll notice that kk can only take the values from 284420284420 to 284478284478. Remembering the two last digits of the 1100111001-th powers of (284420+i)\;(284420+i)\; for ii from 00 to 5858 : 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) 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$) } should help you, after just a smart glance at the 6000060000 digits of the 1100111001-th power, to provide instantly the wished 1100111001-th root ! But to choose between 5959 values we don't really need to memorize all these values (nor even require NN to be a perfect power). Mental calculators usually know their common logarithms and may use : N1/11001≈284419+59.53log10N2,with N2 defined by N=N21060000−1 and1≤N2<10N^{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 this is easily obtained from N1/11001≈1060000−111001+log10(N2)11001≈1060000−111001(1+ln(10)11001log10(N2))\;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 22 digits for N2N_2 should be enough while replacing 59.5359.53 by 6060 gives an error bounded by 0.48\,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 1313-th roots possible for the first digits (specifically for 200200 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 1313-th Root of a 100100-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 1313-th root of 100100 digits? â€™Must be a bloody idiot,â€™ you say. No. It puts you in the Guinness Book, of courseâ€ 1 Fixed first ones? – Oppa Hilbert Style 2 days ago @OppaHilbertStyle: Ok here only the fixed digit 22 but I saw compittions where the 1000010000-th root was computed by 'head' and this gave quite a fiew fixed digits (I edited my answer...). – Raymond Manzoni 2 days ago Minors corrections "between..." should be "from 20309176209047362030917620904736 to 24244620170823282424462017082328 and "a fiew" →\to "a few" 😉 – Raymond Manzoni 2 days ago 1 Why the factorial? – Barry Cipra 2 days ago 2 @BarryCipra Hmmn, good spot. Maybe it's an exclamation mark used as emphasis. – Bacon 2 days ago This is just an elaboration on Raymond Manzoni's answer, addressing the OP's question whether the journalist misunderstood something. Here are the lede paragraphs from the news story (which features a photo illustration of Lemaire pondering the 200-digit number): When the answer is 2,407,899,893,032,210 you know the question is tough. Not so tough, however, that Alexis Lemaire could not work it out in his head. His challenge yesterday was to come up with the 13th root of a computer-generated 200-digit number. And, with 393 trillion possible answers to choose from, the PhD student made it almost look easy. The "393 trillion" almost certainly came from a press release prepared by the sponsor of the challenge; no reporter (except maybe me) has the time or the expertise to make such a calculation (and I would probably get it wrong). Given that the 13th root of the 200-digit number was an integer, it seems fairly clear that what the computer did was pick a (random?) number nn such that 10199≤n3<1020010^{199}\le n^3\lt10^{200}, so that there are ⌊10200/13⌋−⌊10199/13⌋≈393\lfloor10^{200/13}\rfloor-\lfloor10^{199/13}\rfloor\approx393 trillion choices for nn. It's perhaps worth noting, though, that a13≡aa^{13}\equiv a mod 1010 for all aa, which means that that a quick look at the final digit of the 200-digit number tells you the final digit of the answer. So in a sense this quickly cuts the number of possible answers down to around 39.339.3 trillion. And in this case, in fact, the 200-digit number ends in a string of thirteen 00's preceded by a 11, which means the answer necesarrily ends in 1010, thus cutting the number of possibilities to a "manageable" 3.93.9 trillion.... Thanks for the continuation Barry! (factorial Cipra :-)). From your citation I found too this link. Of course we may further reduce the possibilities from the left by evaluating l:=log10(N)/13\;l:=\log_{10}(N)/13\; (and 10l10^l after that) but it seems that the 1313-th root evaluation was and 'industry' with great calculators names like Wim Klein and an excellent article by Ron Doerfler and Miles Forster "The 1313-th Root of a 100-Digit Number". Thanks again for the follow up, – Raymond Manzoni yesterday 1 @RaymondManzoni, excellent link! You might edit it into your own answer as well! (Incidentally, I hope my factorial comment was understood as the gentle joke I intended it to be.) – Barry Cipra yesterday No problem @Barry Cipra I considered it that way(!) (with some minor aftershocks... :-)). The Doerfler-Foerster paper is indeed excellent and I'll introduce it in my answer. Cheers, – Raymond Manzoni yesterday