Looping or Repeating Algorithms?

[JTW2007]

Okay, will:

R U
L R F B
or
M' U

ever repeat? If anyone can give me any insight into why or why not, it'd be greatly appreciated.

 

[soccerking813]

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.

 

[cmhardw]

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]

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]

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.

 

[fanwuq]

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.

You sure?

 

[cmhardw]

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.

 

[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.

 

[ChromisElda]

RU repeats, I used to play around with that back when i used the LBL method.

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

 

[byu]

no RU is 105

This tool is helpful for calculating this stuff.

 

[miniGOINGS]

any algorithm, given time solves the cube

 

[qqwref]

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]

umm R U L D takes more than six hours to solve by hand (i was really bored on a trip to saskatchewan)

 

[qqwref]

But that's only 1260 moves... you're saying 1260 moves took you SIX HOURS?

 

[*LukeMayn*]

what that's like...

3 TPM (minute xD)

 

[qqwref]

Yeah, 3.5 TPM if he took exactly 6 hours, less TPM if he took more time XD

 

[Tetris Cube]

any algorithm, given time solves the cube

I know this is about a week old, but did anyone notice this? >_>

Here's an algorithm for you: U

How long will it take to solve?

 

[cookingfat]

any algorithm, given time solves the cube

I know this is about a week old, but did anyone notice this? >_>

Here's an algorithm for you: U

How long will it take to solve?

about half a second. 3 more Us and you're done.

 

[Tetris Cube]

That's only assuming the cube is already solved, he never said it was.

 

[AvGalen]

That's only assuming the cube is already solved, he never said it was.

Please read the discussion about the devils algorithm.