A075462 -id:A075462 - cp's OEIS frontend

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

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

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

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

A075464 a(n) is the minimal number of nontrivial switch flippings needed to solve the all-ones lights out problem on an n X n square.

Original entry on oeis.org

1, 4, 5, 4, 15, 28, 33, 40, 25, 44, 55, 72, 105, 56, 117, 104, 147, 188, 141, 224, 245, 276, 231, 270, 353, 356, 405, 416, 345, 376, 553, 428, 469, 520, 563, 600, 761, 772, 561, 696, 891, 940, 953, 772, 1069, 1188, 971, 1096, 1165, 1220, 1317, 1256, 1487, 1400

Offset: 1

Eric W. Weisstein, Sep 17 2002

For squares having multiple possible solutions (see A075462, A075463), there may be nontrivial solutions involving *more* than this number of flips.

See A075462 for references.

Zhao Hui Du, Table of n, a(n) for n = 1..78 (terms 1..60 from Max Alekseyev)
Eric Weisstein's World of Mathematics, Lights Out Puzzle
Zhao Hui Du, C code for the problem (please compile it using the latest gcc with option -O3 -msse4.2)

Cf. A075462, A075463.

a(26)-a(29) from Les Reid, Sep 09 2007
a(30)-a(38) from Max Alekseyev, Sep 17 2009
Extended by Max Alekseyev, Sep 20 2009

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

A144260 Number of symmetric n X n binary matrices with each element equal to one minus the sum of its horizontal and vertical neighbors, modulo two.

Original entry on oeis.org

1, 1, 1, 4, 2, 1, 1, 1, 16, 1, 8, 1, 1, 4, 1, 16, 2, 1, 256, 1, 1, 1, 128, 4, 1, 1, 1, 1

Offset: 1

R. H. Hardin, Sep 16 2008

nonn

A075462 is a(n) without the symmetry restriction.

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.

cp's OEIS Frontend

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

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

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

A075464 a(n) is the minimal number of nontrivial switch flippings needed to solve the all-ones lights out problem on an n X n square.

Views

Author

Keywords

Comments

References

Links

Crossrefs

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