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

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

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

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