Le dragon du Rubik's Cube

[Morphocode]

Soit W un sous groupe de M = <H,B,A,P,G,D > à deux générateurs a,b: W = <a,b>
Soit T une formule par ex T = a²bab²a,
on pose T# = ba²bab² , On lit T à l'envers et on remplace a<->b.

On définit alors une suite de formules ainsi :
à chaqu' étape on passe de T à (Ta)#

F1 = a
F2 = bb = b2
F3 = baa = ba2
F4 = bbba = b3a
F5 = bbaaa = b2a3
..... etc ....

Comme il y a un nombre fini d'états on tombe forcement sur un état déjà donné par une formule Fk. Par ex on est à l' étape n ,la première fois qu'on tombe sur la formule F1 = a , l'état e•Fn-1 se nomme le dragon de W,
par ex si à l'étape 17 on tombe (pour la 1er fois) sur F1 = a ,
alors le dragon de W est :
dragon = e•F16

Frank BARNES a démontré que :
M = < Q,K > où Q = HPGHG'H'P' et K = D²AGB'D' (Frank BARNES)

Question: Trouver le dragon de M=<Q,K> ==> (on peut faire un programme informatique pour le trouver)

On dit aussi c'est le dragon du Rubik's Cube.

[Morphocode]

Voici un script en GAP qui permet de trouver le Dragon du Rubik's Cube
Dragon du Rubik's Cube = (D²AGB'D' )75 (HPGHG'H'P' )²




Le script permet aussi de calculer le Dragon du BigBlock

Code : Tout sélectionner

#Soit W un sous groupe de M = <H,B,A,P,G,D > à deux générateurs a,b: W = <a,b>
#On définit alors une suite de formules ainsi :
#F1 = a
#F2 = bb = b2
#F3 = baa = ba2
#F4 = bbba = b3a
#F5 = bbaaa = b2a3
#..... etc ....
#Si Fn=F1=a alors par def le dragon de W est F(n-1)
#
#
# gap_dragon.txt
#         5  6  7
#         4  H  8
#         3  2  1
#25 28 23|21 26 19|17 32 31|29 30 27
#38 G  36|12 A  10|34 D  40|16 P  14
#43 44 37|39 42 33|35 48 45|47 46 41
#         11 18 9
#         20 B  24
#         13 22 15
#H=49,B=50,A=51,P=52,G=53,D=54
#
pH := (2,4,6,8)(26,28,30,32) (1,3,5,7)(17,21,25,29)(19,23,27,31);;#pH
pB := (18,24,22,20)(42,48,46,44) (9,15,13,11)(33,45,41,37)(35,47,43,39);;
pA := (2,34,18,36)(26,10,42,12) (1,35,11,23)(17,9,37,3)(19,33,39,21);;
pP := (6,38,22,40)(30,14,46,16) (7,25,13,45)(29,27,41,47)(31,5,43 ,15);;
pG := (4,12,20,14)(28,36,44,38) (3,39,13,27)(21,11,41,5)(23,37,43,25);;
pD := (8,16,24,10)(32,40,48,34) (1,29,15,33)(17,31,45,35)(19,7,47,9);;#pD
pGamma := (2,26);;
pPsi := (1,17,19);;
pOmega := (2,8)(26,32);;
ph := (10,36,14,40)(34,12,38,16)(51,53,52,54);;
pd := (2,30,22,42)(26,6,46,18)(49,52,50,51);;
pa :=  (4,32,24,44)(28,8,48,20)(49,54,50,53);;

###M = < Q,K > où Q = HPGHG'H'P' et K = D²AGB'D' (Frank BARNES)
dragon := "Rubik" ;;  #dragon=D229H230=D75H2
H := pH*pP*pG*pH*pG^-1*pH^-1*pP^-1 ;;
D := pD*pD*pA*pG*pB^-1*pD^-1 ;;

#dragon := "BigBlock" ;; #dragon=D5H3=DH'
#H := (2,4,6,8)(26,28,30,32) (1,3,5,7)(17,21,25,29)(19,23,27,31);;#pH
#D := (8,16,24,10)(32,40,48,34) (1,29,15,33)(17,31,45,35)(19,7,47,9);;#pD

