login
This site is supported by donations to The OEIS Foundation.

 

Logo

The submissions stack has been unacceptably high for several months now. Please voluntarily restrict your submissions and please help with the editing. (We don't want to have to impose further limits.)

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A075463 a(n) is the number of rotation-reflection inequivalent solutions to the all-ones lights out problem on an n X n square. 5
1, 1, 1, 5, 1, 1, 1, 1, 43, 1, 10, 1, 1, 5, 1, 43, 1, 1, 8356, 1, 1, 1, 2080, 5, 1, 1, 1, 1, 136, 131720, 1, 131720, 8356, 5, 10, 1, 1, 1, 536911936, 1, 1, 1, 1, 5, 1, 1, 134225920, 1, 43, 43, 1, 1, 1, 5, 1, 1, 1, 1, 524800, 1, 137439609088, 2099728, 1, 33564704, 549756338176, 1, 536911936, 1, 43, 1, 2080, 1, 1, 5, 1, 1, 1, 1, 2305843011898064896 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,4

COMMENTS

Reflected and rotated solutions are considered identical.

REFERENCES

See A075462 for references.

LINKS

Du, Zhao Hui, Table of n, a(n) for n = 1..1000

Eric Weisstein's World of Mathematics, Lights Out Puzzle

MATHEMATICA

a[n_, i_, j_ ] := Table[If[Total[Abs[{i, j} - {r, s}]] <= 1, 1, 0], {r, n}, {s, n}] //Flatten

a[n_, k_ ] := a[n, Quotient[k + n - 1, n], Mod[k, n, 1]]

m[n_ ] := a[n, # ] & /@ Range[n^2]

ker[n_ ] := NullSpace[m[n], Modulus -> 2]

b[n_ ] := Table[1, {n^2}]

sol[n_ ] := LinearSolve[m[n], b[n], Modulus -> 2];

allSolutions[n_ ] := Module[{s, k},

s = sol[n];

k = ker[n];

Mod[(s + # ) & /@ (Total[(#*k)] & /@ Tuples[{0, 1}, Length[k]]), 2]

] //Sort

MatrixRotate[m_ ] := Transpose[Reverse[m]]

MatrixRotate[m_, n_ ] := Nest[MatrixRotate, m, Mod[n, 4]]

DihedralOrbit[m_ ] := Union@Join[

MatrixRotate[m, # ] & /@ Range[0, 3],

MatrixRotate[Reverse[m], # ] & /@ Range[0, 3]

]

essentialSolutions[n_ ] := Module[{as},

as = Partition[ #, n] & /@ allSolutions[n];

Union[as, SameTest -> (MemberQ[DihedralOrbit[ #1], #2] &)]

]

Length[essentialSolutions[ # ]] & /@ Range[16]

(* Jacob A. Siehler *)

PROG

(Pari)H(n)={

   my(r);

   r=matrix(n, n, X, Y, Mod(0, 2));

   for(u=1, n, r[u, u]=Mod(1, 2));

   for(u=1, n-1, r[u, u+1]=Mod(1, 2); r[u+1, u]=Mod(1, 2));

   r

}

E(n)={

   my(r);

   r=matrix(n, n, X, Y, Mod(0, 2));

   for(u=1, n, r[u, u]=Mod(1, 2));

   r

}

b(n)={

   vector(n, X, Mod(1, 2))~

}

a(n)={

   my(x0, x1, tmp, y, z, mH, vb, v0, v1, yb, zb);

   my(A159257, A075462, A075463, a2, a3, a4, a5, tm, tb);

   x0=E(n); mH=H(n); x1=mH; vb=b(n);

   y=matrix(n, n); yb=vector(n);

   z=matrix(n, n); zb=vector(n);

   v0=vb; v1=mH*vb+v0;

   y[1, ]=x0[1, ]; yb[1]=Mod(0, 2);

   y[2, ]=x1[1, ]; yb[2]=v0[1];

   z[1, ]=x0[n, ]; zb[1]=Mod(0, 2);

   z[2, ]=x1[n, ]; zb[2]=v0[n];

   for(u=2, n-1,

      tmp=mH*x1+x0; x0=x1; x1=tmp;

      y[u+1, ]=x1[1, ]; z[u+1, ]=x1[n, ];

      tmp=mH*v1+v0+vb; v0=v1; v1=tmp;

      yb[u+1]=v0[1]; zb[u+1]=v0[n]

   );

   x1=mH*x1+x0;

   A159257 = n-matrank(x1);

   A075462=2^A159257;

   tm=matrix(2*n, n, X, Y, Mod(0, 2)); tb=vector(2*n, X, Mod(0, 2))~;

   for(u=1, n, tm[u, ]=x1[u, ]; tb[u]=v1[u]);

   for(u=1, n,

       tm[n+u, u]=Mod(1, 2); tm[n+u, n-u+1]+=Mod(1, 2); tb[n+u]=Mod(0, 2)

   );

   a2=matinverseimage(tm, tb);

   if(length(a2)==0, a2=0, a2=2^(n-matrank(tm)));

   for(u=1, n, tm[n+u, ]=y[u, ]; tb[n+u]=yb[u]; tm[n+u, u]+=Mod(1, 2));

   a3=matinverseimage(tm, tb);

   if(length(a3)==0, a3=0, a3=2^(n-matrank(tm)));

   for(u=1, n, tm[n+u, ]=y[n+1-u, ]; tb[n+u]=yb[n+1-u]; tm[n+u, u]+=Mod(1, 2));

   a4=matinverseimage(tm, tb);

   if(length(a4)==0, a4=0, a4=2^(n-matrank(tm)));

   for(u=1, n, tm[n+u, ]=y[u, ]+z[n+1-u, ]; tb[n+u]=yb[u]+zb[n+1-u]);

   a5=matinverseimage(tm, tb);

   if(length(a5)==0, a5=0, a5=2^(n-matrank(tm)));

   A075463=(A075462+2*(a2+a3+a4)+a5)/8

} \\ Du, Zhao Hui, Mar 29 2014

CROSSREFS

Cf. A075462, A075464.

Sequence in context: A074062 A094635 A220054 * A026518 A051008 A109768

Adjacent sequences:  A075460 A075461 A075462 * A075464 A075465 A075466

KEYWORD

nonn,nice,hard

AUTHOR

Eric W. Weisstein, Sep 17 2002

EXTENSIONS

a(19)-a(29) from Jacob A. Siehler, Apr 29 2008

Terms a(30) and beyond from Du, Zhao Hui, Mar 24 2014

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified August 29 10:37 EDT 2015. Contains 261188 sequences.