## The 13th Root of a 100-Digit Number (Part I)

by Ron Doerfler and Miles Forster Mental calculators of note (so-called “lightning calculators”) developed areas of expertise in performing calculations that seem astonishing, even unbelievable, to the rest of us. One such specialty is calculating the 8-digit root of a 13th power of 100 digits. Achieving record times historically required massive memorization and calculating speed, racing through a procedure that remains a mystery to most people. Part I of this essay provides a historical overview of the extraction of 13th roots, including the methods used by a few mental calculators, methods that largely rely on a mix of intensive mental calculation and large-scale rote memorization. It demonstrates the creativity and drive of these  marvelous people.

In Part II of this essay we will propose a new method for 13th roots like those posed to lightning calculators that is relatively easy to learn, one that makes this feat feasible for those of us with basic mental math capabilities and a desire to do something amazing. A printer-friendly PDF version of Parts I and II is linked at the end of this essay.

Why 13th Roots?

It is generally known that the difficulty of mentally solving for integer roots depends on the number of digits in the root rather than the number of digits in the power. So why did the 13th root of a 100-digit number become the standard?

First, the appeal of a prime power must be acknowledged. Square root extraction is another popular category in itself. Composite roots such as the 4th root or 12th root can be calculated as a sequence of roots of their factors (two square roots to get a 4th root, followed by a cube root to get a 12th root). In fact, for a given number of digits in the root, even-numbered roots are more difficult because the final digit of an odd root can be found from the final digit of the power. It turns out that orders of powers that are one more than a multiple of 4 (such as the 13th power) have a root with the same final digit, while orders of powers that are one less than a multiple of 4 (such as a cube) have a root with a unique final digit relative to the final digit of the power. So here we have the first clue: the final digit of a 13th root will be the same as that of the power.

Second, 100 is an impressive round number of digits, and this produces a 13th root consisting of 8 digits. This number of digits proves to be non-trivial while not beyond the capabilities of the best mental calculators. If there were only 3 digits in the root of an odd power, the problem is easy. The final digit is found from the rules just described. The first digit can be inferred from memorized or estimated ranges of the powers. The properties of modular arithmetic can reveal the middle digit; here the root and power are replaced with remainders after division by an integer while still retaining the 13th power relationship, and we can deduce the missing digit.

For example, consider the 3-digit root of an odd power such as 24137569. Since 2003 = 8000000 and 3003=27000000, we know the root has a 2 as the first digit. Since 3 is one less than a multiple of 4, the final digit of the root will not necessarily equal that of the power, but there will be a unique mapping—in this case 93 ends in 9 so the last digit is in fact 9 and we are left with 2b9, where b is unknown. The remainder when a number N is divided by 11 (or N mod 11) can be found by subtracting the odd-place digits from the even place digits and repeating, adding 11’s until the result lies between 0 and 10. Here 24137569 mod 11 = (9+5+3+4) – (6+7+1+2) = 5. Now (2b9)3 mod 11 must equal 5 as well. So [(9+2) – b]3 mod 11 =  (11 – b)3 mod 11 = 5. As noted above, for cube roots there is a unique mapping between n and n3 mod 11 and this mapping would be memorized by the mental calculator. Here we can see that 33 mod 11 = 5 since 27 = 22+5, so 11–b = 3 or b = 8. So the cube root of 24137569 is 289.

For the 13th root of a 100-digit number, the first digit is always 4, and we know the last digit is the same as the power. But the 13th root has 8 digits and 7992563 possibilities so there is much more ambiguity, even when the performer has memorized long tables of 2-digit or 3-digit sets of beginning and ending digits. For this reason, the Guinness Book of World Records created the category of 13th root extraction of 100-digit numbers, recording in the eleventh edition of 1972 a time of 23 minutes by Herbert B. de Grote of Mexico.

Historical Methods

In the years since de Grote’s initial record, great efforts have been taken to solve 13th roots, and as a result the times required for it have steadily decreased. Here we will discuss three of the major players in this field: Wim Klein, Gert Mittring and Alexis Lemaire.

Wim Klein Wim Klein of the Netherlands, a lightning calculator who worked at CERN, bested de Grote with a time of 5 minutes and then proceeded to lower his time even further. He eventually attained a record time in 1981 of 1 minute 28 seconds to calculate the 13th root of

88008443440489299575219015772236417859411720052615
65487280650870412023307854274990144578442271602817

He found the answer to be 48757377.

