|
| |
|
|
A159257
|
|
Rank deficiency of the Lights Out problem of size n.
|
|
6
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 1,4
|
|
|
COMMENTS
| A square array of n by 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 nA^2 by nA^2 matrix in Z/2Z. The sequence is the rank deficiency of the matrix, such that the terms at 0 correspond to the sizes for which the general case admits a solution, and the others correspond to the dimension of the space of initial configurations that do not admit 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 non-zero iff n is in A117870; a(n) is zero iff n is in A076436. [From Max Alekseyev (maxale(AT)gmail.com), Sep 17 2009]
|
|
|
REFERENCES
| See A075462 for references. [From Max Alekseyev (maxale(AT)gmail.com), Sep 17 2009]
|
|
|
LINKS
| Turn it red
Eric Weisstein's World of Mathematics, Lights Out Puzzle [From Max Alekseyev (maxale(AT)gmail.com), Sep 17 2009]
|
|
|
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}]
(* Gyorgy Birkas, Jun 10 2011 *)
|
|
|
CROSSREFS
| Cf. A075462, A075463, A075464, A076436, A076437 [From Max Alekseyev (maxale(AT)gmail.com), Sep 17 2009]
Sequence in context: A105087 A028572 A107492 * A107088 A137986 A093486
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 (maxale(AT)gmail.com), Sep 17 2009
|
| |
|
|
