A254460 - cp's OEIS frontend

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.

%I A254460 #36 Sep 09 2017 23:27:02
%S A254460 1,8,1,1,512,1,1,32768,1,1,2097152,1,1,134217728,1,1,8589934592,1,1,
%T A254460 549755813888,1,1,35184372088832,1,1,2251799813685248,1,1,
%U A254460 144115188075855872,1
%N 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.
%C A254460 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).
%C A254460 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).
%H A254460 Carlos Rivera, <a href="http://www.primepuzzles.net/puzzles/puzz_772.htm">Prime Puzzle #772</a>
%H A254460 Klaus Sutner, <a href="http://www.link.cs.cmu.edu/15859-s11/notes/sutner.pdf">Linear Cellular Automata and the Garden-of-Eden</a>, Mathematical Intelligencer Vol 11, No. 2 1989.
%H A254460 <a href="https://oeis.org/wiki/Index_to_OEIS:_Section_Ce#cell">Index entries related to cellular automata</a>
%F A254460 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
%e A254460 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.
%p A254460 a:=proc(n)
%p A254460 local A,A1,V,E,i,j,G,f,g,w;
%p A254460 V:=NULL:
%p A254460 E:={}:
%p A254460 for i from 1 to n do
%p A254460 for j from 1 to n do
%p A254460 V:=V,[i,j];
%p A254460 E:=E union {seq(seq({[i,j],[i+x,j+y]},x=-1..1),y=-1..1)};
%p A254460 od:
%p A254460 od:
%p A254460 V:=[V];
%p A254460 E:=remove(t->evalb(has(t,0) or has(t,n+1)),E):
%p A254460 E:=remove(t->evalb(nops(t) = 1),E):
%p A254460 for i from 1 to nops(V)do
%p A254460    f(V[i]):=i:
%p A254460 od:
%p A254460 g:=proc(U)
%p A254460   map(f,U);
%p A254460 end:
%p A254460 G:=GraphTheory:-Graph(map(f, V), map(g, E));
%p A254460 A:=GraphTheory:-AdjacencyMatrix(G)+LinearAlgebra[IdentityMatrix](n^2);
%p A254460 A1:=LinearAlgebra:-Modular:-Mod(2, convert(A,listlist), integer[]);
%p A254460 w:=n^2-LinearAlgebra:-Modular:-Rank(2, A1);
%p A254460 return 2^w;
%p A254460 end proc:
%Y A254460 Cf. A013713.
%K A254460 nonn
%O A254460 1,2
%A A254460 _W. Edwin Clark_, Jan 30 2015

cp's OEIS Frontend