Home > Life in General > Rooted

## Rooted

November 26th, 2004

i was intrigued by this report in the Australian of a mathematical genius who can find the 13th root of 100-digit number in seconds. I was even more intrigued to learn that the number was “selected at random”. The odds against a randomly selected 100-digit number having an integer 13-th root would be a nice problem for a math genius to solve in seconds[1] so I wonder what is meant by this.

Maybe you only have to derive the integer part, which, if my workings below are correct, is an eight-digit number lying in a fairly narrow range. Someone who knew the first three or four places of their log tables and was quick at interpolation could probably manage the feat in the time described.

Or maybe the number is selected from a list of 100-digit 13th powers. This would make life a little easier since you can get the last digit free or cheaply (with preparation, you could probably get a good handle on the last two digits).

I’m not planning on trying this at home, though.

fn1. Not being a math genius, I’d proceed as follows. The number lies between 10^99 and 10^100, and there are roughly 10^100 such numbers. The 13th root lies between 10^99/13 or about 10^7.63 and 10^100/13 or about 10^7.69 and there are about 10^6 integers in this range. So the odds against are 10^94 to 1, which might fairly be described as “long”. Time taken, about 150 seconds, which I guess counts as “in seconds” if you’re feeling generous.

Categories: Life in General Tags:
1. November 26th, 2004 at 08:14 | #1

As to the question of how you select it surely you find the 13th root of the largest and smallest 100 digit number then, select a random integer between the two – There would be around 8 million of these I think from a quick calculation, and put this to the power 13 and present it to the person to solve.

2. November 26th, 2004 at 08:17 | #2

That was more or less what I meant by my last observation

3. November 26th, 2004 at 08:51 | #3

sounds like another example of DIVIDE and conquer!

4. November 26th, 2004 at 12:32 | #4

Here is one algorithm from Wikipedia
http://en.wikipedia.org/wiki/Shifting_nth-root_algorithm
tho the “maths genius” is unlikely to have used it exactly , unless there is some method for raising numbers to the thirteenth power in your head .

5. November 26th, 2004 at 15:07 | #5

The clue may lie in the remark “find a good algorithm”. Incidentally, back when I was young and clever I always found it easier to work out the formula for things like quadratic equations each time from scratch rather than memorise a load of formulae on the off chance that a question might come up about them; I found it easier to learn principles than unsystematic data.

Back to our muttons. Here is a “good” algorithm that occurs to me, though I haven’t tried it out. Start with a range of iteration seeds in roughly the right range, chosen to make calculations easy; maybe they’ll all be powers of two or of ten or something, I haven’t checked yet. Again, these aren’t memorised, a formula for generating them is used to get a good first estimate.

Then use the variant of Newton’s algorithm that doesn’t use division directly but uses multiplication by a fixed reciprocal; don’t bother getting the precise reciprocal, just get a rounded version.

Then slam in a few iterations and you’re there.

One feature of what makes a “good” mental arithmetic algorithm is that it only involves a few actively changing variables, though it can have some preset values as well. It’s a trade off between human short term and medium term memory.

Of course, this is all highly speculative. I would be interested to know what method was actually used. It may even have been simpler than I have suggested, though it must have fitted in with the workings of the physical brain.

6. November 26th, 2004 at 15:36 | #6

I reckon 13th roots of 100 digit numbers would be a pretty safe thing to lie to a reporter about.

They are very unlikely to check, and anyway you can’t do this kind of calculation with a calculator or ordinary spreadsheet programs without horribly sophisticated calculation methods…

7. November 26th, 2004 at 21:05 | #7

It turns out there is any amount of material about this guy on the net. He has been entering competitions for years and apparently holds 24 records. I think this latest was a competition in the UK. In this instance the answer was 47 941 071 solved in 11.8 sec beating some Frenchman who required 13 odd seconds. One site pointed out you’d be pushing it uphill to even write down the 100 digit number in 11.8 seconds.

As many of the sites tell you, the 13th root is taken because the last digit is the same as the given 100 figure number – this is a curious property of the 13th root. The significance of this escapes me but it meant he knew from the beginning that the answer will end in a 1. Perhaps it helps. I checked and it’s true up 9^13 (enter into the Google search panel) and after that it goes into exponents. Also it seems the 13th root of a 100 digit number lies between 40 and 50 million which also must be a great help.

He says he uses an algorithm but I didn’t come across a site saying what it is. He has been calculating roots since he was 8 but he apparently failed maths at school and got an average of 3.8 for his matriculation which, on a scale from 1 to 5 with 1 at the top, is very ordinary.

8. November 26th, 2004 at 21:14 | #8

I reckon 13th roots of 100 digit numbers would be a pretty safe thing to lie to a reporter about.

Also a good way to try to score with first-year female maths students in the Uni bar – perhaps the only way to use the word “root” in your opening line without getting a drink thrown in your face.

9. November 26th, 2004 at 23:23 | #9

The integers whose thirteenth power has 100 digits are those between 49,238,808 and 58,780,138 inclusive. There are 9,541,331 of them. So the answer is about 9.5 X 10^-92.

10. November 27th, 2004 at 12:45 | #10

http://members.aol.com/beagenius/root2.html
Looks like the technique used is the shifting nth root algorithm . You need to remember the 13th powers of 2 to 9 only approximately. For those kiddies at home these are exactly 8192 , 1594323 ,67108864 , 1220703125 ,13060694016 ,96889010407 ,
549755813888 ,2541865828329 and you’ll have to use all the memory techniques you know .

11. November 28th, 2004 at 12:37 | #11

Could be a savant or could be a trick as BIll Slater suggests.

12. November 28th, 2004 at 18:04 | #12

Your numbers can’t be right James. Google says 58 000 000 ^ 13 is 8.4 * 10^100 which has 101 digits. 🙂

He is no savant. He is a psychologist consulting about gifted children.

13. November 28th, 2004 at 18:06 | #13

That is supposed to read 58 million to the power of 13 equals 8.4 times 10 to the power of 100.

14. November 29th, 2004 at 12:56 | #14

You are right Mike. There were other errors too. Here’s another attempt:

The integers whose thirteenth power has 100 digits are those from 41,246264 to 49,238825 inclusive. There are 7,992,562 of them, which is what Steve said. There are .9 X 10^100 numbers with 100 digits.