A075464 -id:A075464 - cp's OEIS frontend

A075462 a(n) is the number of solutions to the all-ones lights out problem on an n X n square.

1, 1, 1, 16, 4, 1, 1, 1, 256, 1, 64, 1, 1, 16, 1, 256, 4, 1, 65536, 1, 1, 1, 16384, 16, 1, 1, 1, 1, 1024, 1048576, 1, 1048576, 65536, 16, 64, 1, 1, 1, 4294967296, 1, 4, 1, 1, 16, 1, 1, 1073741824, 1, 256, 256, 1, 1, 4, 16, 1, 1, 1, 1, 4194304, 1, 1099511627776, 16777216

Offset: 1

Eric W. Weisstein, Sep 17 2002

In these counts, nonidentical reflected and rotated solutions are considered distinct.

Caro, Y., Simple proofs to three parity theorems, Ars Combin. 42 (1996), 175-180.
Conlon, M. M.; Falidas, M.; Forde, M. J.; Kennedy, J. W.; McIlwaine, S.; and Stern, J., Inversion numbers of graphs, Graph Theory Notes New York 37 (1999), 42-48.
Cowen, R.; Hechler, S. H.; Kennedy, J. W.; and Ryba, A., Inversion and neighborhood inversion in graphs, Graph Theory Notes New York 37 (1999), 37-41.
Cowen, R. and Kennedy, J., The Lights Out puzzle, Math. Educ. Res. 9 (2000), 28-32.
Goldwasser, J. and Klostermeyer, W., Maximization versions of 'Lights Out' games in grids and graphs, Congr. Numer. 126 (1997), 99-111.
K. Sutner, Linear cellular automata and the Garden-of-Eden, Math. Intelligencer 11 (1989), 49-53.

Max Alekseyev and Thomas Buchholz, Table of n, a(n) for n = 1..1000 [terms were extended by Max Alekseyev, Sep 17 2009; terms 63 through 1000 were computed by Thomas Buchholz, May 16 2014]
Millstone Website, Lights Out
Eric Weisstein's World of Mathematics, Lights Out Puzzle
Whitman College Department of Mathematics, Lights Out

Cf. A075463, A075464, A076436, A076437.

m[k_] := SparseArray[ {Band[{1, 1}] -> 1, Band[{1, 2}] -> 1, Band[{2, 1}] -> 1}, {k, k}]; b[k_, 0] := SparseArray[ Band[{1, 1}] -> 1, {k, k}]; b[k_, 1] := m[k]; b[k_, n_] := b[k, n] = Mod[m[k].b[k, n-1] + b[k, n-2], 2]; A159257[n_] := First[ Dimensions[ NullSpace[b[n, n], Modulus -> 2]]]; A159257[1] = 0; a[n_] := 2^A159257[n]; Table[a[n], {n, 1, 62}] (* Jean-François Alcover, Oct 10 2012, after Max Alekseyev and Birkas Gyorgy *)

a(n) = 2^A159257(n). - Max Alekseyev, Sep 17 2009

More terms from Max Alekseyev, Sep 17 2009, and Thomas Buchholz, May 16 2014

A159257 Rank deficiency of the Lights Out problem of size n.

Original entry on oeis.org

0, 0, 0, 4, 2, 0, 0, 0, 8, 0, 6, 0, 0, 4, 0, 8, 2, 0, 16, 0, 0, 0, 14, 4, 0, 0, 0, 0, 10, 20, 0, 20, 16, 4, 6, 0, 0, 0, 32, 0, 2, 0, 0, 4, 0, 0, 30, 0, 8, 8, 0, 0, 2, 4, 0, 0, 0, 0, 22, 0, 40, 24, 0, 28, 42, 0, 32, 0, 8, 0, 14, 0, 0, 4, 0, 0, 2, 0, 64, 0, 0, 0, 6, 12, 0, 0, 0, 0, 10, 0, 0, 20, 0, 4, 62, 0, 0, 20, 16, 0, 18, 0, 0, 4, 0, 0, 6, 0, 8, 0, 0, 0, 2, 4, 0, 0, 0, 8, 46, 0, 0, 0, 80, 4, 50, 56, 0, 56, 56, 0

Offset: 1

Bruno Vallet (bruno.vallet(AT)gmail.com), Apr 07 2009

nonn

A square array of n X n pixels can have two states (gray, red). Touching a pixel switches its state and the state of the adjacent pixels. The general problem is to turn all pixels ON given any initial configuration. It requires inverting a n^2 by n^2 matrix in Z/2Z. The sequence is the rank deficiency (corank) of the matrix, such that the zero terms correspond to the sizes for which the general case admits a solution.
The size 5 game can be played at the link given below. Rank deficiency is 2 for that game, but only initial configurations that admit a solution are given.
a(n) is nonzero iff n is in A117870; a(n) is zero iff n is in A076436. - Max Alekseyev, Sep 17 2009
a(n) is even and satisfies a(n) <= n. - Thomas Buchholz, May 19 2014
For all indices n and natural numbers k, a(n*k - 1) >= a(n - 1). - William Boyles, Jun 17 2022

			For n=2, matrix is [1 1 1 0][1 1 0 1][1 0 1 1][0 1 1 1] which is of full rank.

See A075462 for references.

