

A225790


Rubik's Square sequence.


1



1, 24, 96, 165888, 663552, 165112971264, 660451885056, 23665185138564661248, 94660740554258644992, 488428629217633346355864797184, 1953714516870533385423459188736, 1451626239969468099340993140755597642170368, 5806504959877872397363972563022390568681472
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

The nth 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: 180degree rotations of n columns, and 180degree 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.
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), (2nx+1,y), (x,2ny+1) and (2nx+1, 2ny+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 (2ni+1), and enumerate which of them are reversed by an odd number; and we can pair columns j and (2nj1), 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^(2n1) permutations in total.  Qingyu Ren, Aug 12 2019


LINKS

Qingyu Ren, Table of n, a(n) for n = 1..60 (first 25 terms from Eric M. Schmidt)


FORMULA

For any n>0, a(2*n+1) = 4*a(2*n).  Eric M. Schmidt, May 24 2013
Conjecture: a(2*n) = 2^A142463(n) * 3^(n^2) = 2^A142463(n) * 3^A000290(n).  Eric M. Schmidt, Nov 05 2013
For any n>0, a(2*n) = 12^(n^2) * 2^(2n1) = 2^A142463(n) * 3^(n^2).  Qingyu Ren, Aug 12 2019


EXAMPLE

Draw an 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 180degree 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:
gap> G2:=Group((1,2),(3,4),(1,3),(2,4));
gap> Order(G2); 24
gap> G3:=Group((1,3),(4,6),(7,9),(1,7),(2,8),(3,9));
gap> Order(G3); 96
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));
gap> Order(G4); 165888


PROG

(GAP)
A225790 := n > Size(grp(n));
grp := n > Group(Concatenation(List([1, n+1..n^2n+1], s>flip(s, n, 1)), List([1..n], s>flip(s, n, n))));
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
(Haskell)
a225790 1 = 1
a225790 n = 12 ^ (n1 * n1) * 2 ^ (2 * n1  1) * k
where
n1 = div n 2
k = if odd n then 4 else 1  Qingyu Ren, Aug 12 2019
(Python)
a1, n = 1, 1
print(n, a1)
while n < 12:
n = n+1
if n%2 == 0:
nn = n//2
a = 2**(2*nn*nn+2*nn1)*3**(nn*nn)
a1 = a
else:
a = 4*a1
print(n, a) # A.H.M. Smeets, Aug 15 2019


CROSSREFS

Sequence in context: A272871 A319577 A277563 * A042122 A042124 A042126
Adjacent sequences: A225787 A225788 A225789 * A225791 A225792 A225793


KEYWORD

nonn


AUTHOR

Sean D Lawton, May 16 2013


EXTENSIONS

More terms from Eric M. Schmidt, Nov 05 2013


STATUS

approved



