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

by Ron Doerfler and Miles Forster

NewMethodTableSmallPart I of this essay provided  background information that demonstrates the difficulty of the problem of mental extraction of 13th roots and the efforts of calculators to master it. But can it be possible for us to extract 13th roots of 100-digit numbers without devoting portions of our life to it? With a basic talent in mental arithmetic and some study, it can certainly be done, even if not in record time. We present a new method that involves no logarithms, no antilogarithms and no factoring, one that works with 13th powers that end in 1, 3, 7 or 9 (the cases attempted by record holders). The memorization consists of one table and a few formulas. A printer-friendly PDF version of Parts I and II is linked at the end of this essay.

The procedure as written here seems more complicated than it is in use. In practice insignificant digits are dropped as they occur, and hundreds digits are dropped when finding a result mod 100. Performing this calculation with pen and paper and no memorization is perhaps the best way to become comfortable with the process.

The Last Four Digits of the Root

First, we find the last 4 digits of the root. We find these from the last 4 digits of the power, which we denote as dcba where a is the final digit.

1.    We have already seen in Part I the rule for finding the last digit of the root:

The last digit of the root is the same as that of the power.

2.    The second-to-last digit of the root, as evident in the table of 2-digit endings in Part I, is

7b  mod 10               for a = 1 or 7

7(b-2)  mod 10        for a = 3 or 9

3.    The next pair of digits of the root (the 3rd and 4th from the end) are found from the formulas below. The mod 100 operation at the end is the remainder when divided by 100, so it is the last two digits if the result is positive, or 100 minus the last two digits if the result is negative. In fact, the formulas are much simpler than they appear because only the last two digits are kept in each term. The ceiling function rounds the result up to the next integer, and the floor function rounds the result down to the previous integer.

70d – 26b2 + b(20c + 8 ) – ceiling(b/3)    mod 100                 for a = 1

70d + 17(c+1) + 32b2 + b(40c + 42) – floor(b/3)    mod 100     for a = 3

For a = 7, we find 10000-dcba, then find the last four digits of the root from this new value that ends in 3, then subtract the answer from 10000

For a = 9, we find 10000-dcba, then find the last four digits of the root from this new value that ends in 1, then subtract the answer from 10000

A fast way to subtract dcba from 10000 is to subtract each digit from 9 and add 1 to the result.

Now we have the last four digits of the root and we can proceed to find the first four digits.

The First Four Digits of the Root

NewMethodTableSmallIt remains to find the first 4 digits of the root from the initial 5 digits of the power. We can do this by memorizing a short table of root vs. power starting digits, and then applying an offset.

The table to memorize is shown on the right. These values represent a minimum distribution that provides 4-digit accuracy over the interval of 100-digit powers. The values are actually accurate to 5 digits rather the 4 digits, so in fact the next digit is 0 for each value. Therefore, we have values for 5-digit accuracy that only require memorizing 4-digit numbers. Also, the values of n are convenient multipliers to use in our formula.The steps to find the first 4 digits of the root are:

1.    Find S as the first 5 (rounded) digits of the power divided by 10, so the 5th digit follows the decimal point. Find the values of P in the table on either side of S. If S is less than 1/3 the distance between these values of P, choose the R and P from the lower entry row, otherwise choose R and P from the higher row.

2.    Find the difference D below to the 4th decimal place. Then calculate the correction to 3 decimal places and add it to the value of R from the table:

D = (S – P) / 10000

correction = nD – 6(nD)2/R

Generally only the first term is required, but if D is larger the second term may provide an additional small correction that can be taken to a digit or two. Note that R ranges from 42 to 49 so we can replace 6/R with 1/7 or 1/8 depending on which end of the range R lies on.

3.    Then merge the first 4 digits with the last 4 digits to get the most reasonable last digit of the first four digits. For example, assume the first four digits were 2222. If the last four were 3333 the answer would be a simple merge to 22223333, but if the last four were 7777 the last digit 2 in 2222 would be adjusted down to 1 to get 22217777 because 1.7 is closer to 2.0 than 2.7. If the first digit of the last four digits is 5, we would use the 5th digit we calculated for the first digits to decide what is the closest merge.

Example Problems

The exercises presented below are intended to show the method in use with published problems faced by mental calculators. As mentioned earlier, achieving the record times listed here would require a great deal more memorization and practice.

Example 1: Alexis Lemaire Record 13th Root Problem (13.55 seconds)

The first example finds the 13th root of  the following number:

29288115834875201060553567352783652122196502020937
13928425510086152669633464222587770308279739304053


