login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A160239 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. 32

%I

%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 step 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 <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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 18 07:01 EST 2018. Contains 317279 sequences. (Running on oeis4.)