



1, 26, 124, 1400, 10000, 89504, 707008, 5924480, 47900416, 393069824, 3189761536, 25963397888, 210468531712, 1706090904320, 13803141607936, 111595408530176, 901164713600512, 7271581998320384, 58625571435837952, 472335388734974720, 3803021424555945472, 30602681612309510912, 246127842107210007040
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

Comments from Michael Monagan on the computation of a(10) and a(11), Sep 01 2014: (Start)
I wrote a C program to compute them. Instead of storing monomials and coefficients, I just store monomials (presence of monomial means 1 mod 2) in an array  this saves a factor of 2 in space.
I used lexicographical order and packed the monomials in x,y,z into a 64 bit machine word: x^i y^j z^k is encoded as i*2^40+j*2^20+k. So the space needed to store p for n=10 is 3189761536 x 8 bytes = 25 gigs.
But the main gain is realizing that for the last step when we compute expand(p*g) mod 2, we don't need to save the product for the next iteration, so we just need to compute the number of terms in p*g mod 2 which we can do if we compute them in any monomial ordering without creating the product. (End)


LINKS

Table of n, a(n) for n=0..22.
Shalosh B. Ekhad, Details about A246031 and A246032
Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, A MetaAlgorithm for Creating Fast Algorithms for Counting ON Cells in OddRule Cellular Automata, arXiv:1503.01796 [math.CO], 2015; see also the Accompanying Maple Package.
Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, OddRule Cellular Automata on the Square Grid, arXiv:1503.04249 [math.CO], 2015.
N. J. A. Sloane, On the No. of ON Cells in Cellular Automata, Video of talk in Doron Zeilberger's Experimental Math Seminar at Rutgers University, Feb. 05 2015: Part 1, Part 2
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015.
Index entries for sequences related to cellular automata


FORMULA

The g.f. is
(1 + 6*x  317*x^2 + 1718*x^3 + 5420*x^4  59432*x^5 + 61312*x^6 + 428928*x^7  887296*x^8  260096*x^9 + 737280*x^10)/((1  8*x)*(1  12*x  17*x^2 + 608*x^3  856*x^4  9920*x^5 + 22576*x^6 + 52992*x^7  140032*x^8  29696*x^9 + 110592*x^10)),
found by Doron Zeilberger  see the EkhadSloaneZeilberger paper and the Ekhad link.


MAPLE

# Maple program from N. J. A. Sloane, Aug 21 2014 with improvements from Roman Pearce, Aug 25 2014
# f is a 26term polynomial, which describes a 3x3x3 cube with the center removed
f := expand((1+x+x^2)*(1+y+y^2)*(1+z+z^2)x*y*z) mod 2;
# count nonzero terms in a polynomial
C := f>`if`(type(f, `+`), nops(f), 1);
# Find number of ON cells in CA for generations 2^k1 for k = 0..M
# defined by rule that cell is ON iff number of ON cells in nbd at
# time n1 was odd where nbd is defined by a polynomial f(x, y, z).
OddCA2 := proc(f, M) global C; local n, a, i, g, p;
g := expand(f) mod 2;
p := g;
a := [1, C(p)];
map(lprint, a);
for n from 2 to M do
g := expand(g^2) mod 2;
p := expand(p*g) mod 2;
a := [op(a), C(p)];
lprint(a[1]);
end do:
[seq(a[i], i=1..nops(a))];
end proc:
OddCA2(f, 9);


MATHEMATICA

f = PolynomialMod[(1+x+x^2)*(1+y+y^2)*(1+z+z^2)  x*y*z // Expand, 2];
c[f_] := If[f[[0]] === Plus, Length[f], 1];
OddCA2[f_, M_] := Module[{n, a, i, g, p},
g = PolynomialMod[Expand[f], 2];
p = g;
a = {1, c[p]};
Print[1]; Print[a[[1]]];
For[n = 2, n <= M, n++,
g = PolynomialMod[Expand[g^2], 2];
p = PolynomialMod[Expand[p*g], 2];
a = Append[a, c[p]];
Print[a[[1]]]
];
a];
OddCA2[f, 9] (* JeanFrançois Alcover, Jan 20 2018, translated from Maple *)


PROG

(MAGMA)
P<x, y, z> := PolynomialRing(GF(2), 3); g := (1+x+x^2)*(1+y+y^2)*(1+z+z^2)x*y*z;
p := g;
for i := 2 to 9 do
g := g*g;
p := p*g;
print(#Terms(p));
end for; // Roman Pearce, Aug 25 2014


CROSSREFS

Cf. A246031.
Sequence in context: A183066 A124954 A126413 * A044358 A044739 A166831
Adjacent sequences: A246029 A246030 A246031 * A246033 A246034 A246035


KEYWORD

nonn,more


AUTHOR

N. J. A. Sloane, Aug 16 2014; corrected Aug 21 2014


EXTENSIONS

a(7), a(8) and a(9) computed with Maple 18 and confirmed with MAGMA by Roman Pearce, Aug 25 2014
a(1)a(9) confirmed by Michael Monagan, Aug 29 2014
a(10) and a(11) from Michael Monagan, Aug 29 2014
a(12) onwards from Doron Zeilberger, Feb 20 2015


STATUS

approved



