This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A159257 Rank deficiency of the Lights Out problem of size n. 9
 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 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,4 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 consists in turning 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 If a(n) is nonzero, then a(2n+1) is also nonzero. - William Boyles, Jun 28 2018 REFERENCES See A075462 for references. LINKS Max Alekseyev and Thomas Buchholz, Table of n, a(n) for n = 1..1000 [recomputed these a(n), May 16 2014] 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 FORMULA Let f(k, 2x) be the Chebyshev Polynomial of the Second Kind in Limit Field F_2. So f(0,x)=1, f(1,x)=x, f(2,x)=(1+x)^2, f(n+1,x)=x*f(n,x)+f(n-1,x). The degree of gcd(f(n,x), f(n, 1+x)) is this sequence. For example, f(5,x)=x^5+x=x(1+x)^4. f(5, 1+x)=x^4(1+x). So their GCD is x(1+x) and the degree is 2. So the 5th element of the array is 2. - Zhao Hui Du, Mar 17 2014 EXAMPLE 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. 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 *) PROG (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 CROSSREFS Cf. A075462, A075463, A075464, A076436, A076437. Sequence in context: A320647 A028572 A107492 * A258997 A232833 A256269 Adjacent sequences:  A159254 A159255 A159256 * A159258 A159259 A159260 KEYWORD nonn AUTHOR Bruno Vallet (bruno.vallet(AT)gmail.com), Apr 07 2009 EXTENSIONS More terms from Max Alekseyev, Sep 17 2009 More terms from Thomas Buchholz, May 16 2014 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified July 20 16:15 EDT 2019. Contains 325185 sequences. (Running on oeis4.)