A246031 Number of ON cells in 3-D cellular automaton described in Comments, after n generations.

1, 26, 26, 124, 26, 676, 124, 1400, 26, 676, 676, 3224, 124, 3224, 1400, 10000, 26, 676, 676, 3224, 676, 17576, 3224, 36400, 124, 3224, 3224, 15376, 1400, 36400, 10000, 89504, 26, 676, 676, 3224, 676, 17576, 3224, 36400, 676, 17576, 17576, 83824, 3224, 83824, 36400, 260000, 124, 3224, 3224, 15376, 3224, 83824, 15376, 173600, 1400, 36400, 36400, 173600, 10000, 260000, 89504, 707008

Offset: 0

Author

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

Keywords

• nonn

Comments

We work on the cells of the 3-D grid. Each cell has 26 neighbors, A cell is ON iff an odd number of its neighbors were ON at the previous generation. We start with a single ON cell.

The Run Length Transform of a sequence {S(n), n>=0} is defined to be the sequence {T(n), n>=0} given by T(n) = Product_i S(i), where i runs through the lengths of runs of 1's in the binary expansion of n. E.g., 19 is 10011 in binary, which has two runs of 1's, of lengths 1 and 2. So T(19) = S(1)*S(2). T(0)=1 (the empty product).

Examples

			The entries form blocks of sizes 1,1,2,4,8,...:
1,
26,
26, 124,
26, 676, 124, 1400,
26, 676, 676, 3224, 124, 3224, 1400, 10000,
26, 676, 676, 3224, 676, 17576, 3224, 36400, 124, 3224, 3224, 15376, 1400, 36400, 10000, 89504,
26, 676, 676, 3224, 676, 17576, 3224, 36400, 676, 17576, 17576, 83824, 3224, 83824, 36400, 260000, 124, 3224, 3224, 15376, 3224, 83824, 15376, 173600, 1400, 36400, 36400, 173600, 10000, 260000, 89504, 707008
...
From _Omar E. Pol_, Mar 19 2015: (Start)
Also, the sequence can be written as an irregular tetrahedron T(s,r,k) as shown below:
1;
..
26;
...
26;
124;
..........
26,   676;
124;
1400;
.....................
26,   676, 676, 3224;
124,  3224;
1400;
10000;
............................................
26,   676,  676, 3224, 676,17576,3224,36400;
124,  3224, 3224, 15376;
1400, 36400;
10000;
89504;
..........................................................................................
26,   676,  676, 3224, 676,17576,3224,36400,676,17576,17576,83824,3224,83824,36400,260000;
124,  3224, 3224, 15376, 3224, 83824, 15376, 173600;
1400, 36400, 36400, 173600;
10000, 260000;
89504;
707008;
...
Apart from the initial 1, we have that T(s,r,k) = T(s+1,r,k).
(End)
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1022
• 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

Crossrefs

A 3-D analog of A160239 (2-D) and A255477 (4-D). Cf. A246032.

Programs

Magma

P := PolynomialRing(GF(2),3);
f := (1+x+x^2)*(1+y+y^2)*(1+z+z^2)-x*y*z;
p := 1;
for i := 1 to 100 do
  p := p*f;
  print(#Terms(p));
end for; // Roman Pearce, Feb 18 2015

Maple

# This is a very inefficient program!
f:=expand((1+x+x^2)*(1+y+y^2)*(1+z+z^2))-x*y*z;
g:=n->expand(f^n) mod 2;
h:=n->subs({x=1,y=1,z=1},g(n));
[seq(h(n),n=0..30)];
# Better program from Roman Pearce, Feb 18 2015:
f := Expand((1+x+x^2)*(1+y+y^2)*(1+z+z^2)-x*y*z) mod 2:
p := 1;
for i from 1 to 100 do
  p := Expand(p*f) mod 2;
  lprint(nops(p));
end do:

Mathematica

f = (1 + x + x^2)*(1 + y + y^2)*(1 + z + z^2) - x*y*z;
p = 1; Print[1];
Join[{1}, Table[p = Expand[p*f] // PolynomialMod[#, 2]&; Lp = Length[p]; Print[Lp]; Lp, 100]] (* Jean-François Alcover, Jan 17 2018 *)

Formula

This is the Run Length Transform of A246032 (see Comments).