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

 

Logo

Annual Appeal: Please make a donation (tax deductible in USA) to keep the OEIS running. Over 5000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".

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: A094635 A220054 A263152 * 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 | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 6 15:25 EST 2016. Contains 278781 sequences.