Lower bound for Megaminx in htm and qtm

Discussion in 'Puzzle Theory' started by Herbert Kociemba, Mar 1, 2012.

Welcome to the Speedsolving.com. You are currently viewing our boards as a guest which gives you limited access to join discussions and access our other features. By joining our free community of over 30,000 people, you will have access to post topics, communicate privately with other members (PM), respond to polls, upload content and access many other special features. Registration is fast, simple and absolutely free so please, join our community today!

If you have any problems with the registration process or your account login, please contact us and we'll help you get started. We look forward to seeing you on the forums!

Already a member? Login to stop seeing this message.
  1. Herbert Kociemba

    Herbert Kociemba Member

    Nov 29, 2008
    I analyzed the number of generic move sequences to get lower bounds for God's number of Megaminx, taking into account the commutativity of moves. There are a lot of commutating moves because of the many disjoint faces of Megaminx. In htm, I found a lower bound of 45 moves and in qtm a lower bound of 55 moves.

    I posted the details here:

    Brest likes this.
  2. qqwref

    qqwref Member

    Dec 18, 2007
    a <script> tag near you
    I made a somewhat similar recursion a while back and ended up with, I think, 43 moves for the Megaminx. I'm not sure exactly where our techniques differ, but I do like this technique in general, as you can get some pretty nice results without a huge amount of work.
  3. Herbert Kociemba

    Herbert Kociemba Member

    Nov 29, 2008
    I assume, the techniques differ somehow, because the difference between 43 und 45 means that you have more than 1000 times the number of move sequences with 45 moves.
    I would be really pleased, if
    1. Someone could double check, that there are 25 unordered pairs of faces (X,Y), which have no pieces in common and either X or Y (or both) have pieces in common with some arbitrary different fixed face,e.g. U.
    2. The same for 15 unordered triples (X,Y,Z), which have no pieces in common and either X or Y or Z have pieces in common with another different face, for example the U face.
    3. Compute the true number of positions of Megaminx out to some depth in htm and qtm to check if the numbers are the same for the first ??? depths. This depends on the length of the shortest nontrivial identity. Btw, What is the shortest nontrivial identity on Megaminx?
    Last edited: Mar 1, 2012
  4. Lucas Garron

    Lucas Garron Super-Duper Moderator Staff Member

    At most 10 moves. FRU'R'U2F'L'ULU2' works on Megaminx.
  5. TMOY

    TMOY Member

    Jun 29, 2008
    The niklas done the wrong way (L' U R U' L U R' U') is a 8-move identity.
  6. Herbert Kociemba

    Herbert Kociemba Member

    Nov 29, 2008
    In a private communication Tomas Rokicki pointed out recently that my argumentation concerning the commutating moves is too weak. Indeed not all commutative moves are taken into account in my argumentation and the lower bound 45 can be improved to 48 moves.
    shows an algorithm which gives the correct numbers.

    Using the key idea given here - keeping track of the "recently used moves" - I found a pencil and paper method to compute the number of canonical sequences for each depth. If there is more than one recently used move these moves have to commute pairwise.
    There are only 5 different types of "recently used moves":
    0. No recently used move (this happens only at depth 0)
    1. One recently used move
    2. Two recently used moves. There are 2 types for this case. The two moves are opposite to each other or they are not opposite and do not share any cubies (else they would not commute).
    3. Three recently used moves. Essentially there is only one case for three axes such that the moves commute pairwise.

    Let us name the number of maneuvers of depth n which end with 0, 1, 2 or three recently used moves with a0(n), a1(n), a2a(n), a2b(n) and a3(n).
    For depth 0 we have
    a0(0) = 1, a1(0) = 0, a2a(0) = 0, a2b(0) = 0, a3(0) = 0

    Analysing what happens when you append one move you find for n>=0:

    a0(n+1) = 0
    a1(n+1) = 4*(12*a0(n) + 5*a1(n) + 2*a2a(n))
    a2a(n+1) = 4*(5*a1(n) + 4*a2a(n) + 10*a2b(n) + 3*a3(n))/2
    a2b(n+1) = 4*(1*a1(n) + 2*a2a(n) + 3*a3(n))/2
    a3(n+1) = 4*(2*a2a(n) + 3*a3(n))/3

    The factor 4 takes into account that there are 4 possible moves for each axis, dividing by 2 or 3 takes into account that for commutative moves we only count a fraction of the possibilites.

    The total number total (n) of canonical sequences of depth n then is given by

    total(n) = a0(n)+a1(n)+a2a(n)+a2b(n)+a3(n) which gives

    1, 48, 1536, 43520, 1182720, 31641600, 841318400, 22315008000, 591298560000, 15661924352000,....

    Tom also gave me the number of true positions for each depth which is

    1, 48, 1536, 43520, 1180800, 31471080,.....
    which shows that all canonical sequences up to depth 3 give different positions.

    I also found a simple linear recurrence for the number of canonical sequences for the megaminx which I think is really surprising

    total(n+1) = 36 total(n) -240 total(n-1) -320 total(n-2), n>=3 and total(1)= 48, total(2) = 1536 and total(3) =43520.

    This easily gives the lower bound of 48 moves. That this is the same number as the number of depth 1 maneuvers is coincidence. The same coicidence happens btw. for Rubik's cube, where the number of depth 1 maneuvers and the lower bound are both 18...

    The asymtotic branching factor is the greatest zero of the corresponding characteristic polynomial x^3-(36 x^2-240x-320) which is about 26.4803 .

    The above holds for HTM. I do not see how to give an easy similar argumentation for QTM.
    Last edited: Aug 19, 2016
    DGCubes and Brest like this.

Share This Page