A159257 -id:A159257 - 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

A076436 Square board sizes for which the lights-out problem has a unique solution (counting solutions differing only by rotation and reflection as distinct).

Original entry on oeis.org

1, 2, 3, 6, 7, 8, 10, 12, 13, 15, 18, 20, 21, 22, 25, 26, 27, 28, 31, 36, 37, 38, 40, 42, 43, 45, 46, 48, 51, 52, 55, 56, 57, 58, 60, 63, 66, 68, 70, 72, 73, 75, 76, 78, 80, 81, 82, 85, 86, 87, 88, 90, 91, 93, 96, 97, 100, 102, 103, 105, 106, 108, 110, 111, 112, 115, 116, 117, 120

Offset: 1

Eric W. Weisstein, Oct 11 2002

nonn

These are also the boards where any starting configuration can be turned off. - Robert Cowen (robert.cowen(AT)gmail.com), Jan 06 2007. [Comment corrected by Sune Kristian Jakobsen (sunejakobsen(AT)hotmail.com), Feb 04 2008]

N. J. A. Sloane and Thomas Buchholz, Table of n, a(n) for n = 1..1000 [terms were extended by N. J. A. Sloane (based on A117870), May 14 2006; terms 70 through 1000 were computed by Thomas Buchholz, May 16 2014]
K. Sutner, Linear cellular automata and the Garden-of-Eden, Math. Intelligencer, 11 (No. 2, 1989), 49-53.
Eric Weisstein's World of Mathematics, Lights Out Puzzle

Cf. A075462, A076437, A117872. Complement of A117870.

Positive integer n is in this sequence iff A159257(n)=0. [Max Alekseyev, Sep 25 2009]

More terms from N. J. A. Sloane (based on A117870), May 14 2006, and Thomas Buchholz, May 16 2014

A117870 Square board sizes for which the lights out problem does not have a unique solution (counting solutions differing only by rotation and reflection as distinct).

Original entry on oeis.org

4, 5, 9, 11, 14, 16, 17, 19, 23, 24, 29, 30, 32, 33, 34, 35, 39, 41, 44, 47, 49, 50, 53, 54, 59, 61, 62, 64, 65, 67, 69, 71, 74, 77, 79, 83, 84, 89, 92, 94, 95, 98, 99, 101, 104, 107, 109, 113, 114, 118, 119, 123, 124, 125, 126, 128, 129, 131, 134, 135, 137, 139, 143

Offset: 1

N. J. A. Sloane, May 14 2006

nonn

Numbers k such that a k X k parity pattern exists (see A118141). - Don Knuth, May 11 2006

Max Alekseyev and Thomas Buchholz, Table of n, a(n) for n = 1..1000 [terms were extended by Max Alekseyev, Sep 17 2009; terms 64 through 1000 were computed by Thomas Buchholz, May 16 2014]
Jaap's puzzle page, The Mathematics of Lights Out
K. Sutner, Linear cellular automata and the Garden-of-Eden, Math. Intelligencer, 11 (No. 2, 1989), 49-53.
Eric Weisstein's World of Mathematics, Lights-Out Puzzle
Wikipedia, Lights Out (game)

Cf. A075462, A076437, A117872. Complement of A076436.

a(n) = A093614(n) - 1.

Contains positive integers k such that A159257(k) > 0. - Max Alekseyev, Sep 17 2009

More terms from Max Alekseyev, Sep 17 2009, and 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

A165738 Rank deficiency (= dimension of the null space) of the n X n "Lights Out" puzzle on a torus.

Original entry on oeis.org

0, 0, 4, 0, 8, 8, 0, 0, 4, 16, 0, 16, 0, 0, 12, 0, 16, 8, 0, 32, 4, 0, 0, 32, 8, 0, 4, 0, 0, 24, 40, 0, 44, 32, 8, 16, 0, 0, 4, 64, 0, 8, 0, 0, 12, 0, 0, 64, 0, 16, 20, 0, 0, 8, 8, 0, 4, 0, 0, 48, 0, 80, 52, 0, 56, 88, 0, 64, 4, 16, 0, 32, 0, 0, 12, 0, 0, 8, 0, 128, 4, 0, 0, 16, 24, 0, 4, 0, 0, 24

Offset: 1

Max Alekseyev, Sep 25 2009

nonn

The number of solutions to the puzzle is 2^a(n). If a(n)=0 then the puzzle has a unique solution.

See A075462 for further references.

Max Alekseyev and Thomas Buchholz, Table of n, a(n) for n = 1..1000. (Terms n=91 through n=1000 from Thomas Buchholz, May 20 2014)
M. Anderson and T. Feil, Turning Lights Out with Linear Algebra, Mathematics Magazine, 71 (1998), 300-303.
Andries E. Brouwer, Lights Out and Button Madness Games. [Gives theory and a(n) for n = 1..1000, Jun 19 2008]
Eric Weisstein's World of Mathematics, Lights Out Puzzle

Cf. A159257.

a(n) <= 2n.

a(n) is a multiple of 4 and satisfies a(2n) = 2a(n). a(n+1) = 2 * A159257(n) + 4 if n = 2 (mod 3) and a(n+1) = 2 * A159257(n) otherwise. - Thomas Buchholz, May 22 2014

