

A254460


a(n) is the number of predecessors of the allones 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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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^(2n1).


LINKS

Table of n, a(n) for n=1..30.
Carlos Rivera, Prime Puzzle #772
Klaus Sutner, Linear Cellular Automata and the GardenofEden, 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^3x^28*x1) / ((x1)*(4*x1)*(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 allones 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^2LinearAlgebra: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



