Charles Petzold

I do have work to do today. I have an article for MSDN Magazine due on Saturday, and I have a book to finish by the end of this month. But this morning when Deirdre emailed me an article about Alexis Lemaire calculating 13th roots of 200-digit numbers in his head I got a little, well, distracted.

Here's the deal: Two days ago Alexis Lemaire was given a "random" 200-digit number and in 70.2 second he calculated the 13th root of the number, or 2,407,899,893,032,210.

I put "random" in quotation marks because obviously the particular 200-digit number wasn't entirely random. It was a 200-digit number that has an integral 13th root.

So I started thinking: Exactly how many 200-digit numbers have integral 13th roots? Maybe it's not so many. Maybe this is less a calculational job than a memorization job. For example, suppose you wanted to calculate 13th roots of 20-digit numbers. There are only 6 of them: 29 (to the 13th power equals 10,260,628,712,958,602,189) through 34 (to the 13th power equals 81,138,303,245,565,435,904). But I had no feel for how that fact could be extrapolated to 200-digit numbers.

Solution 1. Write a Program!

Yeah, except that when you want to mess around with 200-digit numbers, you're beyond the realm of common integer arithmetic. You need arbitrary-precision integers, and I was actually on my way to writing a tiny arbitrary-precision integer class in C# that derived from List<int> to store the digits. I had the + override finished and when plotting out my strategy for * I figured I should look around for somebody else's arbitrary-precision integer library. After all, I do have work to do today.

After a little bit of search, and contemplating downloading the GNU multi-precision (GMP) library, I stumbled upon this .NET Matters article by Stephen Toub where he recommends using the J# BigInteger class. I didn't even have to download anything new!

This ThirteenthRoots.cs program requires a reference to vjslib.dll (which is probably on your machine if you have Visual Studio installed) and it has an include statement for the java.math namespace.

The program uses the pow method to calculate the 200-digit number Alexis Lemaire was given, which I won't repeat here. The program also attempts to find all 200-digit numbers that have integral 13th roots. I don't know if this part of the program is working right or not; I suspect the brute-force method I implemented might require several years or even centuries of processing time.

However, while attempting to refine the range of numbers the program tests, I realized I didn't need to write a program at all. Duh!

Solution 2. Do the Math!

The math to determine how many integers have 13th powers with 200 digits is actually quite easy and can be done with the Windows Calculator. We're looking for all integer values X that satisfy the following relationship:

10¹⁹⁹ ≤ X¹³ < 10²⁰⁰

or:

10^199/13 ≤ X < 10^200/13

The calculation on the left gives you an X value of 2,030,917,620,904,735 with an infinite decimal so the lowest integer is 2,030,917,620,904,736. Similarly, 10 to the 200/13 power is 2,424,462,017,082,328 with an infinite decimal that can be ignored. There are therefore 393,544,396,177,593 numbers that have 13th powers with 200 digits. That results prompts me to be much more impressed with Alexis Lemaire's feat, and it confirms that the Yahoo article was actually accurate when it referred to "a possible 393 trillion answers."

Solution 3. Look it up in Wikipedia!

While preparing this blog entry, I wondered if there might be a term akin to "square root" and "cube root" that is better than "13th root," and I came upon this Wikipedia entry on "13th Root" that contains precisely the information that I calculated and some other little nuggets as well.

The moral for the day is: Code is cool but Wikipedia is speedier.