Today's number is the Devil's Number
Rubik's Cubes are fun. Those of you who are interested in solving these may be well aware of God's Number, which is defined as the maximum number of moves needed to optimally solve any scrambled cube.
For the standard 3 x 3 x 3 Rubik's Cube, this number has been proven to be 20.
But there's the opposite idea as well. A Devil's Algorithm is defined as a single fixed sequence A such that for any starting state g, some power A^k(g) is solved. In other words, it's an algorithm that you can perform on any starting state, and eventually you will get to a solved state.
Then the Devil's Number is the corresponding number of moves in the shortest Devil's Algorithm.
An upper bound for this number is 43,252,003,274,489,856,000, which is the total number of permutations for a 3 x 3 x 3 Rubik's Cube. To see why, note that the Rubik's Cube has 8 corners and 12 edges. There are 8! ways to arrange the corner cubes. Each corner has 3 possible orientations, although only 7 of them can be oriented independently, so we have 3^7 (2,187) possibilities.
Then for the edges, there are 12! / 2 (239,500,800) ways to arrange them, restricted from 12! because edges must be in an even permutation when the corners are.
Eleven edges can be flipped independently, with the flip of the twelfth depending on the preceding ones (much like the corners), which gives 2^11 (2,048) possibilities. Multiplying all of those out gives:
8! * 3^7 * 12! / 2 * 2^11 = 43,252,003,274,489,856,000.
But this is a bit underwhelming. Of course, if your algorithm cycles through all group elements, then eventually it must hit the identity. Or in other words, if you go through every single permutation, then you will solve the cube. So can we do better?
Unfortunately, I don't believe we can. The upper bound we found is enormous because it comes from a very inefficient idea: blindly cycling through all possible cube states. To make progress, it helps to rephrase the problem in the language of group theory. The set of all Rubik's Cube configurations forms a group G, where each element represents a cube state, and each move sequence is also an element of this group.
A Devil's Algorithm, then would correspond to a single element A in G such that for every configuration g in G, some power of A sends g to the solved state. In other words, repeated application of A eventually reaches the identity, no matter where you start.
This means that the sequence
g, Ag, A^2g, A^3g, ...
must eventually hit the identity for every g in G. Equivalently, for every g in G, some power of A must equal g^-1.
In particular, this implies that the cyclic subgroup generated by A, denoted <A>, must be "large enough" to reach every part of the group. The size of this subgroup is exactly the order of A, say m, meaning that A^m = e.
Now here's the key constraint: If A has order m, then repeated application of A can only produce at most m distinct states before cycling. So for a single algorithm to eventually reach all |G| possible configurations (from appropriate starting points), we must have
m ≥ |G| / k
for some integer k that accounts for how many different starting positions can share the same cycle.
While making this precise requires more careful group-theoretic analysis, it suggests an important takeaway: any Devil's algorithm must have very large order comparable to the size of the Cube group itself.
So although the trivial upper bound is about 4.3 x 10^19, even optimistic lower bounds remain astronomically large. If a Devil's Algorithm exists at all, it cannot be short.
So to restate more clearly, in group terms, you're asking for a single element whose cyclic subgroup intersects every group element's orbit at the identity. This is a strong condition, and it's not obvious that such an element exists. And thus, it's not even obvious that such an algorithm exists for the cube.
So the Devil's Number remains mysterious: enormous if it exists at all, and possibly nonexistent.
