A122108 -id:A122108 - cp's OEIS frontend

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.

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

Offset: 0

John W. Layman, May 05 2009

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 stepped pyramid. - Omar E. Pol, Jan 29 2015

			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)

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
Alexander Yu. Vlasov, Modelling reliability of reversible circuits with 2D second-order cellular automata, arXiv:2312.13034 [nlin.CG], 2023. See page 13.
Index entries for sequences related to cellular automata

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

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

# 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)];

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

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

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

Offset changed to 1 by Hrothgar, Jul 11 2014

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

A164982 Number of ON cells after n generations of the 2D cellular automaton described in the comments.

Original entry on oeis.org

1, 3, 4, 12, 7, 21, 16, 40, 22, 42, 34, 67, 52, 85, 70, 125, 94, 126, 102, 150, 118, 172, 177, 234, 209, 240, 238, 319, 285, 363, 378, 458, 383, 444, 404, 493, 474, 520, 529, 628, 583, 602, 622, 727, 664, 816, 835, 948, 873, 926, 952, 1065, 1010, 1090, 1187

Offset: 1

John W. Layman, Sep 03 2009

nonn

The cells are the squares of the standard square grid. All cells are initially OFF and one cell is turned ON at generation 1. At subsequent generations a cell is ON if and only if (1) exactly one of neighbors NW, NE, and S was ON, or (2) all three of cells N, SW, and SE were ON in the previous generation. (The 9-cell Moore neighborhood is labeled {{NW,N,NE},{W,C,E},{SW,S,SE}}).

John W. Layman, Graphs of the automaton for generations 1-20 [From _John W. Layman_, Sep 14 2009]
Index entries for sequences related to cellular automata

Cf. A048883, A072272, A122108, A160410, A247002.

RasterGraphics[state_?MatrixQ, colors_Integer : 2, opts___] := Graphics[Raster[Reverse[1 - state/(colors - 1)]], AspectRatio -> (AspectRatio /. {opts} /. AspectRatio -> Automatic), Frame -> True, FrameTicks -> None, GridLines -> None];
rule=61986;
Show[GraphicsArray[Map[RasterGraphics, CellularAutomaton[{rule, {2, {{1, 4, 1}, {0, 0, 0}, {4, 1, 4}}}, {1, 1}}, {{{1}}, 0}, 4, -5]]]];
ca = CellularAutomaton[{rule, {2, {{1, 4, 1}, {0, 0, 0}, {4, 1, 4}}}, {1, 1}}, {{{1}}, 0}, 99, -100];
Table[Total[ca[[i]], 2], {i, 1, 100}]

A269711 Number of active (ON, black) cells in n-th stage of growth of two-dimensional cellular automaton defined by "Rule 20", based on the 5-celled von Neumann neighborhood.

Original entry on oeis.org

1, 4, 8, 12, 20, 24, 44, 28, 52, 56, 104, 56, 104, 112, 212, 60, 116, 120, 232, 120, 232, 240, 464, 120, 232, 240, 464, 240, 464, 480, 932, 124, 244, 248, 488, 248, 488, 496, 976, 248, 488, 496, 976, 496, 976, 992, 1952, 248, 488, 496, 976, 496, 976, 992

Offset: 0

Robert Price, Mar 04 2016

Initialized with a single black (ON) cell at stage zero.
Rules 28, 52, 60, 148, 156, 180, 188, 532, 540, 564, 572, 660, 668, 692 and 700 also generate this sequence.
Apparently a duplicate of A122108. - R. J. Mathar, Mar 09 2016

S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 170.

Robert Price, Table of n, a(n) for n = 0..300
Robert Price, Diagrams of first 20 stages.
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015.
Eric Weisstein's World of Mathematics, Elementary Cellular Automaton
S. Wolfram, A New Kind of Science
Index entries for sequences related to cellular automata
Index to 2D 5-Neighbor Cellular Automata
Index to Elementary Cellular Automata

