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

Author

W. Edwin Clark, Jan 30 2015

Keywords

• nonn

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

Examples

			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.
		

Links

• 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

Crossrefs

Cf. A013713.

Programs

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:

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