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