|
%I #200 Jan 14 2024 07:19:16
%S 1,8,8,24,8,64,24,112,8,64,64,192,24,192,112,416,8,64,64,192,64,512,
%T 192,896,24,192,192,576,112,896,416,1728,8,64,64,192,64,512,192,896,
%U 64,512,512,1536,192,1536,896,3328,24,192,192,576,192,1536,576,2688,112,896,896,2688,416,3328,1728,6784
%N Number of "ON" cells in a 2-dimensional cellular automaton ("Fredkin's Replicator") evolving according to the rule that a cell is ON in a given generation if and only if there was an odd number of ON cells among the eight nearest neighbors in the preceding generation, starting with one ON cell.
%C This is the odd-rule cellular automaton defined by OddRule 757 (see Ekhad-Sloane-Zeilberger "Odd-Rule Cellular Automata on the Square Grid" link). - _N. J. A. Sloane_, Feb 25 2015
%C The partial sums are in A245542, in which the structure also looks like an irregular stepped pyramid. - _Omar E. Pol_, Jan 29 2015
%H N. J. A. Sloane, <a href="/A160239/b160239.txt">Table of n, a(n) for n = 0..10000</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 [math.CO], 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 [math.CO], 2015.
%H Charles R Greathouse IV, <a href="/A160239/a160239.pdf">Compact illustration of generations 0..17</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 [math.CO], 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="/A160239/a160239_1.pdf">Enlarged illustration of first 16 generations (pdf).</a>
%H N. J. A. Sloane, <a href="/A160239/a160239.png">Illustration for a(15) = 416 (png).</a>
%H N. J. A. Sloane, <a href="/A160239/a160239_2.pdf">Illustration for a(15) = 416 (pdf).</a>
%H N. J. A. Sloane, <a href="/A160239/a160239_1.png">Illustration for a(31) = 1728.</a>
%H N. J. A. Sloane, <a href="/A160239/a160239_4.png">Illustration for a(63) = 6784.</a>
%H N. J. A. Sloane, <a href="/A160239/a160239_1.tiff">Illustration for a(127) = 27392 (tiff).</a>
%H N. J. A. Sloane, <a href="/A160239/a160239_6.png">Illustration for a(127) = 27392 (png).</a>
%H N. J. A. Sloane, <a href="/wiki/Catalog_of_Toothpick_and_CA_Sequences_in_OEIS">Catalog of Toothpick and Cellular Automata Sequences in the OEIS</a>
%H Alexander Yu. Vlasov, <a href="https://arxiv.org/abs/2312.13034">Modelling reliability of reversible circuits with 2D second-order cellular automata</a>, arXiv:2312.13034 [nlin.CG], 2023. See page 13.
%H <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>
%F a(0) = 1; a(2t)=a(t), a(4t+1)=8*a(t), a(4t+3)=2*a(2t+1)+8*a(t) for t >= 0. (Conjectured by _Hrothgar_, Jul 11 2014; proved by _N. J. A. Sloane_, Oct 04 2014.)
%F For n >= 2, a(n) = 8^r * Product_{lengths i of runs of 1 in binary expansion of n} R(i), where r is the number of runs of 1 in the binary expansion of n and R(i) = A083424(i-1) = (5*4^(i-1)+(-2)^(i-1))/6. Note that row i of the table in A245562 lists the lengths of runs of 1 in binary expansion of i. Example: n=7 = 111 in binary, so r=1, i=3, R(3) = A083424(2) = 14, and so a(7) = 8^1*14 = 112. That is, this sequence is the Run Length Transform of A246030. - _N. J. A. Sloane_, Oct 04 2014
%F 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). - _N. J. A. Sloane_, Aug 25 2014
%e From _Omar E. Pol_, Jul 22 2014 (Start):
%e Written as an irregular triangle in which row lengths is A011782 the sequence begins:
%e 1;
%e 8;
%e 8, 24;
%e 8, 64, 24, 112;
%e 8, 64, 64, 192, 24, 192, 112, 416;
%e 8, 64, 64, 192, 64, 512, 192, 896, 24, 192, 192, 576, 112, 896, 416, 1728;
%e 8, 64, 64, 192, 64, 512, 192, 896, 64, 512, 512, 1536, 192, 1536, 896, 3328, 24, 192, 192, 576, 192, 1536, 576, 2688, 112, 896, 896, 2688, 416, 3328, 1728, 6784;
%e (End)
%e Right border gives A246030. - _Omar E. Pol_, Jan 29 2015 [This is simply a restatement of the theorem that this sequence is the Run Length Transform of A246030. - _N. J. A. Sloane_, Jan 29 2015]
%e .
%e From _Omar E. Pol_, Mar 18 2015 (Start):
%e Also, the sequence can be written as an irregular tetrahedron as shown below:
%e 1;
%e ..
%e 8;
%e ..
%e 8;
%e 24;
%e .........
%e 8, 64;
%e 24;
%e 112;
%e ...................
%e 8, 64, 64, 192;
%e 24, 192;
%e 112;
%e 416;
%e .....................................
%e 8, 64, 64, 192, 64, 512,192, 896;
%e 24, 192, 192, 576;
%e 112, 896;
%e 416;
%e 1728;
%e .......................................................................
%e 8, 64, 64, 192, 64, 512,192, 896,64,512,512,1536,192,1536,896,3328;
%e 24, 192, 192, 576,192,1536,576,2688;
%e 112, 896, 896,2688;
%e 416,3328;
%e 1728;
%e 6784;
%e ...
%e Apart from the initial 1, we have that T(s,r,k) = T(s+1,r,k). On the other hand, it appears that the configuration of ON cells of T(s,r,k) is also the central part of the configuration of ON cells of T(s+1,r+1,k).
%e (End)
%p # From _N. J. A. Sloane_, Jan 19 2015:
%p f:=proc(n) option remember;
%p if n=0 then RETURN(1);
%p elif n mod 2 = 0 then RETURN(f(n/2))
%p elif n mod 4 = 1 then RETURN(8*f((n-1)/4))
%p else RETURN(f(n-2)+2*f((n-1)/2)); fi;
%p end;
%p [seq(f(n),n=0..255)];
%t A160239[n_] :=
%t CellularAutomaton[{52428, {2, {{2, 2, 2}, {2, 1, 2}, {2, 2, 2}}}, {1, 1}}, {{{1}}, 0}, {{n}}][[1]] // Total@*Total (* _Charles R Greathouse IV_, Aug 21 2014 *)
%t ArrayPlot /@ CellularAutomaton[{52428, {2, {{2, 2, 2}, {2, 1, 2}, {2, 2, 2}}}, {1, 1}}, {{{1}}, 0}, 30] (* _Charles R Greathouse IV_, Aug 21 2014 *)
%o (Haskell)
%o import Data.List (transpose)
%o a160239 n = a160239_list !! n
%o a160239_list = 1 : (concat $
%o transpose [a8, hs, zipWith (+) (map (* 2) hs) a8, tail a160239_list])
%o where a8 = map (* 8) a160239_list;
%o hs = h a160239_list; h (_:x:xs) = x : h xs
%o -- _Reinhard Zumkeller_, Feb 13 2015
%o (PARI) A160239=[];a(n)={if(n>#A160239,A160239=concat(A160239,vector(n-#A160239)),n||return(1);A160239[n]&&return(A160239[n]));A160239[n]=if(bittest(n,0),if(bittest(n,1),a(n-2)+2*a(n\2),a(n\4)*8),a(n\2))} \\ _M. F. Hasler_, May 10 2016
%Y Cf. A122108, A147562, A164032, A245180 (gives a(n)/8, n>=2).
%Y Cf. also A245542 (Partial sums), A245543, A083424, A245562, A246030, A254731 (an "even-rule" version).
%K nonn,nice
%O 0,2
%A _John W. Layman_, May 05 2009
%E Offset changed to 1 by _Hrothgar_, Jul 11 2014
%E Offset reverted to 0 by _N. J. A. Sloane_, Jan 19 2015
|
