A335136 - OEIS

%I #32 Jul 13 2020 02:49:29

%S 1,2,1,5,6,1,7,30,71,119,160,184,192,1,9,53,221,592,1072,1296,1,11,80,

%T 488,2550,10511,35601,99142,218400,382480,538912,630080,658944,663552

%N Irregular triangle read by rows: T(n,k) is the number of permutations of an n X n Rubik's Square reachable in k or fewer moves, terminating at the maximum value.

%C For this sequence, a Rubik's Square is 2 dimensional and only has 2 colors. This sequence uses quarter-turn notation; a move is a reversion of either a row or column. So, if one color is '1' and the other is '0', performing a move on [0,1,1,0,0] would make that row/column [1,1,0,0,1].

%C There are two questions associated with this triangle. First, how many permutations are reachable for an n X n Rubik's Square (what is the maximum value in the n-th row)? Second, what is the number of moves necessary to solve an n X n Rubik's Square (when does the n-th row terminate)?

%H E. D. Demaine, M. L. Demaine, S. Eisenstat, A. Lubiw, and A. Winslow, <a href="https://arxiv.org/abs/1106.5736">Algorithms for Solving Rubik’s Cubes</a>, arXiv:1106.5736 [cs.DS], 2011.

%H E. D. Demaine, S. Eisenstat, and M. Rudoy, <a href="https://arxiv.org/abs/1706.06708">Solving the Rubik's Cube Optimally is NP-complete</a>, arXiv:1706.06708 [cs.CC], 2017-2018.

%e The irregular triangle T(n,k) starts:

%e   n\k 0  1  2   3    4     5     6     7      8      9     10     11 ...

%e    1: 1  2

%e    2: 1  5  6

%e    3: 1  7 30  71  119   160   184   192

%e    4: 1  9 53 221  592  1072  1296

%e    5: 1 11 80 488 2550 10511 35601 99142 218400 382480 538912 630080 ...

%o (PARI) A335136_row(n)={my(total=List([0]), completed=List(), moves=[1..2*n], moves2=select(X->X,[-n..n]), M=List([]), moves2bits=Map(Mat([moves~,apply(y-> my(Q=Map(Mat([(S=select(X->floor(X/(n^(y<0)))%n==(abs(y)-1), [0..n^2-1]))[1..ceil(#S/2)]~,Vecrev(S)[1..ceil(#S/2)]~])));

%o apply(X->shift(shift(1, mapget(Q,X)-X)+(X!=mapget(Q,X)),X), Mat(Q)[,1]) ,moves2)~])), mover(Y,Z)=bitxor(Z,vecsum(select(W->my(B=bitand(Z,W));(!B||B==W),mapget(moves2bits,Y)))));

%o while(#completed<#total,listput(M,#total);my(new=setminus(Vec(total), Vec(completed)));completed=total;forvec(A=[[1,2*n],[1,#new]], my(F=mover(A[1],new[A[2]]), S=setsearch(total,F,1));if(S,listinsert(total,F,S))));M}

%K nonn,tabf,more

%O 1,2

%A _Davis Smith_, Jun 02 2020