|
|
A159257
|
|
Rank deficiency of the Lights Out problem of size n.
|
|
10
|
|
|
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 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.
For all indices n and natural numbers k, a(n*k - 1) >= a(n - 1). - William Boyles, Jun 17 2022
|
|
REFERENCES
|
|
|
LINKS
|
|
|
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
|
|
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}]
|
|
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
(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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Bruno Vallet (bruno.vallet(AT)gmail.com), Apr 07 2009
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|