The last digits of the power are 4053, so the last digit of the root is 3, and 7(5-2) mod 10 = 1 so the last two digits of the root are 13. Then we work left-to-right from the formula below, ignoring any hundreds digits as we go:

70(4) + 17(0+1) + 32(5)2 + 5(40(0) + 42) – floor(5/3)    mod 100  =  06

so the last 4 digits of the root are 0613.

The first 5 digits of the power (rounded) are 29288 which we divide by 10 to get 2928.8, and the closest match in the table is 2869 so our first approximation is 44.73. Now D = (2928.8 – 2869) / 10000 = 0.0060 and the first correction nD = 12(0.0060) or 0.072 which we add to 44.73 to get a closer value of 44.802. The second term (0.00602) / 7 is too small to make a difference. Therefore we merge 44.80 and 0613, and we end up with 44800613.


Example 2: Gert Mittring’s Record 13th Root Problem (11.8 seconds)

This example finds the 13th root of a number ending in 1:

70664373816742861022340088302401573757042331707026
32731269721516000395709065419973141914549389684111


The last digits of the power are 4111, so the last digit of the root is 1, and 7b mod 10 = 7 so the last two digits of the root are 71. Then we work left-to-right from the formula below, ignoring any hundreds digits as we go:

70(4) – 23(1) + 26(1)2 + (1)(20(1) + 8 ) – ceiling (1/3)    mod 100  =  10

so the last 4 digits of the root are 1071.

The first 5 digits of the power (rounded) are 70664 which we divide by 10 to get 7066.4, and the closest match in the table is 7398 so our first approximation is 48.11. Now D = (7066.4 – 7398) / 10000 = -0.03316 and the first correction nD = 5(-0.03316) or -0.166 which we add to 48.11 to get a closer value of 47.944. Now (-0.1662) / 8 is very small, about 0.003, and subtracting this gets 47.941. Therefore we merge 4794 and 1071, and we end up with 47941071.


Example 3: Record 13th Root Problem by Wim Klein (1 minute 28 seconds) and Gert Mittring (39 seconds)

Here is an example for a power ending in 7:

88008443440489299575219015772236417859411720052615
65487280650870412023307854274990144578442271602817


The last digit is a 7, so we replace the final digits 2817 with 10000 – 2817 = 7183. The last digit of this root is 3, and 7(8-2) mod 10 = 2 so the last two digits of the root are 23. Then we work left-to-right from the formula below for 7183, ignoring any hundreds digits as we go:

70(7) + 17(1+1) + 32(8)2 + 8(40(1) + 42) – floor(8/3)    mod 100  =  26

so the last 4 digits of the root for 7183 are 2623. Then we find 10000 – 2623 = 7377 as the last four digits of our original power ending in 2817.

The first 5 digits of the power (rounded) are 88008 which we divide by 10 to get 8800.8, and the closest match in the table is 9437 so our first approximation is 49.02. Now D = (8800.8 – 9437) / 10000 = -0.0636 and the first correction nD = 4(-0.0636) or -0.254 which we add to 49.02 to get a closer value of 48.766. The second term (-0.252) / 8 = 0.008 so we subtract that to get 48.758. Therefore we merge 48.758 and 7377, and the closest 8-digit match is 48757377.


Additional Examples

As an additional exercise, you may want to try this record by Alexis Lemaire (3.625 seconds):

38934589793526802773496632556519305532657006082154
49817188566054427172046103952232604799107453543533

The answer is given at the very end of this essay.

Another exercise is this problem of Gert Mittring (11.8 seconds):

34288725041442601391808603643426837852427296517260
61936285121642529526002848517356482932010681285881

This answer can be found in the earlier photograph of Gert Mittring.

Additional examples can be created by installing Python. Then download this file and unzip the Python script. Double-clicking on that filename will launch a window that provides 13th powers ending in 1, 3, 7 and 9 along with their roots.

Conquering the 13th Root

Despite the perception of a general decline in mathematical ability, there are a number of outstanding mental calculators today who use advanced algorithms and memory techniques to eclipse their forerunners. The 13th root problem is clear evidence of this advancement. The early attempts by lightning calculators to find 13th roots of 100-digit numbers were beyond ordinary comprehension at the time, and the practitioners were considered marvels of nature. Today this problem is performed an order of magnitude faster and sometimes, with enough attempts, in a matter of seconds.

