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
1, 8, 8, 24, 8, 64, 24, 112, 8, 64, 64, 192, 24, 192, 112, 416, 8, 64, 64, 192, 64, 512, 192, 896, 24, 192, 192, 576, 112, 896, 416, 1728, 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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

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

The partial sums are in A245542, in which the structure also looks like an irregular step pyramid. - Omar E. Pol, Jan 29 2015

LINKS

N. J. A. Sloane, Table of n, a(n) for n = 0..10000

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 [math.CO], 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 [math.CO], 2015.

Charles R Greathouse IV, Compact illustration of generations 0..17

N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 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, Enlarged illustration of first 16 generations (pdf).

N. J. A. Sloane, Illustration for a(15) = 416 (png).

N. J. A. Sloane, Illustration for a(15) = 416 (pdf).

N. J. A. Sloane, Illustration for a(31) = 1728.

N. J. A. Sloane, Illustration for a(63) = 6784.

N. J. A. Sloane, Illustration for a(127) = 27392 (tiff).

N. J. A. Sloane, Illustration for a(127) = 27392 (png).

N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

Index entries for sequences related to cellular automata

FORMULA

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.)

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

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

EXAMPLE

From Omar E. Pol, Jul 22 2014 (Start):

Written as an irregular triangle in which row lengths is A011782 the sequence begins:

1;

8;

8, 24;

8, 64, 24, 112;

8, 64, 64, 192, 24, 192, 112, 416;

8, 64, 64, 192, 64, 512, 192, 896, 24, 192, 192, 576, 112, 896, 416, 1728;

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;

(End)

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]

.

From Omar E. Pol, Mar 18 2015 (Start):

Also, the sequence can be written as an irregular tetrahedron as shown below:

1;

..

8;

..

8;

24;

.........

8,    64;

24;

112;

...................

8,    64,  64, 192;

24,  192;

112;

416;

.....................................

8,    64,  64, 192, 64, 512,192, 896;

24,  192, 192, 576;

112, 896;

416;

1728;

.......................................................................

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;

...

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).

(End)

MAPLE

# From N. J. A. Sloane, Jan 19 2015:

f:=proc(n) option remember;

if n=0 then RETURN(1);

elif n mod 2 = 0 then RETURN(f(n/2))

elif n mod 4 = 1 then RETURN(8*f((n-1)/4))

else RETURN(f(n-2)+2*f((n-1)/2)); fi;

end;

[seq(f(n), n=0..255)];

MATHEMATICA

A160239[n_] :=

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 *)

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 *)

PROG

(Haskell)

import Data.List (transpose)

a160239 n = a160239_list !! n

a160239_list = 1 : (concat $

   transpose [a8, hs, zipWith (+) (map (* 2) hs) a8, tail a160239_list])

   where a8 = map (* 8) a160239_list;

         hs = h a160239_list; h (_:x:xs) = x : h xs

-- Reinhard Zumkeller, Feb 13 2015

(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

CROSSREFS

Cf. A122108, A147562, A164032, A245180 (gives a(n)/8, n>=2).

Cf. also A245542 (Partial sums), A245543, A083424, A245562, A246030, A254731 (an "even-rule" version).

Sequence in context: A227107 A205382 A109049 * A211017 A037018 A246310

Adjacent sequences:  A160236 A160237 A160238 * A160240 A160241 A160242

KEYWORD

nonn,nice

AUTHOR

John W. Layman, May 05 2009

EXTENSIONS

Offset changed to 1 by Hrothgar, Jul 11 2014

Offset reverted to 0 by N. J. A. Sloane, Jan 19 2015

STATUS

approved

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 September 20 12:42 EDT 2017. Contains 292271 sequences.