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
Shalosh B. Ekhad, Details about A246031 and A246032
Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, A Meta-Algorithm for Creating Fast Algorithms for Counting ON Cells in Odd-Rule Cellular Automata, arXiv:1503.01796 [math.CO], 2015; see also the Accompanying Maple Package.
Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, Odd-Rule 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.
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 Ekhad-Sloane-Zeilberger 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 26-term 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^k-1 for k = 0..M
# defined by rule that cell is ON iff number of ON cells in nbd at
# time n-1 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] (* Jean-Franç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
KEYWORD
nonn
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