13th roots and Rubik's cube

In the comments here a few days ago, commenter Michael S. pointed to this article telling us that the record for finding the 13th root of a 200-digit number has been broken by Alexis Lemaire. It is mentioned that the record for the 13th root of a 100-digit number was 23 minutes in 1970, and now Lemaire can do it in under four seconds. This seems a bit suspicious to me, because it seems like it would take more than four seconds just to read the problem and write down the answer, but presumably it's legitimate. I found what looks like a set of rules here.

What I'm curious about is how much of this improvement is an improvement in the existing methods, and how much of it is coming up with new methods. I suspect that some part of the method takes advantage of certain strange properties that only someone who was looking really hard could find. For example, in the case of cube roots it turns out that the cubes of 0, 1, 2, ..., 9 each end with a different digit (0, 1, 8, 7, 4, 5, 6, 3, 2, 9). So if, for example, you have a number that you know is a perfect cube and it ends in 3, it must be the cube of something that ends in 7. There's a similar trick for fifth roots -- n⁵ and n always end in the same digit.

From what I can gather the methods for the 13th root are a little less ad hoc; at least one person's method basically works by taking the logarithm of the 100-digit number and dividing it by thirteen to get the most significant digits of the 13th root of a 100-digit number; then looking at the last few digits of the 100-digit number gives you the last few digits of its 13th root. One occasionally sees large numbers given in this way, where the first few digits can be found by logarithms, the last few digits by modular arithmetic, but the middle is a lot harder to compute. I can't find descriptions of the method which these mental calculators use for finding 13th roots of 200-digit numbers; one might expect it to be similar, but it doesn't necessarily have to be.

An analogy comes to mind with solving the Rubik's cube. There are people who can solve it very quickly. But there are two metrics for the speed of solving it -- how many "moves" do you have to make to get it back to the starting position, and how many seconds does that take? The first of these is the more mathematically interesting question. A simple combinatorial argument says that there must be positions which are 18 moves from the initial position. The number of positions the Rubik's cube can take is (8! × 38) (12! × 2¹²)/12 = 43,252,003,274,489,856,000. To see this, note that to specify a position of the Rubik's cube, one must specify:

• the positions of the eight corner pieces, in 8! ways


• how each of these is "twisted", in 3⁸ ways


• the positions of the twelve edge pieces, in 12! ways


• how each of these is "flipped", in 2¹² ways

and the factor of 12 arises because it turns out not to be possible to get every possible combination of flips and twists. (Douglas Hofstadter referred to these as "conservation laws" in one of his Metamagical Themas columns, because they reminded him of certain laws about conservation of spin or color in particle physics.) Now, let's say you're randomly scrambling a Rubik's cube. There are twelve "moves" you can make from the initial position -- you can twist each of the six faces in either direction. After that, at each juncture there are eleven moves you can make -- it would be redundant to turn a face clockwise and then counterclockwise on the next move. So the number of positions that you can reach in exactly n moves is 12 × 11ⁿ; summing these up for 1, 2, ..., 17 gives a number which is less than the number of possible positions of the Rubik's cube. So there are positions which are at least 18 moves from the start. It turns out that there are positions that need 26 such moves ("quarter turns"), and an algorithm is known that can solve any position of the Rubik's cube in 35 quarter turns; see this Wikipedia article, or this paper for an idea of the methods. (They use a different metric, in which turning a face by 180 degrees counts as one move, not two; this lets one replace 18, 26 and 35 above by 15, 20 and 26.)

But the people that solve the cube very quickly are interested in the actual amount of time, which means first that they would not want a method that required lots of standing around thinking, and second that there are considerations of manual dexterity that just don't come into play if you're trying to minimize the number of moves. You can imagine a Rubik's cube competition where people are challenged to unscramble the cube in a minimal number of moves, as opposed to the smallest amount of time; however it would be a much different game.

Unfortunately, the analogy to the 13th-root problem breaks down. That's because in the Rubik's cube case, you can see what the players are doing. So it's possible to count the number of moves they make. You can't count the number of elementary arithmetic operations that someone does in their head when trying to extract a 13th root, and furthermore there seems to be an element of synaesthesia in some of their calculations, so hat they see as an elementary arithmetic operation might not be how a "normal" person would define it. What model of computation one uses is tremendously important here.