login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A335136 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. 0
1, 2, 1, 5, 6, 1, 7, 30, 71, 119, 160, 184, 192, 1, 9, 53, 221, 592, 1072, 1296, 1, 11, 80, 488, 2550, 10511, 35601, 99142, 218400, 382480, 538912, 630080, 658944, 663552 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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].

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)?

LINKS

Table of n, a(n) for n=1..34.

E. D. Demaine, M. L. Demaine, S. Eisenstat, A. Lubiw, and A. Winslow, Algorithms for Solving Rubik’s Cubes, arXiv:1106.5736 [cs.DS], 2011.

E. D. Demaine, S. Eisenstat, and M. Rudoy, Solving the Rubik's Cube Optimally is NP-complete, arXiv:1706.06708 [cs.CC], 2017-2018.

EXAMPLE

The irregular triangle T(n,k) starts:

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

   1: 1  2

   2: 1  5  6

   3: 1  7 30  71  119   160   184   192

   4: 1  9 53 221  592  1072  1296

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

PROG

(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)]~])));

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)))));

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}

CROSSREFS

Sequence in context: A269019 A184234 A193816 * A193722 A193635 A241168

Adjacent sequences:  A335133 A335134 A335135 * A335137 A335138 A335139

KEYWORD

nonn,tabf,more

AUTHOR

Davis Smith, Jun 02 2020

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 18 19:19 EDT 2020. Contains 337172 sequences. (Running on oeis4.)