William Boyles, Table of n, a(n) for n = 1..25000 (first 1000 terms by Max Alekseyev and Thomas Buchholz).
Andries E. Brouwer, Lights Out and Button Madness Games [Gives theory and a(n) for n = 1..1000, Jun 19 2008]
JeuxT45, Turn it red [Dead link]
Martin Kreh, "Lights Out" and Variants, The American Mathematical Monthly 124:10 (2017), 937-950.
Eric Weisstein's World of Mathematics, Lights Out Puzzle

Cf. A075462, A075463, A075464, A076436, A076437.

Table[First[Dimensions[NullSpace[AdjacencyMatrix[GridGraph[{n, n}]] + IdentityMatrix[n*n],Modulus -> 2]]], {n, 2, 30}]
(* Or Faster *)
A[k_] := DiagonalMatrix[Array[1 &, k - 1], -1] +
  DiagonalMatrix[Array[1 &, k - 1], 1] + IdentityMatrix[k];
B[k_, 0] := IdentityMatrix[k];
B[k_, 1] := A[k];
B[k_, n_] := B[k, n] = Mod[A[k].B[k, n - 1] + B[k, n - 2], 2];
Table[First[Dimensions[NullSpace[B[n, n], Modulus -> 2]]], {n, 2, 30}]
(* Birkas Gyorgy, Jun 10 2011 *)

{ A159257(n) = my(p,q,r); p=Mod(1,2); q=p*x;for(u=2,n,r=x*q+p;p=q;q=r); p=subst(q,x,1+x); r=gcd(p,q); poldegree(r) } \\ Zhao Hui Du, Mar 18 2014

{ A159257(n) = my(f = polchebyshev(n,2,x/2)*Mod(1,2)); poldegree( gcd(f,subst(f,x,1+x)) ); } \\ Max Alekseyev, Nov 12 2019

Let f(k,x) = U(k,x/2), where U(k,x) is the k-th Chebyshev polynomial of the second kind over the field GF(2). So f(0,x)=1, f(1,x)=x, f(2,x)=(1+x)^2, and f(n+1,x)=x*f(n,x)+f(n-1,x). Then a(n) equals the degree of gcd(f(n,x), f(n,1+x)). For example, f(5,x)=x^5+x=x(1+x)^4 and f(5, 1+x)=x^4(1+x). So their GCD is x(1+x) and the degree is 2, that is a(5)=2. - Zhao Hui Du, Mar 17 2014; edited by Max Alekseyev, Nov 12 2019

More terms from Max Alekseyev, Sep 17 2009

More terms from Thomas Buchholz, May 16 2014

A075463 a(n) is the number of rotation-reflection inequivalent solutions to the all-ones lights out problem on an n X n square.

Original entry on oeis.org

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

Offset: 1

Eric W. Weisstein, Sep 17 2002

Reflected and rotated solutions are considered identical.

See A075462 for references.

Zhao Hui Du, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Lights Out Puzzle

Cf. A075462, A075464.

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 *)

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
} \\ Zhao Hui Du, Mar 29 2014

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

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

A137619 a(n) is the maximal (nonredundant) number of switch flippings in a solution of the all-ones lights out problem on an n X n square.

Original entry on oeis.org

1, 4, 5, 12, 15, 28, 33, 40, 55, 44, 71, 72, 105, 96, 117, 152, 147, 188, 225, 224, 245, 276, 299, 306, 353, 356, 405, 416, 451

Offset: 1

Jacob A. Siehler, Apr 27 2008

See A075462 for references.

Cf. A075464.

A353071 Maximum number of clicks needed to solve any solvable Lights Out problem on an n X n grid.

Original entry on oeis.org

1, 4, 9, 7, 15, 36, 49, 64, 37, 100, 65, 144, 169, 123, 225, 124, 199, 324, 197, 400, 441, 484

Offset: 1

William Boyles, Apr 21 2022

a(n) = n^2 if and only if A159257(n) = 0.
a(n) >= A075464(n).
If n = 6k-1 for some integer k, then a(n) <= 26k^2 - 12k + 1. This upper bound is equal to a(n) when A159257(n) = 2. Further, it is conjectured that if A159257(n) = 2, then n = 6k-1 for some integer k.
It is conjectured that if A159257(n) = 4, then n = 5k-1 for some integer k, and a(n) = 17k^2 - 10k.
It is conjectured that if A159257(n) = 6, then n = 12k-1 for some integer k, and a(n) = 88k^2 - 24k + 1
It is conjectured that if A159257(n) = 8, then either n = 10k-1 or n = 17k-1 for some integer k. If n = 10k-1, then a(n) = 60k^2 - 20k - 3. If n = 17k-1, then a(n) = 161k^2 - 34k - 3.
It is conjectured that if A159257(n) = 10, then n = 30k-1 for some integer k, and a(n) = 506k^2 - 60k - 3.
239 <= a(23) <= 305.

William Boyles, Most Clicks Problem in Lights Out, arXiv:2201.03452 [math.CO], 2022.

Cf. A159257, A075464.

cp's OEIS Frontend

A075462 a(n) is the number of solutions to the all-ones lights out problem on an n X n square.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A159257 Rank deficiency of the Lights Out problem of size n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A075463 a(n) is the number of rotation-reflection inequivalent solutions to the all-ones lights out problem on an n X n square.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A137619 a(n) is the maximal (nonredundant) number of switch flippings in a solution of the all-ones lights out problem on an n X n square.

Views

Author

Keywords

References

Crossrefs

A353071 Maximum number of clicks needed to solve any solvable Lights Out problem on an n X n grid.

Views

Author

Keywords

Comments

Links

Crossrefs