More terms from Thomas Buchholz, May 20 2014

A165740 Positive integers n such that solution to the toric n X n "Lights Out" puzzle is not unique (up to the order of flippings; each flipping appears at most once).

Original entry on oeis.org

3, 5, 6, 9, 10, 12, 15, 17, 18, 20, 21, 24, 25, 27, 30, 31, 33, 34, 35, 36, 39, 40, 42, 45, 48, 50, 51, 54, 55, 57, 60, 62, 63, 65, 66, 68, 69, 70, 72, 75, 78, 80, 81, 84, 85, 87, 90, 93, 95, 96, 99, 100, 102, 105, 108, 110, 111, 114, 115, 117, 119, 120, 123, 124, 125, 126

Offset: 1

Max Alekseyev, Sep 25 2009

nonn

Complement to the sequence A165741 in the set of positive integers.

Any positive multiple of a member of this sequence is also a member. Primitive elements are in A007802. - Thomas Buchholz, May 23 2014

See A165738 for the references.

Max Alekseyev and Thomas Buchholz, Table of n, a(n) for n = 1..1000 [terms 67 through 1000 were computed by Thomas Buchholz, May 20 2014]

Cf. A159257, A075462, A117870, A165741, A007802, A165738.

A number n is in this sequence iff A165738(n) > 0.

More terms from Thomas Buchholz, May 20 2014

A165741 Positive integers n such that the toric n X n "Lights Out" puzzle has a unique solution (up to the order of flippings; each flipping appears at most once).

Original entry on oeis.org

1, 2, 4, 7, 8, 11, 13, 14, 16, 19, 22, 23, 26, 28, 29, 32, 37, 38, 41, 43, 44, 46, 47, 49, 52, 53, 56, 58, 59, 61, 64, 67, 71, 73, 74, 76, 77, 79, 82, 83, 86, 88, 89, 91, 92, 94, 97, 98, 101, 103, 104, 106, 107, 109, 112, 113, 116, 118, 121, 122, 128, 131, 133, 134, 137

Offset: 1

Max Alekseyev, Sep 25 2009

nonn

Complement to the sequence A165740 in the set of positive integers.

See A165738 for the references.

Max Alekseyev and Thomas Buchholz, Table of n, a(n) for n = 1..1000 [terms 66 through 1000 were computed by Thomas Buchholz, May 20 2014]

Cf. A159257, A075462, A076436, A165740.

n is in this sequence iff A165738(n)=0.

More terms from Thomas Buchholz, May 20 2014

A220195 Sum of neighbor maps: log base 2 of the number of n X n binary arrays indicating the locations of corresponding elements equal to the sum mod 2 of their horizontal and vertical neighbors in a random 0..1 n X n array.

Original entry on oeis.org

1, 4, 9, 12, 23, 36, 49, 64, 73, 100, 115, 144, 169, 192, 225, 248, 287, 324, 345, 400, 441, 484, 515, 572, 625, 676, 729, 784, 831, 880, 961, 1004, 1073, 1152, 1219, 1296, 1369, 1444, 1489, 1600, 1679, 1764, 1849, 1932, 2025, 2116, 2179, 2304, 2393, 2492

Offset: 1

R. H. Hardin, Dec 07 2012

nonn

Diagonal of A220196.
Also, equals n^2 - A159257(n).
The entries describe the rank of the Lights Out problem of size n (see A159257).

			Some solutions for n=3
..1..1..0....0..1..1....0..0..0....1..1..1....0..1..0....1..0..0....0..0..1
..1..0..1....0..0..0....0..0..1....1..1..0....0..0..0....0..0..1....1..0..1
..1..0..0....1..0..0....1..0..0....0..1..0....1..1..1....0..0..0....1..1..0

Cf. A159257, A220196.

Table[n^2 - (First[Dimensions[NullSpace[AdjacencyMatrix[GridGraph[{n, n}]] + IdentityMatrix[n*n], Modulus->2]]]), {n, 1, 40}] (* Vincenzo Librandi, Feb 10 2017 *)

More terms from Vincenzo Librandi, Feb 10 2017

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

A076436 Square board sizes for which the lights-out problem has a unique solution (counting solutions differing only by rotation and reflection as distinct).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A117870 Square board sizes for which the lights out problem does not have a unique solution (counting solutions differing only by rotation and reflection as distinct).

Views

Author

Keywords

Comments

Links

Crossrefs

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

A165738 Rank deficiency (= dimension of the null space) of the n X n "Lights Out" puzzle on a torus.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A165740 Positive integers n such that solution to the toric n X n "Lights Out" puzzle is not unique (up to the order of flippings; each flipping appears at most once).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A165741 Positive integers n such that the toric n X n "Lights Out" puzzle has a unique solution (up to the order of flippings; each flipping appears at most once).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A220195 Sum of neighbor maps: log base 2 of the number of n X n binary arrays indicating the locations of corresponding elements equal to the sum mod 2 of their horizontal and vertical neighbors in a random 0..1 n X n array.

Views

Author

Keywords

Comments

Examples

Crossrefs