Looping or Repeating Algorithms?

[genericcuber666]

R U R' U' is a trigger

 

[Rnewms]

http://mzrg.com/rubik/ordercalc.shtml

 

[P14082003]

R U R' U' is a trigger

Yeah, but it makes the effect I describe

 

[JustinTimeCuber]

If anyone is looking for an order 7 then
(R U)15
is the easiest one I can find but it seems kinda lazy because it's so repetitive.

 

[Cale S]

If anyone is looking for an order 7 then
(R U)15
is the easiest one I can find but it seems kinda lazy because it's so repetitive.

7 cycle of edges or corners

 

[P14082003]

What does "order 7" mean?

 

[Cale S]

What does "order 7" mean?

takes 7 repititions to go back to solved

 

[P14082003]

So R U R' U' is order 6

 

[Lucas Garron]

What do you call those algorithms that when applied to a cube, after some repetitions, it returns to the starting pattern?

Elements with an order.
As others have pointed out, the cube is a group, so every algorithm has this property on 3x3x3 (and most puzzles you're care about).

 

[mark49152]

Here's a fun and simple one though: (R U)105

If anyone is looking for an order 7 then
(R U)15

15 * 7 = 105

 

[P14082003]

Elements with an order.
As others have pointed out, the cube is a group, so every algorithm has this property on 3x3x3 (and most puzzles you're care about).

Thank you!

 

[campos20]

So "R L2 U' F' d" (Order=2520) is the biggest one? But how to calculate that? There is a calculation on the order calculator site, but i can't see how it works. And i didnt studied Maths enough to understand that wiki article i guess. So does someone have a understandable explanation?

It'd be great if have mentioned some sources.

Hey

You need 2 T-Perms, to get to were you started. You need 6 sexy moves to get to where you started. And so on and so forth. But what is the longest of those cycles and how to calculate that?
I assume, that the longest cycle would be a sequence which moves all of the sides.

I should clarify that I'm talking about 3x3 in normal HTM metric.

BTW.: A few years ago i saw a website on which you can type moves and it gives you the cycle number. Is this website still up? I can't find it anywhere.

I run a program written by me in python (a very slow one, but it gets the job done) to test all sequences and count cycles. Basically, I used a problem I solved a while ago. It was quick to adapt. After one night of computations, it looks like @cuBerBruce is right. Longest sequence is 1260 in HTM. I also, using the program, could make a list to check all sizes of sequences, up to 6 moves.

Spoiler: Order of cycles and corresponding sequences

1260 - U L' U B' D2
990 - U L U F R' D'
840 - U L F2 B'
720 - U L U F D2
630 - U L U F R2
504 - U L' B R2
495 - U L F' U2 R'
462 - U L F R2 D'
420 - U L U2 B
360 - U L B'
336 - U L U F B2
330 - U L F R2 B'
315 - U L D R
280 - U L U F' R
252 - U L B R
240 - U L' F R2
231 - U L F' R'
210 - U L' U F2
198 - U L F2 R2
180 - U L R'
168 - U L R2
165 - U L U2 R' B
154 - U L U F R B'
144 - U L F' B2
140 - U L' U F'
132 - U L B' R
126 - U L U F2
120 - U L U R2
112 - U L F U2 R' B2
110 - U L F U2 L D R'
105 - U L
99 - U L2 F R2
90 - U L R
84 - U L B
80 - U L F
77 - U L F' R
72 - U L U F'
70 - U L F2 R F2
66 - U L U F2 R'
63 - U L'
60 - U L F'
56 - U L F' R2
55 - U L F' U' B' R
48 - U L U2 F
45 - U L U R
44 - U L F' D'
42 - U L' U2 L2
40 - U L U2 R
36 - U L F2
35 - U L2 D' L2
33 - U L R' B'
30 - U L2
28 - U L U' R
24 - U L2 R2
22 - U L F B' D2
21 - U L2 F L2
20 - U L U' R2
18 - U L U L F2
16 - U L U' F B
15 - U L2 U L2
14 - U L U F L' B
12 - U L2 F2
11 - U L F B' D2 U L F B' D2 **
10 - U L U' F
9 - U L B2
8 - U L2 D
7 - U L U' B
6 - U2 L2
5 - U L U L'
4 - U
3 - U2 L2 U2 L2
2 - U2

** this one I added manually. Explanation is bellow. Basically, 2 sequences of length 22.

It's clear if N is even and there's a sequence of size N, there's also a sequence of size N/2. For example: sexy move, as you said, has a length of 6. Then, 2 sexy moves has length of 3.

 

[xyzzy]

There is a calculation on the order calculator site, but i can't see how it works.

That one's written in JavaScript and you can just look at the source code.

So does someone have a understandable explanation?

The brute force way to calculate the order is to repeatedly apply the move sequence until you return to a solved state, and count the number times you applied it. The fast way (for 2x2x2 and 3x3x3; doesn't work on larger cubes because of indistinguishable centres) is to trace cycles on the stickers, and take the least common multiple of the lengths of all the cycles.

Edit: Looks like I forgot to answer the actual question, lol. To determine what the largest possible order is, what we would like to do is to go through all 43 quintillion states and determine each of their orders, but this is simply not possible within a human lifetime.

Instead, all we really need to do is to go through the possible cycle structures, since it doesn't really matter exactly which pieces/stickers are being cycled. (For example, R U2 R' U2 has two 3-cycles and three 5-cycles of stickers, and for our purposes is the same as any other move sequence that has two 3-cycles and three 5-cycles of stickers, such as L F2 L' U' R2 F2 R2 U R2 F2 R2.) This has something like a few hundred cases and you could go through all the possibilities with a bit of patience.

It's clear if N is even and there's a sequence of size N, there's also a sequence of size N/2. For example: sexy move, as you said, has a length of 6. Then, 2 sexy moves has length of 3.

We can actually say more than this. If we have a move sequence of order n, then for every factor d of n, there is a sequence of order d, and we can get such a sequence by repeating an order-n sequence n/d times. To modify the example, 2 is a factor of 6, so you can make an order-2 sequence out of the sexy move just by doing the sexy move thrice.

 

[Smiles]

(Uz') repeat... i've done it 800 times and then just gave up

tried this, after 60 turns you get a 7 cycle for edges and 3 cycle for corners,

least common multiple is 21

60*21 = 1260
not bad

without cube rotations it would be U R D L, which would have a length of 315 instead

 

[campos20]

Source
I'm not sure if it's missing some.

Spoiler: Cycles and sequences

1260 - U L' U B' D2
990 - U L U F R' D'
840 - U L F2 B'
720 - U L U F D2
630 - U L U F R2
504 - U L' B R2
495 - U L F' U2 R'
462 - U L F R2 D'
420 - U L U2 B
360 - U L B'
336 - U L U F B2
330 - U L F R2 B'
315 - U L D R
280 - U L U F' R
252 - U L B R
240 - U L' F R2
231 - U L F' R'
210 - U L' U F2
198 - U L F2 R2
180 - U L R'
168 - U L R2
165 - U L U2 R' B
154 - U L U F R B'
144 - U L F' B2
140 - U L' U F'
132 - U L B' R
126 - U L U F2
120 - U L U R2
112 - U L F U2 R' B2
110 - U L F U2 L D R'
105 - U L
99 - U L2 F R2
90 - U L R
84 - U L B
80 - U L F
77 - U L F' R
72 - U L U F'
70 - U L F2 R F2
66 - U L U F2 R'
63 - U L'
60 - U L F'
56 - U L F' R2
55 - U L F' U' B' R
48 - U L U2 F
45 - U L U R
44 - U L F' D'
42 - U L' U2 L2
40 - U L U2 R
36 - U L F2
35 - U L2 D' L2
33 - U L R' B'
30 - U L2
28 - U L U' R
24 - U L2 R2
22 - U L F B' D2
21 - U L2 F L2
20 - U L U' R2
18 - U L U L F2
16 - U L U' F B
15 - U L2 U L2
14 - U L U F L' B
12 - U L2 F2
11 - U L F B' D2 U L F B' D2 **
10 - U L U' F
9 - U L B2
8 - U L2 D
7 - U L U' B
6 - U2 L2
5 - U L U L'
4 - U
3 - U2 L2 U2 L2
2 - U2

** this one I added manually. Explanation is bellow. Basically, 2 sequences of length 22.

 

[stwert]

I don't know the proper terminology for these ideas, so bear with me. Every algorithm or sequence of moves can be repeated until you reach your starting state. Eg. Sexy move is 6 iterations for a full loop. U2 is 2 iterations.
Question: what is the average loop length if you just repeated a standard wca 3x3 scramble until the cube was solved? I don't know if this is an easy calculation or something you'd have to brute force like God's number.

 

[DuckubingCuber347]

Didn't you just make this post on the "Probability Thread"?

 

[stwert]

Didn't you just make this post on the "Probability Thread"?

Yeah, I removed it cause I realized it wasn't exactly probability and maybe fit better as its own thread. You were too quick to read and like it.

 

[Lucas Garron]

An interesting question!

It's definitely possible to compute an exact answer by breaking down all the possible combinations of orbit cycles and tallying the possible orders ("order" is the group theory term for "loop length").

But that's a bit tricky, so I started with 10,000 simulations:

https://codepen.io/lgarron/pen/wvewRrr?editors=0010

This gives me an average order of very roughly ≈120. But as you can see, it didn't even generate a single scramble with order 2 or 3, not to mention other possible orders. That's expected, but the wide range of values means simulations can vary quite bit.

 

[stwert]

Wow, that's fantastic. Thanks for running that. I find the spikes at multiple of 6 orders very interesting, but I guess not too unexpected. I wonder if finding the mode would be more appropriate than the mean. Would it be safe to say it's 60? Or not a big enough sample? Also basically none over 1000 is a little surprising, given that we've got... Wait I don't even know how many valid unique scrambles there would be.