However, these feats require an astonishing dedication and number knowledge that still places these lightning calculators in a category beyond the understanding of the vast majority of people. We have attempted in this essay to present typical approaches taken by lightning calculators to this problem, both past and present, and we have described a new method that allows the mathematically-inclined person—with a reasonable degree of time and effort—to extract 13th roots of 100-digit numbers, and to do so at speeds that were once considered unthinkable.

Appendix: Derivation of the Doerfler-Forster Method

The final digit of the root is always the same as the final digit of the power since the power is of the form 4k+1. The formula for the second-to-last digit is apparent from the table of 2-digit endings presented above. The formulas for the two digits prior to these were found by manually searching for patterns in 4-digit tables of 13th roots, a task too mind-numbing to relate. Lemaire described this in an earlier excerpt quoted in this paper as “working out patterns.” The formulas were then verified over all the 4-digit endings by a software program.

The Newton-Raphson iterative approximation for solving the equation ap = N is given by

Derivation1

or

Derivation2

For an initial estimate R of N1/13, we can improve this estimate with the correction from one iteration:
Derivation3

Defining n = R / (13R13) = 1 / (13R12) and D = N – R13, the correction we add to the initial estimate is
Derivation4

Rather than attempt a second iteration of the Newton-Raphson method, we can simply add another correction called the Chebyshev term [Doerfler 1993].
Derivation5

The total correction is the sum of correction1 and correction2:
Derivation6

A table was created in software of all numbers n to 4 decimal places between 4×10-22 and 32×10-22. A column was added for R from the equation n = 1/(13R12), or R = (13n)-1/12, and another column was added for P, where P = R13×10-18. This table was manually searched for rows in which n (without the exponent) was an integer to high accuracy, while R and P rounded to 4 digits with 5-digit accuracy. These were candidates for rows in the memorized table, where the powers of 10 are incorporated into the method rather than the table. Finally, the values were tested until there was a sufficient distribution of table rows to provide accuracy over the range of possible roots R to 3 decimal places in the correction formula. The result is a table that provides sufficient accuracy of results while minimizing the task of memorization.

References

Doerfler, R. W. 1993. Dead Reckoning: Calculating Without Instruments, Gulf Publishing, Houston.

Hope, J. A. 1985. Unravelling the Mysteries of Expert Mental Calculation, Educational Studies in Mathematics, 16:355-374. Available from JSTOR at http://www.jstor.org/stable/3482445

Lemaire, A. 13th Root: The Official Integer Root, http://www.13throot.com/index2.html

Lemaire, A. and Rousseaux, F. 2009. Hypercalculia for the mind emulation, AI and Soc, 24:191-196. Available from SpringerLink at http://www.springerlink.com/content/c3v31q6k0r4854n3/

Mittring, G. 2004. In 11,6 Sekunden die 13. Wurzel ziehen, Spiegel Online, http://www.spiegel.de/wissenschaft/mensch/0,1518,333380,00.html

Rekord-Klub SAXONIA, Mental Calculation Records: Extracting Roots, http://www.recordholders.org/en/list/roots.html

Smith, S. B. 1983. The Great Mental Calculators: The Psychology, Methods, and Lives of Calculating Prodigies, Past and Present, Columbia University Press, New York.

Answer to Additional Example #1:

38934589793526802773496632556519305532657006082154
49817188566054427172046103952232604799107453543533

has a 13th root of 45792573.

<<< Go to Part I of this essay

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

2 thoughts on “The 13th Root of a 100-Digit Number (Part II)

  1. Scott Finegan November 26, 2011 / 9:31 pm

    As always, something interesting to be learned. I will be sure not to get involved in a competition…
    Nice to hear from you again, Scott! Thanks for your comment. — Ron

    Like

  2. j vos November 29, 2011 / 8:30 pm

    are you sure there is nothing wrong with the formulas for the fourth and third last digits?
    I’ve checked myself several times and I keep getting false results.
    ty very much.
    Based on someone else’s question I received by email, the problem could lie with dealing with the parentheses. For example, in the term 5(40(0)+42) of Example 1, the innermost parentheses are calculated first. The order would be 40(0) = 0, then 0 + 42 = 42, then 5(42) = 210. Then
    280 + 17 + 800 + 210 – 1 = 1306
    Since we are only keeping the last two digits at the end, we can drop any hundreds digits as we go to speed up the addition:
    80 + 17 + 0 + 10 – 1 = 06
    If a negative number appears, we would add 100’s until it becomes positive, so a result of -21 would give us 79 as the two digits.
    However, if you have a particular example of where you are getting an incorrect result, can you please post it or email it to me using the Contact Me link in the panel on the right? I’ll be happy to look at it and reply to you. — Ron

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s