cp's OEIS Frontend

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

%I A159257 #114 Feb 16 2025 08:33:10
%S A159257 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,
%T A159257 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,
%U A159257 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
%N A159257 Rank deficiency of the Lights Out problem of size n.
%C A159257 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.
%C A159257 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.
%C A159257 a(n) is nonzero iff n is in A117870; a(n) is zero iff n is in A076436. - _Max Alekseyev_, Sep 17 2009
%C A159257 a(n) is even and satisfies a(n) <= n. - _Thomas Buchholz_, May 19 2014
%C A159257 For all indices n and natural numbers k, a(n*k - 1) >= a(n - 1). - _William Boyles_, Jun 17 2022
%D A159257 See A075462 for references.
%H A159257 William Boyles, <a href="/A159257/b159257.txt">Table of n, a(n) for n = 1..25000</a> (first 1000 terms by Max Alekseyev and Thomas Buchholz).
%H A159257 Andries E. Brouwer, <a href="http://www.win.tue.nl/~aeb/ca/madness/madrect.html">Lights Out and Button Madness Games</a> [Gives theory and a(n) for n = 1..1000, Jun 19 2008]
%H A159257 JeuxT45, <a href="http://www.t45ol.com/play/1109/turn-it-red.html">Turn it red</a> [Dead link]
%H A159257 Martin Kreh, <a href="http://www.jstor.org/stable/10.4169/amer.math.monthly.124.10.937">"Lights Out" and Variants</a>, The American Mathematical Monthly 124:10 (2017), 937-950.
%H A159257 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/LightsOutPuzzle.html">Lights Out Puzzle</a>
%F A159257 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
%e A159257 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.
%t A159257 Table[First[Dimensions[NullSpace[AdjacencyMatrix[GridGraph[{n, n}]] + IdentityMatrix[n*n],Modulus -> 2]]], {n, 2, 30}]
%t A159257 (* Or Faster *)
%t A159257 A[k_] := DiagonalMatrix[Array[1 &, k - 1], -1] +
%t A159257   DiagonalMatrix[Array[1 &, k - 1], 1] + IdentityMatrix[k];
%t A159257 B[k_, 0] := IdentityMatrix[k];
%t A159257 B[k_, 1] := A[k];
%t A159257 B[k_, n_] := B[k, n] = Mod[A[k].B[k, n - 1] + B[k, n - 2], 2];
%t A159257 Table[First[Dimensions[NullSpace[B[n, n], Modulus -> 2]]], {n, 2, 30}]
%t A159257 (* _Birkas Gyorgy_, Jun 10 2011 *)
%o A159257 (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
%o A159257 (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
%Y A159257 Cf. A075462, A075463, A075464, A076436, A076437.
%K A159257 nonn
%O A159257 1,4
%A A159257 Bruno Vallet (bruno.vallet(AT)gmail.com), Apr 07 2009
%E A159257 More terms from _Max Alekseyev_, Sep 17 2009
%E A159257 More terms from _Thomas Buchholz_, May 16 2014