A246031 -id:A246031 - cp's OEIS frontend

A246032 a(n) = A246031(2^n-1).

1, 26, 124, 1400, 10000, 89504, 707008, 5924480, 47900416, 393069824, 3189761536, 25963397888, 210468531712, 1706090904320, 13803141607936, 111595408530176, 901164713600512, 7271581998320384, 58625571435837952, 472335388734974720, 3803021424555945472, 30602681612309510912, 246127842107210007040

Offset: 0

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

nonn

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)

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.
Index entries for sequences related to cellular automata

Cf. A246031.

P := 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

# 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);

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 *)

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.

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

A255364 Partial sums of A246031.

Original entry on oeis.org

1, 27, 53, 177, 203, 879, 1003, 2403, 2429, 3105, 3781, 7005, 7129, 10353, 11753, 21753, 21779, 22455, 23131, 26355, 27031, 44607, 47831, 84231, 84355, 87579, 90803, 106179, 107579, 143979, 153979, 243483, 243509, 244185, 244861, 248085, 248761, 266337, 269561, 305961, 306637, 324213, 341789, 425613, 428837, 512661, 549061, 809061

Offset: 0

Omar E. Pol, Feb 21 2015

nonn

Total number of cubic ON cells after n generations in a three-dimensional structure in which A246031(n) gives the number of cubic ON cells in the n-th cubic layer of the structure. A cubic ON cell remains ON forever. The structure looks like an irregular cube (or hexahedron).

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

Cf. A160239, A245542, A246031, A246032.

A255477 Number of ON cells after n generations in 4-D cellular automaton defined by 4-dimensional analog of Moore neighborhood, when started with a single ON cell at generation 0.

Original entry on oeis.org

1, 80, 80, 624, 80, 6400, 624, 16480, 80, 6400, 6400, 49920, 624, 49920, 16480, 221888, 80, 6400, 6400, 49920, 6400, 512000, 49920, 1318400, 624, 49920, 49920, 389376, 16480, 1318400, 221888, 4245888, 80, 6400, 6400, 49920, 6400, 512000, 49920, 1318400, 6400, 512000, 512000, 3993600, 49920, 3993600, 1318400

Offset: 0

Doron Zeilberger, Feb 26 2015

nonn

Run length transform of A255478.

Shalosh B. Ekhad, Details about A255477 and A255478
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

Cf. A255478.

See also A160239 and A246031 for analogs in 2 and 3 dimensions.

cp's OEIS Frontend

A246032 a(n) = A246031(2^n-1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

Extensions

A255364 Partial sums of A246031.

Views

Author

Keywords

Comments

Links

Crossrefs

A255477 Number of ON cells after n generations in 4-D cellular automaton defined by 4-dimensional analog of Moore neighborhood, when started with a single ON cell at generation 0.

Views

Author

Keywords

Comments

Links

Crossrefs