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

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

A093614 Numbers n such that F_n(x) and F_n(1-x) have a common factor mod 2, with F_n(x) = U(n-1,x/2) the monic Chebyshev polynomials of second kind.

Original entry on oeis.org

5, 6, 10, 12, 15, 17, 18, 20, 24, 25, 30, 31, 33, 34, 35, 36, 40, 42, 45, 48, 50, 51, 54, 55, 60, 62, 63, 65, 66, 68, 70, 72, 75, 78, 80, 84, 85, 90, 93, 95, 96, 99, 100, 102, 105, 108, 110, 114, 115, 119, 120, 124, 125, 126, 127, 129, 130, 132, 135, 136, 138

Offset: 1

Ralf Stephan, May 22 2004

nonn

Goldwasser et al. proved that 2^k+-1 belongs to the set, for k>4.

Closed under multiplication by positive integers. - Don Knuth, May 11 2006

Ralf Stephan and Thomas Buchholz, Table of n, a(n) for n = 1..1000 [terms 1 through 61 were computed by Ralf Stephan, May 22 2004; terms 62 through 1000 by Thomas Buchholz, May 16 2014]
M. Hunziker, A. Machiavelo and J. Park, Chebyshev polynomials over finite fields and reversibility of sigma-automata on square grids, Theoretical Comp. Sci., 320 (2004), 465-483.
K. Sutner, Linear cellular automata and the Garden-of-Eden, Math. Intelligencer, 11 (No. 2, 1989), 49-53.
K. Sutner, The computational complexity of cellular automata, in Lect. Notes Computer Sci., 380 (1989), 451-459.
Eric Weisstein's World of Mathematics, Lights-Out Puzzle

Equals A117870(n) + 1.

Cf. A094425 (primitive elements), A076436.

{ F2(n)=local(t, t1, t2, tmp); t1=Mod(0, 2); t2=Mod(1, 2); t=Mod(1, 2)*x; for(k=2, n, tmp=t*t2-t1; t1=t2; t2=tmp); tmp }
for(n=2, 200, t=F2(n); if(gcd(t, subst(t, x, 1-x))!=1, print1(n", ")))

More terms from Thomas Buchholz, May 16 2014

A118141 Length of the longest perfect parity pattern with n columns.

Original entry on oeis.org

2, 3, 5, 4, 23, 8, 11, 27, 29, 30, 47, 62, 17, 339, 23, 254, 167, 512, 59, 2339, 185, 2046, 95, 1024, 125, 2043, 35, 3276, 2039, 340, 47, 4091, 509, 4094, 335, 3590, 1025, 16379, 119, 1048574, 4679, 16382, 371, 92819, 12281, 8388606, 191, 2097152, 6149, 262139

Offset: 1

Don Knuth, May 11 2006

nonn

Also the length of the unique perfect parity pattern whose first row is 0....01 (with n-1 zeros).
Definitions: A parity pattern is a matrix of 0's and 1's with the property that every 0 is adjacent to an even number of 1's and every 1 is adjacent to an odd number of 1's.
It is called perfect if no row or column is entirely zero. Every parity pattern can be built up in a straightforward way from the smallest perfect subpattern in its upper left corner.
For example, the 3 X 2 matrix
11
00
11
is a parity pattern built up from the perfect 1 X 2 pattern "11". The 3 X 5 matrix
01010
11011
01010
is similarly built up from the perfect 3 X 2 pattern of its first two columns. The 4 X 4 matrix
0011
0100
1101
0101
is perfect. So is the 5 X 5
01110
10101
11011
10101
01110
which moreover has 8-fold symmetry (cf. A118143).
All perfect parity patterns of n columns can be shown to have length d-1 where d divides a(n)+1.

D. E. Knuth, The Art of Computer Programming, Section 7.1.3.

Andries E. Brouwer, Jun 15 2008, Table of n, a(n) for n = 1..85
Andries E. Brouwer, Button Madness and Lights Out on rectangles

