A246032 - OEIS

%I #80 Apr 14 2024 09:06:30

%S 1,26,124,1400,10000,89504,707008,5924480,47900416,393069824,

%T 3189761536,25963397888,210468531712,1706090904320,13803141607936,

%U 111595408530176,901164713600512,7271581998320384,58625571435837952,472335388734974720,3803021424555945472,30602681612309510912,246127842107210007040

%N a(n) = A246031(2^n-1).

%C Comments from Michael Monagan on the computation of a(10) and a(11), Sep 01 2014: (Start)

%C 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.

%C 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.

%C 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)

%H Shalosh B. Ekhad, <a href="/A246031/a246031.txt">Details about A246031 and A246032</a>

%H Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, <a href="http://arxiv.org/abs/1503.01796">A Meta-Algorithm for Creating Fast Algorithms for Counting ON Cells in Odd-Rule Cellular Automata</a>, arXiv:1503.01796 [math.CO], 2015; see also the <a href="http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/CAcount.html">Accompanying Maple Package</a>.

%H Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, <a href="http://arxiv.org/abs/1503.04249">Odd-Rule Cellular Automata on the Square Grid</a>, arXiv:1503.04249 [math.CO], 2015.

%H 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: <a href="https://vimeo.com/119073818">Part 1</a>, <a href="https://vimeo.com/119073819">Part 2</a>

%H N. J. A. Sloane, <a href="http://arxiv.org/abs/1503.01168">On the Number of ON Cells in Cellular Automata</a>, arXiv:1503.01168 [math.CO], 2015.

%H <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>

%F The g.f. is

%F (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)),

%F found by Doron Zeilberger - see the Ekhad-Sloane-Zeilberger paper and the Ekhad link.

%p # Maple program from _N. J. A. Sloane_, Aug 21 2014 with improvements from _Roman Pearce_, Aug 25 2014

%p # f is a 26-term polynomial, which describes a 3x3x3 cube with the center removed

%p f := expand((1+x+x^2)*(1+y+y^2)*(1+z+z^2)-x*y*z) mod 2;

%p # count nonzero terms in a polynomial

%p C := f->`if`(type(f,`+`),nops(f),1);

%p # Find number of ON cells in CA for generations 2^k-1 for k = 0..M

%p # defined by rule that cell is ON iff number of ON cells in nbd at

%p # time n-1 was odd where nbd is defined by a polynomial f(x, y, z).

%p OddCA2 := proc(f, M) global C; local n, a, i, g, p;

%p    g := expand(f) mod 2;

%p    p := g;

%p    a := [1,C(p)];

%p    map(lprint,a);

%p    for n from 2 to M do

%p      g := expand(g^2) mod 2;

%p      p := expand(p*g) mod 2;

%p      a := [op(a), C(p)];

%p      lprint(a[-1]);

%p    end do:

%p    [seq(a[i], i=1..nops(a))];

%p end proc:

%p OddCA2(f, 9);

%t f = PolynomialMod[(1+x+x^2)*(1+y+y^2)*(1+z+z^2) - x*y*z // Expand, 2];

%t c[f_] := If[f[[0]] === Plus, Length[f], 1];

%t OddCA2[f_, M_] := Module[{n, a, i, g, p},

%t   g = PolynomialMod[Expand[f], 2];

%t   p = g;

%t   a = {1, c[p]};

%t   Print[1]; Print[a[[-1]]];

%t   For[n = 2, n <= M, n++,

%t    g = PolynomialMod[Expand[g^2], 2];

%t    p = PolynomialMod[Expand[p*g], 2];

%t    a = Append[a, c[p]];

%t    Print[a[[-1]]]

%t   ];

%t a];

%t OddCA2[f, 9] (* _Jean-François Alcover_, Jan 20 2018, translated from Maple *)

%o (Magma)

%o P<x,y,z> := PolynomialRing(GF(2),3);g := (1+x+x^2)*(1+y+y^2)*(1+z+z^2)-x*y*z;

%o p := g;

%o for i := 2 to 9 do

%o   g := g*g;

%o   p := p*g;

%o   print(#Terms(p));

%o end for; // _Roman Pearce_, Aug 25 2014

%Y Cf. A246031.

%K nonn

%O 0,2

%A _N. J. A. Sloane_, Aug 16 2014; corrected Aug 21 2014

%E a(7), a(8) and a(9) computed with Maple 18 and confirmed with MAGMA by _Roman Pearce_, Aug 25 2014

%E a(1)-a(9) confirmed by Michael Monagan, Aug 29 2014

%E a(10) and a(11) from Michael Monagan, Aug 29 2014

%E a(12) onwards from _Doron Zeilberger_, Feb 20 2015