How did he calculate these roots? Klein used logarithms to find the first five digits, and then used his knowledge of 13th root endings and modular arithmetic to deduce the last three digits. To find the logarithms he would factor the initial digits and add up those 5-digit logarithms from memory, interpolating between values as needed for offsets. Then he would divide by 13 and use the reverse process to find the antilogarithm, the number whose logarithm would be that value. This would be the initial five digits of the root. It is far easier said than done.

Smith  discussed with Klein his method for finding the 13th root of

14762420839370760705665953772022217870318956930659
27236796230563061507768203333609354957218480390144

Here is Smith’s account of Klein’s procedure:

The first five digits of the root are fixed through the use of logarithms. Klein has memorized to five places the logs of the integers up to 150; this, coupled with his ability to factor large numbers, allows him to approximate the log of the first five digits of the power, which is usually sufficient to determine the first five digits of the root, though, as he says “the fifth digit is a bit chancy.”

Klein began by factoring 1,476 into 36 times 41 and taking the (decimal) log of each: log 36 = 1.55630 and log 41 = 1.61278; adding the mantissas yields 0.16908, but this is, of course, too little. Through various interpolations Klein estimated the mantissa of the log of 147,624 as 0.16925 (it is more nearly 0.16916).

Klein now had an approximation of the log of the 100-digit number above – 99.16925. This must be divided by 13 to obtain the log of the 13th root. Since 99=13 × 7 with a remainder of 8, to obtain the mantissa of the antilog of the 13th root he divided 8.16925 by 13, which is approximately 0.62840. He estimated the antilog to be about halfway between 4.2 and 4.3 and decided to try 4.25. The result was exact, so the first five digits of the root should be 42500, as indeed they are.

It is now necessary to determine the last three digits of the root. This he does from an examination of the last three digits of the power. In the case of odd powers, these uniquely determine the last three digits of the root, but in the case of even roots, like this one, this method yields four possibilities; in the case of 144 they are 014, 264, 514, and 764. (The choices always differ by 250.) To select the correct one Klein divides the original number by 13 and retains the remainder. In the case of 13th roots, the root remainder and the power remainder must be the same. The power remainder is 7; only 764 as the final three digits of the root will yield 7 as the remainder. Thus the 13th root is determined to be 42,500,764.

As we will see, there are multiple endings possible when the 13th power ends in 2, 4, 6, or 8, so these are not going to be record attempts. In fact, the above account appears to be unique; other accounts of 13th roots are limited to odd final digits, and the method described in Part II of this paper is also limited to odd final digits.

Here is Klein’s account for another 13th power, also from Smith:

75185285487713563581947553291145079861723813162341
53935861550997297991815299022662358976308065985831

The first five digits of the power are 75185, which is nearly 7519, and 7519 is 73 times 103. The mantissa of the log of 73 is 0.86332 and that of 103 is 0.01284. Their sum is 0.87616. Dividing 8.87616 by 13 yields 0.68278. This falls between the mantissas of the logs of 48 and 49, but is much closer to 48. Since 481 is 13 (mantissa 0.11394) times 37 (mantissa 0.56820), the mantissa of its log will be 0.68214; close, but still a bit low; 4,816 can be factored into 16 (mantissa 0.20412) times 7 (mantissa 0.84510) times 43 (mantissa 0.63347). This gives a mantissa of 0.68269. Then 4,818 factors into 66 (mantissa 0.81954) times 73 (mantissa 0.86332), which yields a mantissa of 0.68286. Thus, in the interpolation we want 9/17 of 20 which is about 10 1/2. The first five digits of the root should be 48170 (48160 + 10). This, in fact, is correct.

When Klein actually did the calculation he made a minor error (he was looking for the antilog of 0.68277 instead of 0.68278) and first took 48169 for the first five digits of the root. In this case, however, since the root is odd, the last three digits are uniquely fixed—since the power ends in 831, the root must end in 311. Upon dividing the power by 13 Klein got a remainder of 7. But dividing 48,169,311 by 13 gives a remainder of 8. To make these two remainders come into line he changed his solution to 48,170,311, which is correct.

Hope  remarks that “acquaintances of Klein report that during these complex mental calculation tasks, Klein mutters constantly in Dutch while calculating, and a good part of his muttering consists of swearing.”

Klein also worked with higher-order roots. In 1976, he found the 73rd root of a 500-digit number in 2 minutes 43 seconds, a feat recorded in the two photographs of Klein in this essay.  In 1983 he found the 73rd root of a 505-digit number in 1 minute 43 seconds. A 73rd root duplicates the final digit of the power just as the 13th root does, since they are both of order 4k+1. No doubt Klein used the same procedure described above but divided the logarithm by 73 rather than 13. In this case there are only 7 digits with 273696 possibilities, a factor of nearly 30 fewer than the 13th root of a 100-digit number. As we have seen, the mass of digits in the middle of the power mean nothing to the mental calculator, only the starting and ending digits. Klein talked freely of how he would sometimes write down intermediate results, particularly in front of audiences [Smith 1983].