#dragon := "Fused" ;; #dragon=D5AH3=DAH'
#H := (2,4,6,8)(26,28,30,32) (1,3,5,7)(17,21,25,29)(19,23,27,31);;#pH
#D := (8,16,24,10)(32,40,48,34) (1,29,15,33)(17,31,45,35)(19,7,47,9);;#pD
#A := (2,34,18,36)(26,10,42,12) (1,35,11,23)(17,9,37,3)(19,33,39,21);;#pA

### pour les tests
#dragon := "S4" ;; #dragon=D5H3=DH'
#H := (1,2);;
#D := (1,2,3,4);;
#dragon := "S5" ;; #dragon=D5H3=DH'
#H := (1,2);;
#D := (1,2,3,4,5);;
#dragon := "S6" ;; #dragon=D5H3=DH'
#H := (1,2);;
#D := (1,2,3,4,5,6);;
#dragon := "S7" ;; #dragon=D5H3=DH'
#H := (1,2);;
#D := (1,2,3,4,5,6,7);;
#dragon := "S8" ;; #dragon=D5H3=DH'
#H := (1,2);;
#D := (1,2,3,4,5,6,7,8);;
#dragon := "S12" ;; #dragon=D5H3=DH'
#H := (1,2);;
#D := (1,2,3,4,5,6,7,8,9,10,11,12);;
#dragon := "Mathieu12" ;;#dragon=D9H10=D9
#H := (1,12)(2,11)(3,10)(4,9)(5,8)(6,7);;
#D := (2,3,5,9,8,10,6,11,4,7,12);;

Tdiese := function(p,q,dragon)
   local m, Q ;
   m:=q+1;
   
   if (dragon="Fused") then
      Q := D^m *A* H^p ;
   else
      Q := D^m * H^p ;
   fi;
   
   return Q;
end;;

permu:=[];;
formule:=[];;
n:=500;;#recherche limitée à 500 premiers termes
for k in [1..n] do
    permu[k]:= 0 ;
   formule[k]:= "" ;
od;

if (dragon="Fused") then
   permu[1]:= A*H;;
   formule[1]:= "A*H" ;;
else
   permu[1]:= H;;
   formule[1]:= "H" ;;   
fi;

v := 2;;
p:=0;;
q:=1;;
etape := 1;;
g := 2;;
while (g <= n) do
   
   qq:=String(q+1); #q=4 ==> convertir en chaine "5"
   pp:=String(p);#p=7 ==> convertir en chaine "7"
   T:=Concatenation( "D^", qq );
   
   if (dragon="Fused") then
      T1:=Concatenation( "*A*H^", pp );
   else
      T1:=Concatenation( "*H^", pp );
   fi;

   T:=Concatenation( T, T1 );

   pT := Tdiese(p,q,dragon); # entrée p,q sortie permutation

   deja := false ;
   for k in [1..n] do
       if (pT = permu[k]) then
         deja := true ;
         etape := g ; #save g
         g := n;   #pour sortir de la boucle while
      fi;
   od;
   
   if (not deja) then   
   
      formule[v] := T ; #mettre T dans la tab
      permu[v] := pT ;#mettre pT dans la tab
      v := v+1;
      xx:=p; #recomencer avec les nouvelle val p,q
      p:=q+1;
      q:=xx;
      
   fi;
   g := g+1;
            
od;

#afficher le resultat, on saute qd c'est trop long
#for k in [1..n] do
#   if (permu[k] <> 0 ) then 
#      Print( "\n ",k,") ", formule[k]," => ",permu[k],"\n");   
#   fi;      
#od;

#dragon=dernier de la tab
Print( "\n\n dragon-",dragon," = ", formule[v-1]," => ",permu[v-1],"\n");   
Print( "\n n=", etape,"\n");
Print( "\n OrdreD=", Order(D),"\n");
Print( "\n OrdreH=", Order(H),"\n");
Print( "\n p=", p,"\n");
Print( "\n q=", q,"\n");
Print( "\n D^", p mod Order(D),"\n");
Print( "\n H^", q mod Order(H),"\n");