• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 35,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

Repeating Algs Question

soccerking813

Member
Joined
Jan 27, 2009
Messages
735
Location
North Carolina, USA
R U will repeat, but I am not sure about the others, I will test it though.

Edit:
M' U will also repeat.

Edit2:
L R F B will also repeat.

I am not sure exactly why any move sequence will repeat, but I think that any sequence will repeat, regardless of how long it is.
 
Last edited:

cmhardw

Premium Member
Joined
Apr 5, 2006
Messages
4,106
Location
Atlanta, Georgia
WCA
2003HARD01
Absolutely any algorithm, repeated over and over, will eventually return you to the same state you started at. Think of it this way. There are 43,252,003,274,489,856,000 positions on a cube. If you repeat an algorithm, even one that produces a unique position every time, then you must eventually come back to a position you were at before.

I don't remember how to make precise the proof that you will eventually return to the same starting position, but it is using essentially the same idea. If you break any algorithm down into it's net effect on the cycles of pieces, and orientations of pieces you can then calculate the least common multiple of when each of those effects returns it's piece type to solved. This essentially returns the cube to the original state before you started.

Chris
 

JustinJ

Premium Member
Joined
Oct 15, 2008
Messages
635
Location
Waterloo, Ontario, Canada
WCA
2008JAFF01
Of course they will. Badmephisto gives a really good reason as to why in his setting up cases video, it's something like, if it never repeated, you would be creating an infinite amount of states on the cube, but there is a finite amount which means all sequences must repeat.
 

JTW2007

BattsMan
Joined
Nov 29, 2008
Messages
1,591
Location
The BattCave
WCA
2008WARL01
YouTube
2007JTW
Thanks for the info everyone. So does this mean that any 6-Gen alg repeated over and over will take a cube through every possible position before restoring it to the solved state.
 

cmhardw

Premium Member
Joined
Apr 5, 2006
Messages
4,106
Location
Atlanta, Georgia
WCA
2003HARD01
Thanks for the info everyone. So does this mean that any 6-Gen alg repeated over and over will take a cube through every possible position before restoring it to the solved state.
That algorithm is called "Devil's algorithm" and has not yet been discovered. As far as I know the length of that algorithm is not known either. It would be mathematically beautiful if there existed an algorithm of length 43,252,003,274,489,856,000 that went through every possible position. I don't think it's known what the length of a shortest possible Devil's Algorithm is right now.

No, in general algorithms repeat with a maximum number of repetitions of, I believe it is, 1260. I might be wrong on that number, I will look into it to make sure I'm not giving you a bogus wrong answer.

For example, starting the algorithm R U from the solved state you will re-solve edges every 7 repetitions. You will re-solve corners every 15 repetitions. Using the idea of least common multiple you would repeat this algorithm 105 times until you achieve the solved state again. This algorithm has 2 moves, and you will cycle through distinct positions every turn, meaning you will cycle through 209 distinct positions before returning to the original state before you started applying this algorithm.

Chris

--edit--
Bruce thanks for correcting me on the upper bound for the number of repetitions. I edited the number in my post.
 
Last edited:

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
cuBerBruce
Thanks for the info everyone. So does this mean that any 6-Gen alg repeated over and over will take a cube through every possible position before restoring it to the solved state.
No, definitely not. It is well known that any <U,D,L,R,F,B> alg returns you to the starting state in <= 1260 repetitions. So any <U,D,L,R,F,B> alg that cycles through all possible cube positions must consist of at least 34326986725785600 moves.

EDIT:
Chris, I carefully noted that the number 1260 applies to <U,D,L,R,F,B>. For <U,E,R,M,F,S>, the number is 2520.
 
Last edited:

ChromisElda

Member
Joined
Feb 21, 2009
Messages
31
RU repeats, I used to play around with that back when i used the LBL method. :p

Repeats after you do it about 67-68 times if I remember
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,830
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
qqwref2
I made a program a while back that would look at the order of an algorithm on 3x3, 4x4, or 5x5. The longest one I found, for the 5x5, was (Fw' B2 x) - you have to do that one 978120 times to get back to solved! (Of course, no, I did NOT test this by hand...)
 

miniGOINGS

Member
Joined
Feb 27, 2009
Messages
3,052
umm R U L D takes more than six hours to solve by hand (i was really bored on a trip to saskatchewan) :)
 
Top