login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (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^(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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 16 10:17 EDT 2021. Contains 345056 sequences. (Running on oeis4.)