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

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

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 July 28 04:02 EDT 2014. Contains 244987 sequences.