cp's OEIS Frontend

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

%I A246031 #47 Jul 11 2025 18:40:09
%S A246031 1,26,26,124,26,676,124,1400,26,676,676,3224,124,3224,1400,10000,26,
%T A246031 676,676,3224,676,17576,3224,36400,124,3224,3224,15376,1400,36400,
%U A246031 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
%N A246031 Number of ON cells in 3-D cellular automaton described in Comments, after n generations.
%C A246031 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.
%C A246031 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).
%H A246031 Alois P. Heinz, <a href="/A246031/b246031.txt">Table of n, a(n) for n = 0..1022</a>
%H A246031 Shalosh B. Ekhad, <a href="/A246031/a246031.txt">Details about A246031 and A246032</a>
%H A246031 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, 2015; see also the <a href="http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/CAcount.html">Accompanying Maple Package</a>.
%H A246031 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, 2015.
%H A246031 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 A246031 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, 2015
%H A246031 <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>
%F A246031 This is the Run Length Transform of A246032 (see Comments).
%e A246031 The entries form blocks of sizes 1,1,2,4,8,...:
%e A246031 1,
%e A246031 26,
%e A246031 26, 124,
%e A246031 26, 676, 124, 1400,
%e A246031 26, 676, 676, 3224, 124, 3224, 1400, 10000,
%e A246031 26, 676, 676, 3224, 676, 17576, 3224, 36400, 124, 3224, 3224, 15376, 1400, 36400, 10000, 89504,
%e A246031 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
%e A246031 ...
%e A246031 From _Omar E. Pol_, Mar 19 2015: (Start)
%e A246031 Also, the sequence can be written as an irregular tetrahedron T(s,r,k) as shown below:
%e A246031 1;
%e A246031 ..
%e A246031 26;
%e A246031 ...
%e A246031 26;
%e A246031 124;
%e A246031 ..........
%e A246031 26,   676;
%e A246031 124;
%e A246031 1400;
%e A246031 .....................
%e A246031 26,   676, 676, 3224;
%e A246031 124,  3224;
%e A246031 1400;
%e A246031 10000;
%e A246031 ............................................
%e A246031 26,   676,  676, 3224, 676,17576,3224,36400;
%e A246031 124,  3224, 3224, 15376;
%e A246031 1400, 36400;
%e A246031 10000;
%e A246031 89504;
%e A246031 ..........................................................................................
%e A246031 26,   676,  676, 3224, 676,17576,3224,36400,676,17576,17576,83824,3224,83824,36400,260000;
%e A246031 124,  3224, 3224, 15376, 3224, 83824, 15376, 173600;
%e A246031 1400, 36400, 36400, 173600;
%e A246031 10000, 260000;
%e A246031 89504;
%e A246031 707008;
%e A246031 ...
%e A246031 Apart from the initial 1, we have that T(s,r,k) = T(s+1,r,k).
%e A246031 (End)
%p A246031 # This is a very inefficient program!
%p A246031 f:=expand((1+x+x^2)*(1+y+y^2)*(1+z+z^2))-x*y*z;
%p A246031 g:=n->expand(f^n) mod 2;
%p A246031 h:=n->subs({x=1,y=1,z=1},g(n));
%p A246031 [seq(h(n),n=0..30)];
%p A246031 # Better program from _Roman Pearce_, Feb 18 2015:
%p A246031 f := Expand((1+x+x^2)*(1+y+y^2)*(1+z+z^2)-x*y*z) mod 2:
%p A246031 p := 1;
%p A246031 for i from 1 to 100 do
%p A246031   p := Expand(p*f) mod 2;
%p A246031   lprint(nops(p));
%p A246031 end do:
%t A246031 f = (1 + x + x^2)*(1 + y + y^2)*(1 + z + z^2) - x*y*z;
%t A246031 p = 1; Print[1];
%t A246031 Join[{1}, Table[p = Expand[p*f] // PolynomialMod[#, 2]&; Lp = Length[p]; Print[Lp]; Lp, 100]] (* _Jean-François Alcover_, Jan 17 2018 *)
%o A246031 (Magma)
%o A246031 P<x,y,z> := PolynomialRing(GF(2),3);
%o A246031 f := (1+x+x^2)*(1+y+y^2)*(1+z+z^2)-x*y*z;
%o A246031 p := 1;
%o A246031 for i := 1 to 100 do
%o A246031   p := p*f;
%o A246031   print(#Terms(p));
%o A246031 end for; // _Roman Pearce_, Feb 18 2015
%Y A246031 A 3-D analog of A160239 (2-D) and A255477 (4-D). Cf. A246032.
%K A246031 nonn
%O A246031 0,2
%A A246031 _N. J. A. Sloane_, Aug 16 2014; corrected Aug 21 2014