The longest alg?

[cmhardw]

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.

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]

From everyone friendly alg thread to place with maths. Horrible maths. @_@

 

[hawkmp4]

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.

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]

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]

I can't let you do that, Chris.

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

 

[cmhardw]

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]

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.

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.

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]

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]

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?

yes

 

[keemy]

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]

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?

yes

KK Ima switch -starts learning alg-

 

[StachuK1992]

<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