OFFSET
1,4
COMMENTS
Reflected and rotated solutions are considered identical.
REFERENCES
See A075462 for references.
LINKS
Zhao Hui Du, 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);
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);
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)));
} \\ Zhao Hui Du, Mar 29 2014
CROSSREFS
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 Zhao Hui Du, Mar 24 2014
STATUS
approved