Gert Mittring These examples of Klein demonstrate a great deal of effort by an extremely talented and dedicated mental calculator, far beyond reasonable expectations for the rest of us. But modern calculators have eclipsed Klein, claiming records of mere seconds for particular attempts. One such calculator is Gert Mittring of Germany. On August 25, 2011, Mittring won his eighth consecutive title in the Mental Calculations World Championship, evidence of formidable talent. In 2004 Mittring (shown here with a different record attempt) achieved a record of 11.8 seconds for the 13th root of

70664373816742861022340088302401573757042331707026
32731269721516000395709065419973141914549389684111

Writing in Spiegel Online [Mittring 2004], Mittring describes one strategy for finding this particular root, as translated below:

There are different strategies in the present problem of finding the solution. I will try to explain a variation that I’ve used. As you like, you may devise alternative strategies. It is desirable in any case to have a “memory-economic” variant.

The determination of the 8-digit (integer) 13th root of a 100-digit number is done in three major steps:

1. The estimate of the logarithm.
2. The division by 13 (the root exponent). The result is the logarithm of the solution.
3. The conversion of the logarithm to its antilogarithm.

It is sufficient to look at the first six digits of the 100-digit number. Rounded, it starts with 706644 × 1094. How can the logarithm be estimated effectively? I only know the logarithms of the primes up to 100 (2, 3, 5…, 97). That amounts to 25 logarithm values to 7 decimal places each, so the memory effort is equivalent to 15 phone numbers.

The first big step:

A first estimate is the following simple application of the rules of logarithms by factoring the number 706644 × 1094 into prime factors and then summing them up (where log 2 + log 5 = 1):

log (706644 × 1094)
~ 94 + 2 log 2 + 5 log 3 + (6 log 3 + 2 log 5 + log 29) / 2
= 95 + 2 + 8 log 3 + log 29 /2 ~ 99.849199…   (the exact value would be 99.849200…)

The second step is simple:

Through my experience with multiplication I immediately know that 7.68 × 13 = 99.84. Right away I get the additional decimal places 07077 (rounded up, and knowing very well that the estimate for the original logarithm is a lower bound).

The third step:

In the last step I have to find the antilogarithm of 7.6807077. A rough linear approximation over

log 48 = 4 log 2 + log 3      and      log 47

gives me the first digits of the solution: 4794. It is apparent that

log 4794 × 104 = 4 + log 2 + log 3 + log 17 + log 47 (where log 47 is already known above)

~ 7.6806980

The difference now is only 97 × 10-7. Obviously, 97 times ‘a bit over 11 units’ still needs to be added. The estimated solution is then ‘a little over’ 47941067.

As a check, one can analyze the end digits of the original number. Because the 100-digit number ends in 11, a rule tells me that the solution needs to end in 71. Therefore, everything speaks in favor of 47941071, which I then spoke out and which was indeed the right answer.

Let’s study Mittring’s third step for finding the antilogarithm of 7.6807077. For N = 107.6807077, he uses his knowledge of logarithms to find N such that lo g N = 7.6807077:

1. Mittring would know that log 47 = 1.6721. The original number minus 6 yields 1.6807077 which is greater than log 47 by 0.0086. So he checks log 48, and in this case he factors it into primes (24 × 3) and finds log 48 as 4 log 2 + log 3 = 1.6812, which is a little high by 0.0005. In practice, Mittring has no doubt memorized the table of logarithms on the right that spans the range of the initial two digits of the 13th root.
1. The “rough linear approximation” is a linear interpolation between log 47 and log 48. The difference between the values of log 48 and log 47 is 0.0091 per the table, and log 48 is 0.0005 too high, so 0.0005/0.0091 = 0.06 is subtracted from 48 to yield 47.94. Adding the 6 that was subtracted from the original number of 7.6807077 gives 6 + log 47.94 or log 106 + log 47.94 or log 47940000. Now 4794000 becomes our initial estimate of the root.
1. Now Mittring finds the exact value of log 47940000 in order to find its difference from the exact value of 7.6807077. From his innate knowledge of numbers, he factors 47940000 into 104×2×3×17×47, so log 47940000 = 4 + log 2 + log 3 + log 17 + log 47, which he adds up from memorized values of logarithms to get log 47940000 = 7.6806980.
1. Now log 47940000 is 0.0000097 lower than 7.6807077. How much would we increase 47940000 if we increase its log by 97? In other words, for n=47940000 what is Δn for a given increase of Δ(log n)? Mittring at least implicitly uses the linear approximation

