login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A246032 a(n) = A246031(2^n-1). 3
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 Meta-Algorithm for Creating Fast Algorithms for Counting ON Cells in Odd-Rule Cellular Automata, arXiv:1503.01796, 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, 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, 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 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);

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 Zeilbeger_, Feb 20 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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified July 26 06:03 EDT 2017. Contains 289798 sequences.