login
Rubik's Square sequence.
1

%I #70 Oct 13 2023 06:38:47

%S 1,24,96,165888,663552,165112971264,660451885056,23665185138564661248,

%T 94660740554258644992,488428629217633346355864797184,

%U 1953714516870533385423459188736,1451626239969468099340993140755597642170368,5806504959877872397363972563022390568681472

%N Rubik's Square sequence.

%C The n-th term of this sequence is by definition the order of the group of admissible positions of the n X n Rubik's Square. The group is generated by 2n elements of order 2: 180-degree rotations of n columns, and 180-degree rotations of n rows. It is naturally a subgroup of the symmetric group on n^2 symbols. The sequence was discovered by Carlos Aguirre during a semester project supervised by Sean D. Lawton.

%C Proof of the formula: for any n>0, we split the square of 2n X 2n to four parts. It is easy to show that an element (x, y) has only four places to arrive: ((x, y), (2n-x+1,y), (x,2n-y+1) and (2n-x+1, 2n-y+1)), we call them a, b, c, d. By some rotation we can make any even permutation of abcd, without changing other elements. So we can pair rows i and (2n-i+1), and enumerate which of them are reversed by an odd number; and we can pair columns j and (2n-j-1), enumerate which of them are reversed by an odd number. Then each quad tuple (a, b, c, d) is determined to have an odd permutation, or even permutation; so they have 12 permutations to choose. This gives 12^(n^2) * 2^(2n) permutations, but reversing all columns and rows gives the same permutations, so there are 12^(n^2) * 2^(2n-1) permutations in total. - _Qingyu Ren_, Aug 12 2019

%H Qingyu Ren, <a href="/A225790/b225790.txt">Table of n, a(n) for n = 1..60</a> (first 25 terms from Eric M. Schmidt)

%F For any n>0, a(2*n+1) = 4*a(2*n). - _Eric M. Schmidt_, May 24 2013

%F Conjecture: a(2*n) = 2^A142463(n) * 3^(n^2) = 2^A142463(n) * 3^A000290(n). - _Eric M. Schmidt_, Nov 05 2013

%F For any n>0, a(2*n) = 12^(n^2) * 2^(2n-1) = 2^A142463(n) * 3^(n^2). - _Qingyu Ren_, Aug 12 2019

%e Draw a square n X n array of squares (one face of an n X n X n Rubik's cube). Starting with 1, number the n^2 squares of the array from left to right and from top to bottom. One is allowed to permute this labeling by a finite succession of 180-degree rotations of rows or columns. To compute the terms of the sequence, compute the order of the group of allowed positions. The 1 X 1 case corresponds to the trivial group and so its order is 1: the first term. Here are computations for the next three terms of this sequence using the computer program GAP:

%e gap> G2:=Group((1,2),(3,4),(1,3),(2,4));

%e gap> Order(G2); 24

%e gap> G3:=Group((1,3),(4,6),(7,9),(1,7),(2,8),(3,9));

%e gap> Order(G3); 96

%e gap> G4:=Group((1,4)(2,3), (5,8)(6,7), (9,12)(10,11), (13,16)(14,15), (1,13)(5,9), (2,14)(6,10), (3,15)(7,11), (4,16)(8,12));

%e gap> Order(G4); 165888

%o (GAP)

%o A225790 := n -> Size(grp(n));

%o grp := n -> Group(Concatenation(List([1,n+1..n^2-n+1], s->flip(s, n, 1)), List([1..n], s->flip(s, n, n))));

%o flip := function(start, nterms, skip) return Product([1..Int(nterms/2)], m->(start + skip*(m - 1), start + skip*(nterms - m)), ()); end; # _Eric M. Schmidt_, Nov 05 2013

%o (Haskell)

%o a225790 1 = 1

%o a225790 n = 12 ^ (n1 * n1) * 2 ^ (2 * n1 - 1) * k

%o where

%o n1 = div n 2

%o k = if odd n then 4 else 1 -- _Qingyu Ren_, Aug 12 2019

%o (Python)

%o a1,n = 1,1

%o print(n,a1)

%o while n < 12:

%o n = n+1

%o if n%2 == 0:

%o nn = n//2

%o a = 2**(2*nn*nn+2*nn-1)*3**(nn*nn)

%o a1 = a

%o else:

%o a = 4*a1

%o print(n,a) # _A.H.M. Smeets_, Aug 15 2019

%K nonn

%O 1,2

%A _Sean D Lawton_, May 16 2013

%E More terms from _Eric M. Schmidt_, Nov 05 2013