# The longest alg?



## Kenneth (Aug 18, 2010)

There is a shortest alg for a case, we know that, But is it a longest?

To simplify we assume it is a 2-gen RU, say U-PLL, what is then the longest alg for it using the two sides without repeating states?


----------



## ErikJ (Aug 18, 2010)

stryker Z: U' R U R U' R U2 R U' R' U' R U R' U' R' U R U' R U' R U R U' R' U' R' U' R U' R U'


----------



## lilkdub503 (Aug 18, 2010)

Honestly, isn't it possible to make an algorithm infinitely long? We could just keep undoing and redoing moves within an algorithm like the stryker.


----------



## Kirjava (Aug 18, 2010)

Not infinite. There is a limit if you can't repeat states.

Very very very silly long though.


----------



## uberCuber (Aug 18, 2010)

lilkdub503 said:


> Honestly, isn't it possible to make an algorithm infinitely long? We could just keep undoing and redoing moves within an algorithm like the stryzer.



ahem..



Kenneth said:


> There is a shortest alg for a case, we know that, But is it a longest?
> 
> To simlify we assume it is a 2-gen RU, say U-PLL, what is then the longest alg for it using the two sides *without repeating states?*


----------



## hawkmp4 (Aug 18, 2010)

(R U')*62 R' U' R' U R U R' U' R' U' R' U R'.
EDIT: Missed a move.


----------



## anders (Aug 18, 2010)

Kenneth said:


> There is a shortest alg for a case, we know that, But is it a longest?



The Devil's Algorithm: An algorithm that takes a puzzle through all possible configurations.


----------



## waffle=ijm (Aug 18, 2010)

http://www.youtube.com/watch?v=4ILvYNg5EFc


----------



## uberCuber (Aug 18, 2010)

anders said:


> Kenneth said:
> 
> 
> > There is a shortest alg for a case, we know that, But is it a longest?
> ...



and does anyone know what this algorithm is for the 3x3? We have the devil's alg for floppy cube, but..


----------



## PatrickJameson (Aug 18, 2010)

anders said:


> Kenneth said:
> 
> 
> > There is a shortest alg for a case, we know that, But is it a longest?
> ...



Although I have no evidence to back this up, I'm pretty confident in saying that there is no algorithm that can do that without repeating states.

PROVE ME WRONG.


----------



## uberCuber (Aug 18, 2010)

PatrickJameson said:


> anders said:
> 
> 
> > Kenneth said:
> ...



its possible on floppy cube, why not 3x3?  lol not that I believe that but I'd still like to see some evidence in either direction


----------



## hawkmp4 (Aug 18, 2010)

http://www.jaapsch.net/puzzles/hamilton.htm 

"Although the Petersen graph is vertex-transitive, it does not occur as a Cayley graph of some group. It has been conjectured that Cayley graphs always have a Hamilton cycle. If this is true, then every puzzle with a group structure has a Hamilton cycle. In particular, the puzzles with unrestricted reversible moves and distinct pieces, such as the 2×2×2 and 3×3×3 Rubik's Cubes, the Pyraminx, and the 12 colour Megaminx, will have Hamilton cycles."

Keep in mind, the Devil's algorithm may not be the longest algorithm that performs, for example, a U permutation.


----------



## Sa967St (Aug 18, 2010)

waffle=ijm said:


> http://www.youtube.com/watch?v=4ILvYNg5EFc



I was just about to post that.


----------



## Kenneth (Aug 18, 2010)

The thing that started me was that I was bored yesterday and started to search for a really crappy A-PLL using RUF,

Like this one: U2 R2 F2 R' U' R' F2 R2 F2 R U' F2 R2 U2 R2 F2 U2 R U2 (19f)

Then I started to think it must be a commutator inside and the rest will be setup turns. But you can't set up the corners and commutate them in so many ways using only three sides, it must be a limit to the length if you don't want it to do/undo states and the same must apply for using all sides but more combinations of course.

BTW: A using only q-moves : F' R' F R U' R' F' R F R F U F' R' F U' F' U (18f) ... I think it is the shortest using only quarters and three sides but I did not search the whole list I got.


----------



## qqwref (Aug 18, 2010)

Here is a long U perm. I don't know if it repeats states but I don't think it does.

(R U R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2)104 R' U2 R2 U' R U' R U' R' U R U' R' U' R U R' U R U2 R' U' R U R' U R U2 R' U

Length is 5646 moves.


----------



## Kenneth (Aug 18, 2010)

Man, that's mad!


----------



## cmhardw (Aug 18, 2010)

qqwref said:


> Here is a long U perm. I don't know if it repeats states but I don't think it does.
> 
> (R U R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2)104 R' U2 R2 U' R U' R U' R' U R U' R' U' R U R' U R U2 R' U' R U R' U R U2 R' U
> 
> Length is 5646 moves.



If you'll allow me to step outside of the RU restriction to expand on this a bit, I can increase your alg to 42,157,984 turns, and I'm fairly certain that no state is repeated, though I'm a little unsure as to how to formally prove this.

Replace every R in your alg with: (D' L' U' R')*629 D' L' U'
Replace every R' with: (U L D R)*629 U L D
Replace every R2 with: [(D' L' U' R')*629 D' L' U']*2
Replace every U with: (R' D' L' U')*629 R' D' L'
Replace every U' with: (L D R U)*629 L D R
Replace every U2 with: [(R' D' L' U')*629 R' D' L']*2

No two consecutive moves would give any cancellation, and as far as I can tell no states should repeat.

If you wanted to expand on this further, then use a long algorithm with order 1260.

--edit--
I will also look at this from the viewpoint of RU turns only, I think this is really interesting! Also, I think I have a conjectured answer, but give me some time to type it up.

Chris


----------



## Ravi (Aug 18, 2010)

I suspect that there are Hamiltonian paths and cycles on the Rubik's Cube, and there are probably even non-repeating algs of 43252003274489855999 moves for every unsolved position. No, I don't have proof of either claim. A possible proof may start with finding a Devil's Algorithm for Thistlethwaite's group G2 (generated by U, D, F2, R2, B2, and L2), then finding a path between all of the cosets of this in the cube group.

Or something like that.

If we're just talking about finding "long" algs rather than the longest ones, then you can start with an ordinary alg and repeatedly substitute alternatives for each move in it. (It appears this is what qqwref did.) (EDIT: Well played, Chris.) Or you could get a million-move-long scramble, then solve that into your desired position with the method of your choice. It's still unlikely that there will be any repeats.


----------



## cmhardw (Aug 18, 2010)

Ok, so I think I have a potential answer. I will put it out as a conjecture, and it can be either proven or disproven.

*Hardwick conjecture:*
The longest possible algorithm for any effect in the 2-gen 3x3x3 puzzle obtained by turning only R's and U's and without repeating any cube state is 73,483,199 turns. Such an algorithm would be the equivalent of either one quarter turn or one half turn on the puzzle. Any other permutation effect on the cube must be of equal or shorter length than this one.

This is done by constructing a Hamiltonian cycle out of all possible 73,483,200 2-gen [R,U] 3x3x3 states. *IF* such a hamiltonian cycle exists, then imagine it is constructed of all 73,483,200 states of the 2-gen puzzle. Call this Hamiltonian cycle the 2-gen Devil's algorithm.

Number the states the 2gen Devil's algorithm passes through as:
\( a_1, a_2, a_3, ... , a_{73,483,200} \)

where each \( a_i \) is a unique cube state achieved in the 2-gen permutation group. All \( a_i \) states taken together form a partition of the 2-generator cube group. Also, define \( a_1 \) to be the solved cube.

Now let's number the turns in the Devil's algorithm itself as:
\( s_1, s_2, s_3, ... , s_{73,483,200} \)

where \( s_n \) denotes the particular turn that takes the cube from state \( a_{n} \) to state \( a_{n+1} \)

Now assume that the particular algorithm you want to achieve is state \( a_{k+1} \)

So our currently numbered Devil's algorithm can be viewed as:
\( s_1, s_2, s_3, ... , s_k, s_{k+1}, ... , s_{73,483,200} \)

Now to construct the algorithm that has the effect of taking the solved state and turning it into state \( a_{k+1} \) construct the following algorithm:

\( s_1, s_2, s_3, ... , s_{k-1}, s_{k} \)

This sequence is k turns in length. To construct another version of this algorithm you can use:

\( s_{73,483,200}', s_{73,483,199}', ... , s_{k+2}', s_{k+1}' \)

where \( s_n' \) denotes the inverse of turn \( s_n \) and is the turn that takes the cube from state \( a_{n+1} \) to state \( a_n \). This constructed sequence is \( 73,483,200 - k \) turns in length.

Finding the longest possible alg to achieve a particular U permutation can be constructed by finding an optimal turn length 2gen 3 cycle for that U perm. Call that state \( a_{k+1} \) and construct the longer version of the permutation using the method above, which will be the permutation you wished to achieve.

This leads me to:

*Hardwick conjecture number 2:*
*A* longest possible algorithm for *any* desired permutation \( P \) is of length:
\( 73,483,200 - O_{P} \) turns.

\( O_{P} \) denotes the length of an optimal algorithm to achieve the permutation \( P \)

This algorithm is constructed by creating a new Devil's Algorithm \( r_n \) such that:
\( r_1, r_2, ... , r_{O_P} \) is the optimal length algorithm that takes the solved state and transforms it into the permutation \( P \). Now construct the following algorithm out of this new Devil's algorithm \( r_n \) *IF* such a new Devil's algorithm exists:

\( r_{73,483,200}', r_{73,483,199}', ... , r_{O_P+2}', r_{O_P+1}' \)

This algorithm will be *a* longest possible algorithm to achieve the permutation \( P_k \) and this assertion is Hardwick conjecture number 2.

Chris


----------



## Ravi (Aug 18, 2010)

A little corollary to the Hardwick conjecture: If there is a Hamiltonian cycle, then its inverse is also a Hamiltonian cycle, and by choosing between these two we can find an algorithm of length at least 73483200/2 = 36741600 moves.

P.S. Anybody recognize the number 36741600?


Spoiler



It's ten times the number of positions of a 2x2 cube. Semi-coincidence.


----------



## cmhardw (Aug 18, 2010)

Ravi said:


> A little corollary to the Hardwick conjecture: If there is a Hamiltonian cycle, then its inverse is also a Hamiltonian cycle, and by choosing between these two we can find an algorithm of length at least 73483200/2 = 36741600 moves.
> 
> P.S. Anybody recognize the number 36741600?
> 
> ...



Ravi, did you see the end of my first conjecture, leading into my second conjecture? I had a number of edits since the time I submitted it. My second conjecture gives a process of how to construct *a* longest possible algorithm for *any* desired permutation, as well as how many moves it contains.

Chris


----------



## Edward (Aug 18, 2010)

From everyone friendly alg thread to place with maths. Horrible maths. @[email protected]


----------



## hawkmp4 (Aug 18, 2010)

Ravi said:


> A little corollary to the Hardwick conjecture: If there is a Hamiltonian cycle, then its inverse is also a Hamiltonian cycle, and by choosing between these two we can find an algorithm of length at least 73483200/2 = 36741600 moves.
> 
> P.S. Anybody recognize the number 36741600?
> 
> ...



Why do you say semi coincidence?
There's not much I can really add to the previous two posts; other than that it all looks good to me. Of course, all of this hinges on the existence of a Hamiltonian cycle...

How would one go about finding the algorithm for the <R,U> Devil's algorithm? Those numbers for states generated by <R,U> are considerably smaller than the numbers for the entire cube group...is the Devil's algorithm for <R,U> (if it exists) something that's within our (i.e., someone with a home computer's) computing power?

EDIT @Edward:
It looks scary, but the concepts here are pretty simple and accessible. If you're interested I can dig up a link that'll give you a decent working knowledge of what they're talking about.


----------



## cmhardw (Aug 18, 2010)

Ok, hopefully the last big edits are done.

My second conjecture is now complete in and of itself, and provides not only my hypothesized maximal length to any desired permutation in the [R,U] group without repeating states, but also how to construct such an algorithm.

If there are any blaring errors please point them out as I will correct them. I would very much love to see the conjecture either proven or disproved, and I am excited to hope that it might be done as there are only 73 million possible states for the 2-gen group, which is far less than the 43 quintillion of the entire cube group.

Chris


----------



## Lucas Garron (Aug 18, 2010)

I can't let you do that, Chris. 

Anyhow, interesting problem, but I need to stop myself.


----------



## cmhardw (Aug 18, 2010)

Lucas Garron said:


> I can't let you do that, Chris.
> 
> Anyhow, interesting problem, but I need to stop myself.



Haha, Lucas thanks I had forgotten about that! 

I guess I have a few unproven conjectures that I need to get started on now 

Chris


----------



## qqwref (Aug 18, 2010)

cmhardw said:


> *Hardwick conjecture:*
> The longest possible algorithm for any effect in the 2-gen 3x3x3 puzzle obtained by turning only R's and U's and without repeating any cube state is 73,483,199 turns. Such an algorithm would be the equivalent of either one quarter turn or one half turn on the puzzle. Any other permutation effect on the cube must be of equal or shorter length than this one.


This is certainly an upper bound. However, I'm not so sure this algorithm can be constructed because we want our sequence to alternate R's and U's (sequences such as U U U R' R' U2 U ... are not OK). The issue is not just of finding a Hamiltonian cycle of the 2-generator group; there is also an added constraint that, in graph theory terms, the edges have one of two colors and we must alternate edge colors in our cycle.



cmhardw said:


> Finding the longest possible alg to achieve a particular U permutation can be constructed by finding an optimal turn length 2gen 3 cycle for that U perm. Call that state \( a_{k+1} \) and construct the longer version of the permutation using the method above, which will be the permutation you wished to achieve.


Sorry, but how do you know that (if one exists at all) there is a Devil's algorithm ending in that particular algorithm? For all we know this may not be possible for all optimal algorithms.



cmhardw said:


> *Hardwick conjecture number 2:*
> *A* longest possible algorithm for *any* desired permutation \( P \) is of length:
> \( 73,483,200 - O_{P} \) turns.


Ah, but what if there is a longer algorithm out there (which still doesn't repeat states)? For instance, maybe there is an algorithm that goes through almost every state, hits the permutation P, and then cannot continue to form a Devil's Algorithm type cycle because the remaining permutations (and the solved state) cannot all be reached in the remaining moves.


----------



## Joker (Aug 19, 2010)

qqwref said:


> Here is a long U perm. I don't know if it repeats states but I don't think it does.
> 
> (R U R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2 R U2)104 R' U2 R2 U' R U' R U' R' U R U' R' U' R U R' U R U2 R' U' R U R' U R U2 R' U
> 
> Length is 5646 moves.



Will this be a good alg for speedcubing?


----------



## Forte (Aug 19, 2010)

Joker said:


> qqwref said:
> 
> 
> > Here is a long U perm. I don't know if it repeats states but I don't think it does.
> ...


yes


----------



## keemy (Aug 19, 2010)

qq: I think that doing U U U would be a valid set of moves for the purpose of this discussion if nothing else it would certainly be more likely a Hamiltonian cycle exists if we allow this.

2nd hah was going to post that too 

3rd yeh Hamiltonian path rather than cycle


----------



## Joker (Aug 19, 2010)

Forte said:


> Joker said:
> 
> 
> > qqwref said:
> ...



KK Ima switch -starts learning alg-


----------



## StachuK1992 (Aug 19, 2010)

<statue> baha. I just made [a bad] J perm, out of an R perm with an M conjugate >_<
<statue> (R' M') U2 (R M) U2 R' F (R U R' U') R' F' R2 U M' U2 M


----------

