Last edited by Stefan; 06-17-2012 at 04:12 AM.
oops. should have looked up the meaning of "traverse"
From your algebra, you assume that your "+" function, which does not add anything but rather composes two moves on the cube (g*a and g*b), is commutative. The only little mistake here is assuming that the composing functions has the same properties as the plus function, since you gave them the same symbol. If we let + be the function that composes two moves on the cube, as you have, then obviously U+R =/= R+U, regardless of them being g*a or g*b, so there still could be a Devil's/God's Algorithm.
EDIT: I was being stupid. You're right whauk and Stefan.
Last edited by calebcole203; 06-17-2012 at 10:16 PM.
No, his proof is alright. He didn't write
he specifically wrote
Yes, there is no full sequence g such that g^a=R and g^b=U for some a and b. This is a pretty clear result and there are a bunch of ways you can explain it - here's another:
- every sequence has a maximum order of 1260 (if the centers are fixed)
- g^a is always one of those 1260 positions (one of which is solved) for any integer a
- performing one of those positions and then another will always give one of those positions, since (g^a)(g^b) = g^(a+b)
- if both R and U are among those 1260 positions, then all sequences like RU, UR, UR2, RUR'URU2R', etc. are among those 1260 positions, and clearly there are more than 1260 of those, so we have a contradiction.
As far as I know, though, there's nothing theoretically stopping us from making a sequence that is about 1/1260 of the length of the full Devil's Algorithm, such that applying the sequence over and over will go through every position at some point (i.e. the sequence 1260 times is its own Devil's Algorithm). It wouldn't help much in practice, though, since it would still be over 10^16 moves long.
I have seen this web site (http://anttila.ca/michael/devilsalgorithm/) that gives a definition for a Devil's Number and a Devil's algorithm that is similar or the same as what's being discussed in this thread.
What hasn't been stated clearly is if the last iteration of the sequence must execute the full sequence, or if the Hamiltonian circuit can be completed somewhere in the middle of the last iteration of the sequence. If we allow the Hamiltonian circuit to be completed somewhere in the middle of the sequence, we can find upper bounds for (this definition of) Devil's number below
For example, we can let P=UR, and find a place in my Hamiltonian circuit where URUR occurs. We can start the cycle at that point, and then call the rest of the Hamiltonian circuit Q. So the Hamiltonian circuit is PPQ. Then we can cyclic shift to get the Hamiltonian circuit PQP. We can consider that we just need to repeat PQ, and after the P is executed the 2nd time, we will have done a Hamiltonian circuit. Since PQ has length 43,252,003,274,489,855,998, we have that number as an upper bound for Devil's number.
Of course, larger sequences that can be used for P are easy to find within my Hamiltonian circuit, reducing the upper bound even more.