Δn ≈ 2.3nΔ(log n)
= 2.3 × 4.794e7 × 97e-7  ≈  11 × 97  =  106

and so 47941067 is our next estimate. The “bit over 11 units” that is multiplied by 97 in Mittring’s explanation is evidently from approximating 2.3 × 4.8.

1. T he final two digits of a 13th root of a power ending in 1, 3, 7, or 9 are easily found from the final two digits of the power (the other endings of 13th powers do not produce unique endings of their roots). The table on the right shows the two digit endings of 13th roots for any two-digit endings of the powers. For any final two digits of the power shown in the body of the table, the corresponding digits of the root are found at the edges. The last two digits of the power are 11, so the root ends in 71. The estimate of 47941067 is therefore modified to 47941071.

Did Gert Mittring do all this in 11.8 seconds? He described it as simply one strategy he has used, a variant that is “memory-economic,” but it requires significant knowledge of factors and logarithmic values. The details of the presentation of the problem and the timing parameters of the test are not known, but it seems inconceivable that this was the method used to achieve this record time. Perhaps this attempt was achieved through a different, “memory-intensive” method. In the next section we will discuss another mental calculator who bested Mittring’s time and refers to these as simply tests of memory, albeit of prodigious memory.

Alexis Lemaire Less than a month after Gert Mittring’s 2004 record of 11.8 seconds, Alexis Lemaire of France is reported to have extracted the 13th root of the number below in 3.625 seconds. As presumably the case with Mittring, this time included the time to write the answer of 45792573:

38934589793526802773496632556519305532657006082154
49817188566054427172046103952232604799107453543533

What are we to make of this feat?  On Lemaire’s website [Lemaire], he relates how he moved on extracting 13th roots of 200-digit numbers because the former “can now only be a record of memorization.”

[The 3.625 record time] means the 13th root of a 100-digit number is an immediate calculation (1 second), and the recordholder will be the one with the fastest time for writing, not with the fastest time for calculating. Every left part and right part of the 13th root of a 100-digit number can be memorized: there are only 3 and 4 digits to be memorized. Therefore the 13th root of a 100-digit number can be only a record of memorization, whereas the 13th root of a 200-digit number is a true task of mental calculation.

Lemaire here downplays the difficulty of memorizing all the starting and ending combinations; this is a stunning achievement of memorization. Referring to this record time and the number of possible answers, Lemaire in another paper [Lemaire 2009] states

Nearly 8 million combinations have been learned beforehand (consciousness of the future) through a generalization axiom which compresses these numbers into softer rules by working out patterns… Furthermore, this reverse artificial intelligence uses fuzzy sets to compute faster when dealing with the central most difficult part of the calculation; the fuzzier the computation, the faster it is but also the less accurate. We use this point to break records set after a great number of attempts.

The complete set does not need to be memorized; a “fuzzy” but fast attempt is made and if the answer is incorrect the next number is attempted. A competitor may also be asked a familiar number by chance. It is important to remember that mental calculators make many, many attempts at record times. Lemaire remarks on his website that it took 742 attempts in 2005 to beat his previous record in the 200-digit realm. This is not a criticism—athletes do the same—but simply an aspect of the competition.

The Current State of 13th Root Extraction

Wim Klein once said, “What is the use of extracting the 13th root of 100 digits?  ‘Must be a bloody idiot,’ you say. No. It puts you in the Guinness Book, of course” [Smith, 1983]. But in fact Guinness World Records dropped the category of 13th roots of 100-digit roots because the result is so dependent on the particular value of the power. And with the memorization capabilities witnessed today (most visible in the memorization of π), the field does not have the intellectual depth it once enjoyed.

Today a set of 13th roots is required for the world record as maintained by a separate organization, Rekord-Klub SAXONIA, and purposely includes even-numbered final digits of the powers that allow multiple combinations of final digits [Rekord-Klub SAXONIA]. It appears that no one has attempted this, and in fact it is likely that only Wim Klein, who passed away in 1986, could do it.

Part II of this essay describes a new way of extracting 13th roots of powers ending in 1, 3, 7 or 9. This method requires practice, but it allows someone to master 13th roots with a reasonable amount of number sense and memorization.

Go to Part II of this essay >>>

Printer-friendly PDF file of The 13th Root of a 100-Digit Number (Parts I-II)