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, 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).

Links

Table of n, a(n) for n=1..30.

Carlos Rivera, Prime Puzzle #772

Klaus Sutner, Linear Cellular Automata and the Garden-of-Eden, Mathematical Intelligencer Vol 11, No. 2 1989.

Index entries related to cellular automata

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

Adjacent sequences: A254457 A254458 A254459 * A254461 A254462 A254463

Keyword

nonn

Author

W. Edwin Clark, Jan 30 2015

Status

approved