rule=20; stages=300;
ca=CellularAutomaton[{rule,{2,{{0,2,0},{2,1,2},{0,2,0}}},{1,1}},{{{1}},0},stages]; (* Start with single black cell *)
Map[Function[Apply[Plus,Flatten[#1]]],ca] (* Count ON cells at each stage *)

A165345 Number of ON cells after n generations of the 2D cellular automaton described in the comments.

Original entry on oeis.org

1, 5, 9, 25, 29, 41, 53, 105, 113, 129, 141, 193, 205, 241, 285, 433, 453, 481, 497, 553, 569, 609, 653, 801, 829, 881, 917, 1073, 1109, 1217, 1349, 1793, 1845, 1905, 1933, 2001, 2029, 2081, 2129, 2281, 2313, 2369, 2409, 2569, 2609, 2721, 2853, 3297, 3357

Offset: 1

John W. Layman, Sep 15 2009, Sep 16 2009

nonn

The cells are the squares of the standard square grid. All cells are initially OFF and one cell is turned ON at generation 1. At subsequent generations a cell is ON if and only if (1) it was ON, or (2) exactly one of the four nearest side neighbors was ON, or (3) exactly three of the four nearest corner neighbors were ON, in the previous generation

The equivalent Mathematica automaton is obtained with neighborhood weights {{10,2,10},{2,1,2},{10,2,10}}, rule number 755364134566574, and initial configuration {{1}} (see code).

Graphs of the automaton for generations 1-20. [From _John W. Layman_, Sep 15 2009]

Cf. A048883, A072272, A122108, A160410, A164982.

RasterGraphics[state_?MatrixQ, colors_Integer:2, opts___]:= Graphics[Raster[ Reverse[1 -state/(colors -1)]],AspectRatio-> (AspectRatio /.{opts} /.AspectRatio-> Automatic),Frame-> True, FrameTicks ->none,GridLines->none]; wt = {{10, 2, 10}, {2, 1, 2}, {10, 2, 10}}; rule=755364134566574; init = {{1}}; Show[GraphicsArray[ Map[RasterGraphics, CellularAutomaton[{rule, {2, wt}, {1, 1}}, {init, 0}, 9, -10]]]]; ca = CellularAutomaton[{rule, {2, wt}, {1, 1}}, {init, 0}, 99, -100]; a = Table[Total[ca[[i]], 2], {i, 1, 100}]

A164032 Number of "ON" cells in a certain 2-dimensional cellular automaton.

Original entry on oeis.org

1, 9, 4, 36, 4, 36, 16, 144, 4, 36, 16, 144, 16, 144, 64, 576, 4, 36, 16, 144, 16, 144, 64, 576, 16, 144, 64, 576, 64, 576, 256, 2304, 4, 36, 16, 144, 16, 144, 64, 576, 16, 144, 64, 576, 64, 576, 256, 2304, 16, 144, 64, 576, 64, 576, 256, 2304, 64, 576, 256, 2304, 256

Offset: 1

John W. Layman, Aug 08 2009

nonn

This automaton starts with one ON cell and evolves according to the rule that a cell is ON in a given generation if and only if the number of ON cells, among the cell itself and its eight nearest neighbors, was exactly one in the preceding generation.

			Can be arranged into blocks of length 2^k:
1,
9,
4, 36,
4, 36, 16, 144,
4, 36, 16, 144, 16, 144, 64, 576,
4, 36, 16, 144, 16, 144, 64, 576, 16, 144, 64, 576, 64, 576, 256, 2304,
4, 36, 16, 144, 16, 144, 64, 576, 16, 144, 64, 576, 64, 576, 256, 2304, 16, 144, 64, 576, 64, 576, 256, 2304, 64, 576, 256, 2304, 256, ...
...

David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.], which is also available at arXiv:1004.3036v2
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Index entries for sequences related to cellular automata

Cf. A000120, A048883, A079315, A122108, A160239, A002063 (last entry in each block)

wt[i_] := DigitCount[i, 2, 1];
a[n_] := If[OddQ[n], 1, 9] 4^wt[Floor[(n-1)/2]];
Array[a, 61] (* Jean-François Alcover, Oct 08 2018, after N. J. A. Sloane *)

a(n) = 4^hammingweight((n-1)\2) * if(n%2, 1, 9); \\ Michel Marcus, Oct 08 2018

It appears that this is the self-generating sequence defined by the following process: start with s={1,9} and repeatedly extend by concatenating s with 4*s, thus obtaining {1,9} -> {1,9,4,36} -> {1,9,4,36,4,36,16,144},... , etc.
Also, it appears that if n=2^k+j, with n>2 and 1<=j<=2^k, then a(n)=4a(j), with a(1)=1, a(2)=9.
From N. J. A. Sloane, Jul 21 2014: (Start)
Both of these assertions are not difficult to prove. At generation G = 2^k (k>=1) the ON cells are bounded by a box of edge 2G-1, and in that box there are (G/2)^2 3X3 blocks each containing 9 ON cells (separated by rows of OFF cells of width 1), so a total of a(2^k) = 9*2^(2k-2) ON cells (cf. A002063).
This box is full (more precisely, every cell in it has more than one ON neighbor), and at generation G+1 we have just 4 ON cells which are now at the corners of a box of edge 2G+1. Until the next power of 2 there is no interaction between the configurations that grow at the four corners, and so a(2^k+j) = 4a(j), as conjectured.
In fact this implies an explicit formula for a(n):
a(n) = c*4^wt(floor((n-1)/2)),
where c=1 if n is odd, c=9 if n is even, and wt(i) = A000120(i) is the binary weight function. For example, if n=20, [(n-1)/2]=9 which has weight 2, so a(20) = 9*4^2 = 144. (End)

cp's OEIS Frontend

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A164982 Number of ON cells after n generations of the 2D cellular automaton described in the comments.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A269711 Number of active (ON, black) cells in n-th stage of growth of two-dimensional cellular automaton defined by "Rule 20", based on the 5-celled von Neumann neighborhood.

Views

Author

Keywords

Comments

References

Links

Programs

Mathematica

A165345 Number of ON cells after n generations of the 2D cellular automaton described in the comments.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A164032 Number of "ON" cells in a certain 2-dimensional cellular automaton.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula