Pressing Toward the Prize

Posts Tagged ‘algorithm

I recently came upon an article in Math Horizons magazine (Nov. 2010) that caught my eye: The Quest for God’s Number. Now I never knew God had a number, so I thought I better stop and check it out. The first thing I discovered is that God’s number is linked to God’s algorithm… who knew?

What this really has to do with is solving a Rubik’s Cube in the fewest moves, and hence the shortest amount of time. According to the article by Rik van Grol, “God’s algorithm is the procedure to bring back Rubik’s Cube from any random position to its solved state in the minimum number of steps. The maximum of all minimally needed number of steps is referred to as God’s number. This number can be defined in several ways. The most common is in terms of the number of face turns required, but it can also be measured as the number of quarter turns… Earlier this year, after decades of gradual progress, it was determined that God’s number is 20 face turns. Thus, if God’s algorithm were used to solve the cube, no starting position would ever require more than 20 face turns.” The article chronicles the process used to determine that God’s number is 20, and as one might imagine, it involves looking at an astronomically large number of possible pattern combinations, more than 4.3 x 10^19.

It was interesting to find that one of the mathematicians working on lowering the upper bound in search of God’s number used group theory in his calculations. He used the cube group, similar to the shape groups we studied in Abstract Algebra. His group had 6 moves on a cube fixed in space, Left, Right, Front, Back, Up, and Down, and the group operation was concatenation. He then divided the cube group into a nested chain of subgroups, and created an algorithm to eliminate some of the moves early on in the process. Using this method, he was able to show that the Rubik’s Cube could be solved in at most 85 moves. This was in 1979. By January of 1980 he had reduced it to 80, and by the end of that year, to 52. In 1995, another mathematician brought the upper bound to 29 face turns, but it was not until July of this year that the upper bound met the lower bound at 20.

Now that they have found God’s number for the classic 3x3x3 cube, they have turned their attention to the 4x4x4, 5x5x5, 6x6x6, and 7x7x7 cubes, all of which are currently on the market. There might be a hitch in this, though, since the 7x7x7 cube has 2.0 x 10^160 possible positions. Good luck with that!

I recently did a review of an article involving Gaussian integers (complex numbers whose real and “imaginary” parts are integers) in which the Euclidean algorithm was used to find the greatest common divisor (gcd) of two complex numbers. I had never heard of the Euclidean algorithm before, and the process described in the article involved complex numbers and several Greek letters, so I had no idea what was going on. Then, as luck would have it, only a few days later we discussed in math class how to use the Euclidean algorithm to find the gcd of two integers, that is, the largest number that divides both of them without leaving a remainder. It is based on the principle that the gcd does not change if the smaller number is subtracted from the larger number. If this process is repeated, the numbers keep getting smaller until one of them is zero. At this point, the gcd is the larger, non-zero number.

Here is a simple video that describes the process used to find the gcd of 123 and 36:

So what happens if the numbers are a bit larger?

Let’s find the gcd of 5,624 and 3,959:

\begin{aligned} 5,624 &= 3,959 \cdot 1 - 1,665\\ 3,959 &= 1,665 \cdot 2 - 629\\ 1,665 &= 629 \cdot 2 - 407\\ 629 &= 407 \cdot 1 - 222\\ 407 &= 222 \cdot 1 - 185\\ 222 &= 185 \cdot 1 - 37\\ 185 &= 37 \cdot 5 - 0 \end{aligned}

So the gcd(5,624, 3,959) = 37.

No matter how large the numbers, the process can be completed in a finite number of steps. It has been found that the maximum number of steps required is five times the number of digits in the smaller integer. If the numbers are sufficiently large, this still could take a very long time. The beauty of this algorithm is that a computer can be programmed to complete the steps in a matter of seconds, rather than the untold hours if calculated by hand. Although I still don’t fully understand this algorithm as applied to Gaussian integers, I have found it to be a wonderful tool for calculations on real integers.

  • None
  • gramsonjanessa: I can't wait to listen to your capstone presentation in the spring! Your proposal was really interesting and I'm interested to see how the linear alge
  • dewittda: This is impressive! I thought I was good because I solved a rubik‚Äôs cube once in an hour. I served with a guy in the Air Force who could solve a r
  • ZeroSum Ruler: The Euclidean algorithm should me the mainstream way we teach students how to find the GCF. Why isn't it? A mystery.