login
A254460
a(n) is the number of predecessors of the all-ones state of the binary cellular automaton on the n X n grid graph with edges joining diagonal neighbors as well as vertical and horizontal neighbors, whose local rule is f(i,j) = sum of the state at vertex (i,j) and the states at all of its neighbors mod 2.
1
1, 8, 1, 1, 512, 1, 1, 32768, 1, 1, 2097152, 1, 1, 134217728, 1, 1, 8589934592, 1, 1, 549755813888, 1, 1, 35184372088832, 1, 1, 2251799813685248, 1, 1, 144115188075855872, 1
OFFSET
1,2
COMMENTS
This sequence arose in a discussion among Carlos Rivera, Emmanuel Vantieghem, Dmitry Kamenetsky, W. Edwin Clark, Fred Schneider, Ramón David, and Claudio Meller concerning Puzzle 772 at Prime Puzzles (see Prime Puzzle #772 link).
Later we discovered the relationship to Sutner's paper. A corollary of that paper is that a(n) > 0 for all n. An obvious conjecture is that a(n) = 1 for n mod 3 = 0 or 1 and if n mod 3 = 2 then a(n) = 2^(2n-1).
FORMULA
Empirical g.f.: -x*(64*x^5+8*x^4+64*x^3-x^2-8*x-1) / ((x-1)*(4*x-1)*(x^2+x+1)*(16*x^2+4*x+1)). - Colin Barker, Jan 31 2015
EXAMPLE
For n = 2 the a(2) = 8 predecessors of the all-ones matrix are the eight 2 X 2 binary matrices with one or three zero entries.
MAPLE
a:=proc(n)
local A, A1, V, E, i, j, G, f, g, w;
V:=NULL:
E:={}:
for i from 1 to n do
for j from 1 to n do
V:=V, [i, j];
E:=E union {seq(seq({[i, j], [i+x, j+y]}, x=-1..1), y=-1..1)};
od:
od:
V:=[V];
E:=remove(t->evalb(has(t, 0) or has(t, n+1)), E):
E:=remove(t->evalb(nops(t) = 1), E):
for i from 1 to nops(V)do
f(V[i]):=i:
od:
g:=proc(U)
map(f, U);
end:
G:=GraphTheory:-Graph(map(f, V), map(g, E));
A:=GraphTheory:-AdjacencyMatrix(G)+LinearAlgebra[IdentityMatrix](n^2);
A1:=LinearAlgebra:-Modular:-Mod(2, convert(A, listlist), integer[]);
w:=n^2-LinearAlgebra:-Modular:-Rank(2, A1);
return 2^w;
end proc:
CROSSREFS
Cf. A013713.
Sequence in context: A178046 A176340 A111835 * A198830 A254244 A232068
KEYWORD
nonn
AUTHOR
W. Edwin Clark, Jan 30 2015
STATUS
approved