The number of perfect parity patterns that have exactly n columns is A000740.
The sequence of all n such that an n X n parity pattern exists is A117870 (cf. A076436, A093614, A094425).
Cf. also A118142, A118143.
Cf. A007802.

More terms from John W. Layman, May 17 2006

More terms from Andries E. Brouwer, Jun 15 2008

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

Original entry on oeis.org

1, 2, 3, 5, 6, 7, 8, 10, 12, 13, 15, 17, 18, 20, 21, 22, 25, 26, 27, 28, 31, 36, 37, 38, 40, 41, 42, 43, 45, 46, 48, 51, 52, 53, 55, 56, 57, 58, 60, 63, 66, 68, 70, 72, 73, 75, 76, 77, 78, 80

Offset: 1

Eric W. Weisstein, Oct 11 2002

M. Anderson and T. Feil, Turning Lights Out with Linear Algebra, Mathematics Magazine, 71 (1998), 300-303
Eric Weisstein's World of Mathematics, Lights Out Puzzle

Cf. A075463, A076436.

More terms from Zhao Hui Du, Mar 29 2014

A094425 Numbers n such that F_n(x) and F_n(1-x) have a common factor mod 2, with F_n(x) = U(n-1,x/2) the monic Chebyshev polynomials of second kind; this lists only the primitive elements of the set.

Original entry on oeis.org

5, 6, 17, 31, 33, 63, 127, 129, 171, 257, 511, 683, 2047, 2731, 2979, 3277, 3641, 8191, 28197, 43691, 48771, 52429, 61681, 65537, 85489, 131071

Offset: 1

Ralf Stephan, May 22 2004

Klaus Sutner, Jun 26 2006, remarks that it can be shown that this sequence is infinite.

Dieter Gebhardt, "Cross pattern puzzles revisited," Cubism For Fun 69 (March 2006), 23-25.

K. Sutner, Linear cellular automata and the Garden-of-Eden, Math. Intelligencer, 11 (No. 2, 1989), 49-53.
K. Sutner, The computational complexity of cellular automata, in Lect. Notes Computer Sci., 380 (1989), 451-459.
K. Sutner, sigma-Automata and Chebyshev-polynomials, Theoretical Comp. Sci., 230 (2000), 49-73.
M. Hunziker, A. Machiavelo and J. Park, Chebyshev polynomials over finite fields and reversibility of sigma-automata on square grids, Theoretical Comp. Sci., 320 (2004), 465-483.
Eric Weisstein's World of Mathematics, Lights-Out Puzzle

Cf. A093614 (all elements), A076436.

Gebhardt and Sutner references from Don Knuth, May 11 2006

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

A334443 Number of unlabeled connected n-vertex graphs for which the lights out puzzle has a unique solution.

Original entry on oeis.org

1, 0, 1, 2, 9, 33, 290, 3692, 94280, 4454654

Offset: 1

Pontus von Brömssen, Apr 30 2020

The lights out puzzle on a graph has a unique solution if and only if the graph has an odd number of matchings. (See Section 6 in the paper by Eriksson, Eriksson, and Sjöstrand.)

			The connected 4-vertex graphs for which the lights out puzzle has a unique solution are the path and the cycle, so a(4)=2.

H. Eriksson, K. Eriksson, J. Sjöstrand, Note on the lamp lighting problem, Advances in Applied Mathematics 27 (2001), 357-366.
Eric Weisstein's World of Mathematics, Lights Out Puzzle

Cf. A076436.

Inverse Euler transform of A334444.

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

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

A093614 Numbers n such that F_n(x) and F_n(1-x) have a common factor mod 2, with F_n(x) = U(n-1,x/2) the monic Chebyshev polynomials of second kind.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Extensions

A118141 Length of the longest perfect parity pattern with n columns.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Extensions

A094425 Numbers n such that F_n(x) and F_n(1-x) have a common factor mod 2, with F_n(x) = U(n-1,x/2) the monic Chebyshev polynomials of second kind; this lists only the primitive elements of the set.

Views

Author

Keywords

Comments

References

Links

Crossrefs

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