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

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

Author

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

Keywords

• nonn

Comments

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

Examples

			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.
		

References

• See A075462 for references.

Links

• 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

Crossrefs

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

Programs

Mathematica

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

PARI

{ 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

PARI

{ 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

Formula

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

Extensions

More terms from Max Alekseyev, Sep 17 2009

More terms from Thomas Buchholz, May 16 2014