This site is supported by donations to The OEIS Foundation.
Index to Elementary Cellular Automata
This is the latest Index to Elementary Cellular Automata
Sequences in the OEIS related to Elementary Cellular Automata are tabulated here.
Contents
Introduction
There are 256 possible Elementary Cellular Automata. Wolfram's numbering scheme identifies these by rule numbers from 0 to 255. See "A New Kind of Science" by Stephen Wolfram, pages 51-60 or the Eric Weisstein's "World of Mathematics" links below. The sequences in the OEIS generally represent a one-dimensional cellular automata (CA) as a growing triangle whose rows represent successive generations or stages. These rows grow as 2n+1 where n=0 specifies the initial state of a single black (ON) cell. Black (ON) cells are translated as ones and white (OFF) cells as zeroes. For example, the first five rows of the CA generated by Rule 1 are:
1
0 0 0
0 0 1 0 0
1 1 0 0 0 1 1
0 0 0 0 1 0 0 0 0
Certain attributes of these CA can be interpreted as integer sequences. These are tabulated in the tables below. The most basic attribute is the binary interpretation of the entire generated triangle itself. For example, the sequence generated by Rule 1 begins: 1,0,0,0,0,0,1,0,0,1,1,0,0,0,1,1,0,0,0,0,1,0,0,0,0. Another sequence interprets each row as a binary number. The sequence generated by Rule 1 for this attribute begins: 1,0,100,1100011,10000. These binary numbers, when converted to decimal yields another sequence. For Rule 1, the sequence begins: 1,0,4,99,16. The middle column of the triangle can also be interpreted as a binary sequence of ones and zeroes. For Rule 1, the sequence begins: 1,0,1,0,1. This middle column can also be represented as a sequence of binary numbers as the triangle grows. For Rule 1, this sequence begins: 1,10,101,1010,10101. Again, the decimal equivalent produces another sequence. For Rule 1, this sequence begins: 1,2,5,10,21. Another sequence is the number of black (ON) cells at each generation of the CA. For Rule 1, this sequence begins: 1,0,1,4,1. Yet another sequence is obtained by counting the total number of black (ON) cells through n generations. For Rule 1, this sequence begins: 1,1,2,6,7. Counting the white (ON) cells instead of the black cells yields two more sequences. For Rule 1, these two sequences are: 0,3,4,3,8 and 0,3,7,10,18. Other sequences are defined by the left and right diagonals. The left diagonal for Rule 1 begins: 1,0,0,1,0,1,0,1. The right diagonal in this case is the same. But not all rules produce a symmetric triangle. Similar to the middle column sequences, a binary and decimal interpretation of the left and right diagonals produce yet other sequences. As it turns out, there are only six different sequences for each of the left and right diagonals. These sequences are tabulated in the tables below titled as "Left Diagonal Sequences" and "Right Diagonal Sequences".
Given the number of black cells in a row, Black(n), and the fact that there are 2n+1 cells in a row, certain sequences can be computed from others. Black() is the partial sum of Black(n) and Black(n) is the first difference of Black(). Also, White(n) = 2n + 1 - Black(n). Similarly White() is the partial sum of White(n) and White(n) is the first difference of White(). Also, White(n) = 2n + 1 - Black(n) and White() = (n+1)^2 - Black(). Thus, if any of these four sequences are known, the other three can be calculated. And, if two or more CA generate an identical sequence for one of these, then all four must be identical for all of those CA.
Certain CA definitions (or rules), while different, generate identical histories. For example, rules 1 and 33 while having different specifications generate identical triangles. See the section below on "Equivalent Elementary Cellular Automata". Sequences generated by the middle column using various rules may also be identical. For example rules 60, 102, 110, 150 and 188 each show all black cells in the middle column. For another example, rules 57, 99, 131 and 145 all generate the same middle column. See "Equivalencies Based on the Middle Column " below for these sequences. Similarly, different rules can generate identical Black cell counts in each row. For example, rules 28, 70, 156 and 198 all generate the same Black(n) sequence. See "Equivalencies Based on Number of ON (Black) Cells in a Row" below for these sequences.
Often a well known sequence like A005408 (The Odd Integers) comes very close to the CA generated sequence. The first term, usually a zero, may be missing or substituted. Or an extra first term will be present. In these cases the well known sequence is used in the tables below and the sequence is indicated with an asterisk. For example, the binary sequence of the middle column as the triangle grows for Rule 1 is: 1,10,101,1010,10101,... . A056830(n) = 0,1,10,101,1010,10101,... . The CA sequence is A056830 ignoring the the first term of A056830.
Certain CA are mirror images of another. Some are near complements of each other, where black (ON) cells are swapped with white (OFF) cells. Still others are complements of the mirror image. Wolfram states that Rule 135 is the complement of Rule 30. This is not precisely true, as both start with a single black (ON) cell at stage 0. But if you compare Rule 135 starting at stage 1 ignoring the leftmost two cells, it matches the complement of Rule 30 starting at stage 0. This type of near complement is seen in rules 135 and 149 among others.
1 1
1 1 0 1 1 1 0
1 1 0 0 0 1 1 0 0 1 0 0 0
1 1 0 0 1 1 0 1 1 0 1 1 1 1 0 0 1 1 0
1 1 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0
1 1 0 0 1 1 0 1 1 1 0 1 1 0 1 1 1 1 0 1 1 1 0 0 1 1 0 1 1 1 0
Rule 135 Rule 30 Truncated Rule 135
Sequences in the OEIS Related to Elementary Cellular Automata
Column headings in the table below: Rule Wolfram's Rule Number Triangle A-number of sequence listing the CA stages (iterations, generations) in a triangular table Stages(B) A-number of sequence listing each CA stage as a binary number Stages(D) A-number of sequence listing each CA stage as a decimal number Middle A-number of sequence listing the middle column of the CA stages in a binary representation Middle(B) A-number of sequence listing the middle column at each stage as a binary number Middle(D) A-number of sequence listing the middle column at each stage as a decimal number Black(n) A-number of sequence listing the number of black (ON) cells at each stage Black() A-number of sequence listing the total number of black (ON) cells through stage n White(n) A-number of sequence listing the number of white (OFF) cells at each stage White() A-number of sequence listing the total number of white (OFF) cells through stage n Other A-number of sequence listing other attributes of the CA (an asterisk, "*", in an A-number indicates a near match)
Left Diagonal Sequences
Column headings in the table below:
Rule Wolfram's Rule Number
L_Diag A-number of sequence listing the left diagonal in a binary representation
L_Diag(B) A-number of sequence listing the left diagonal at each stage as a binary number
L_Diag(D) A-number of sequence listing the left diagonal at each stage as a decimal number
(an asterisk, "*", in an A-number indicates a near match)
| Rule | L_Diag | L_Diag(B) | L_Diag(D) |
|---|---|---|---|
| 0,4,8,12,16,20,24,28,32,36,40,44,48,52,56,60,64,68,72,76,80,84,88,92,96,100,104,108, 112,116,120,124,128,129,132,133,136,137,140,141,144,145,148,149,152,153,156,157,160,161,164,165, 168,169,172,173,176,177,180,181,184,185,188,189,192,196,200,204,208,212,216,220,224,228,232,236, 240,244,248,252 | A000007 | A011557 | A000079 |
| 1,5,9,13,17,21,25,29,33,37,41,45,49,53,57,61 | A266070 | A266071 | A081253* |
| 2,6,10,14,18,22,26,30,34,38,42,46,50,54,58,62,66,70,74,78,82,86,90,94,98,102,106,110,114,118,122, 126,130,131,134,135,138,139,142,143,146,147,150,151,154,155,158,159,162,163,166,167,170,171,174, 175,178,179,182,183,186,187,190,191,194,195,198,199,202,203,206,207,210,211,214,215,218,219,222, 223,226,227,230,231,234,235,238,239,242,243,246,247,250,251,254,255 | A000012 | A002275* | A168604 |
| 3,7,11,15,19,23,27,31,35,39,43,47,51,55,59,63,67,71,75,79,83,87, 91,95,99,103,107,111,115,119,123, 127 | A135528 | A266219 | A081254 |
| 65,69,73,77,81,85,89,93,97,101,105,109,113,117,121,125 | A059841 | A056830* | A000975* |
| 193,197,201,205,209,213,217,221,225,229,233,237,241,245,249,253 | A060576 | A267623 | A083329 |
Right Diagonal Sequences
Column headings in the table below:
Rule Wolfram's Rule Number
R_Diag A-number of sequence listing the right diagonal in a binary representation
R_Diag(B) A-number of sequence listing the right diagonal at each stage as a binary number
R_Diag(D) A-number of sequence listing the right diagonal at each stage as a decimal number
(an asterisk, "*", in an A-number indicates a near match)
| Rule | R_Diag | R_Diag(B) | R_Diag(D) |
|---|---|---|---|
| 0,2,4,6,8,10,12,14,32,34,36,38,40,42,44,46,64,66,68,70,72,74,76,78,96,98,100,102,104,106, 108,110,128,129,130,131,132,133,134,135,136,138,140,142,160,161,162,163,164,165,166,167,168, 170,172,174,192,193,194,195,196,197,198,199,200,202,204,206,224,225,226,227,228,229,230,231, 232,234,236,238 | A000007 | A011557 | A000079 |
| 1,3,5,7,33,35,37,39,65,67,69,71,97,99,101,103 | A266070 | A266071 | A081253* |
| 9,11,13,15,41,43,45,47,73,75,77,79,105,107,109,111 | A059841 | A056830* | A000975* |
| 16,18,20,22,24,26,28,30,48,50,52,54,56,58,60,62,80,82,84,86,88,90,92,94,112,114,116,118,120, 122,124,126,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,176,177,178,179, 180,181,182,183,184,185,186,187,188,189,190,191,208,209,210,211,212,213,214,215,216,217,218, 219,220,221,222,223,240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255 | A000012 | A002275* | A168604 |
| 17,19,21,23,25,27,29,31,49,51,53,55,57,59,61,63,81,83,85,87,89,91,93,95,113,115,117,119,121,123,125,127 | A135528 | A266219 | A081254 |
| 137,139,141,143,169,171,173,175,201,203,205,207,233,235,237,239 | A060576 | A267623 | A083329 |
Mathematica Program To Generate the Sequences Above
rule=73; rows=20;
ca=CellularAutomaton[rule,{{1},0},rows-1,{All,All}]; (* Start with single black cell *)
catri=Table[Take[ca[ [k] ],{rows-k+1,rows+k-1}],{k,1,rows}]; (* Truncated list of each row *)
Print["CA Evolution Diagram"];
For[i=1, i≤rows, i++, str=StringTake[" ",rows-i]; str = str <> str; (* Create padding for particular row *)
For[j=1, j<=Length[catri[ [i] ]], j++, str = str <> If[catri[ [i] ][ [j] ] == 0, "0 ", "1 "]];
Print[str]];
Print["Triangle Representation of CA"]; Flatten[catri]
Print["Binary Representation of Rows"]; Table[FromDigits[catri[ [k] ]],{k,1,rows}]
Print["Decimal Representation of Rows"]; Table[FromDigits[catri[ [k] ],2],{k,1,rows}]
Print["Middle Column"]; mc=Table[catri[ [k] ][ [k] ],{k,1,rows}] (* Keep only middle cell from each row *)
Print["Binary Representation of Middle Column"]; Table[FromDigits[Take[mc,k]],{k,1,rows}]
Print["Decimal Representation of Middle Column"]; Table[FromDigits[Take[mc,k],2],{k,1,rows}]
Print["Number of Black cells in stage n"]; nbc=Table[Total[catri[ [k] ]],{k,1,rows}]
Print["Number of Black cells through stage n"]; Table[Total[Take[nbc,k]],{k,1,rows}]
Print["Number of White cells in stage n"]; nwc=Table[Length[catri[ [k] ]]-nbc[ [k] ],{k,1,rows}]
Print["Number of White cells through stage n"]; Table[Total[Take[nwc,k]],{k,1,rows}]
Print["Left Diagonal"]; ld=Table[catri[ [k] ][ [1] ], {k,1,rows}] (* Keep only first cell from each row *)
Print["Binary Representation of Left Diagonal"]; Table[FromDigits[Take[ld,k]], {k,1,rows}]
Print["Decimal Representation of Left Diagonal"]; Table[FromDigits[Take[ld,k],2], {k,1,rows}]
Print["Right Diagonal"]; rd=Table[catri[k][2*(k-1)+1], {k,1,rows}] (* Keep only last cell from each row *)
Print["Binary Representation of Right Diagonal"]; Table[FromDigits[Take[rd,k]], {k,1,rows}]
Print["Decimal Representation of Right Diagonal"]; Table[FromDigits[Take[rd,k],2], {k,1,rows}]
CA Evolution Diagram
1
0 0 0
1 0 1 0 1
0 0 0 0 0 0 0
1 0 1 1 1 1 1 0 1
0 0 0 1 0 0 0 1 0 0 0
1 0 1 0 0 0 1 0 0 0 1 0 1
0 0 0 0 0 1 0 0 0 1 0 0 0 0 0
1 0 1 1 1 0 0 0 1 0 0 0 1 1 1 0 1
0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0
1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1
0 0 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 0
1 0 1 1 1 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 1
0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0
1 0 1 0 0 0 0 0 1 0 0 0 1 1 1 1 1 0 0 0 1 0 0 0 0 0 1 0 1
0 0 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 1 1 0 0 0 0 0
1 0 1 1 1 0 1 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 1 1 1 0 1
0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0
1 0 1 0 0 0 0 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 0 0 0 0 1 0 1
0 0 0 0 0 1 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 1 0 0 0 0 0
Triangle Representation of CA
{1,0,0,0,1,0,1,0,1,0,0,0,0,0,0,0,1,0,1,1,1,1,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0, 1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,1,1,0,0,0,1,0,0,0,1,1,1,0,1,0,0,0,1,0,1,0,1,0,0,0, 1,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,1,1,1,1,1,0,0,0,1,1,1,1, 1,0,0,0,0,0,1,0,1,1,1,0,1,0,0,0,1,0,1,0,1,0,0,0,1,0,1,1,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0, 0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,1,1,1,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0, 1,1,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,1,1,0,0,0,0,0,1,0,1,1,1,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0, 0,0,1,0,1,0,1,0,1,1,1,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,1,1,1,0,0,0,1,1,1,0,0,0,0,0,0,0,1,0,1,0, 0,0,1,0,1,0,0,0,0,0,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,1,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,1, 1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,1,1,1,0,0,0,0,0}
Binary Representation of Rows
{1,0,10101,0,101111101,10001000,1010001000101,1000100000,10111000100011101,1010100010101000, 101000000010000000101,111110001111100000,1011101000101010001011101,101000100000001000101000, 10100000100011111000100000101,11100010100010100011100000,101110101010000010000010101011101, 10100000001110001110000000101000,1010000011111010101010101111100000101, 1110100010000000000010001011100000}
Decimal Representation of Rows
{1,0,21,0,381,136,5189,544,94493,43176,1311749,254944,24400989,10617384,336720133,59386080, 6262162781,2688081960,86425034501,15602819808}
Middle Column
{1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0}
Binary Representation of Middle Column
{1,10,101,1010,10101,101010,1010101,10101010,101010101,1010101010,10101010101,101010101010, 1010101010101,10101010101010,101010101010101,1010101010101010,10101010101010101, 101010101010101010,1010101010101010101,10101010101010101010}
Decimal Representation of Middle Column
{1,2,5,10,21,42,85,170,341,682,1365,2730,5461,10922,21845,43690,87381,174762,349525,699050}
Number of Black cells in stage n
{1,0,3,0,7,2,5,2,9,6,5,10,13,6,11,10,15,10,19,10}
Number of Black cells through stage n
{1,1,4,4,11,13,18,20,29,35,40,50,63,69,80,90,105,115,134,144}
Number of White cells in stage n
{0,3,2,7,2,9,8,13,8,13,16,13,12,21,18,21,18,25,18,29}
Number of White cells through stage n
{0,3,5,12,14,23,31,44,52,65,81,94,106,127,145,166,184,209,227,256}
Left Diagonal
{1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0}
Binary Representation of Left Diagonal
{1,10,101,1010,10101,101010,1010101,10101010,101010101,1010101010,10101010101, 101010101010,1010101010101,10101010101010,101010101010101,1010101010101010, 10101010101010101,101010101010101010,1010101010101010101,10101010101010101010}
Decimal Representation of Left Diagonal
{1,2,5,10,21,42,85,170,341,682,1365,2730,5461,10922,21845,43690,87381,174762, 349525,699050}
Right Diagonal
{1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0}
Binary Representation of Right Diagonal
{1,10,101,1010,10101,101010,1010101,10101010,101010101,1010101010,10101010101, 101010101010,1010101010101,10101010101010,101010101010101,1010101010101010, 10101010101010101,101010101010101010,1010101010101010101,10101010101010101010}
Decimal Representation of Right Diagonal
{1,2,5,10,21,42,85,170,341,682,1365,2730,5461,10922,21845,43690,87381,174762, 349525,699050}
Equivalent Elementary Cellular Automata
Rules in each of the lists below generate identical Cellular Automata histories:
{0,8,32,40,64,72,96,104,128,136,160,168,192,200,224,232}
{1,33}
{2,10,34,42,66,74,98,106,130,138,162,170,194,202,226,234}
{3,35}
{4,12,36,44,68,76,100,108,132,140,164,172,196,204,228,236}
{6,38,134,166}
{11,43}
{14,46,142,174}
{16,24,48,56,80,88,112,120,144,152,176,184,208,216,240,248}
{17,49}
{18,26,82,90,146,154,210,218}
{20,52,148,180}
{23,31,55,63,87,95,119,127}
{28,156}
{50,58,114,122,178,179,186,242,250}
{70,198}
{81,113}
{84,116,212,244}
{129,161}
{139,171}
{151,159,183,191,215,222,223,247,254,255}
{206,238}
{209,241}
{220,252}
Equivalencies Based on Number of ON (Black) Cells in a Row
Rules in each of the lists below generate identical number of ON (Black) cells in a row. And as a consequence, the four related sequences are identical.
{2,4,10,12,16,24,34,36,42,44,48,56,66,68,74,76,80,88,98,100,106,108,112,120,130,132, 138,140,144,152,162,164,170,172,176,184,194,196,202,204,208,216,226,228,234,236,240,248}
{3,5,17,35,49}
{6,20,38,52,134,148,166,180}
{7,19,21}
{9,65}
{11,43,81,113}
{13,57,69,99}
{14,46,84,116,142,174,212,244}
{15,27,29,39,51,53,71,83,85}
{18,26,60,82,90,102,146,154,210,218}
{22}
{23,31,55,63,87,95,119,127}
{25,67}
{28,70,156,198}
{30,86}
{37}
{41,97}
{45,101}
{47,117}
{50,58,114,122,178,179,186,206,220,238,242,250,252}
{54}
{59,115}
{61,103}
{62,118}
{73}
{75,89}
{77}
{78,92}
{79,93,147}
{91}
{94}
{105}
{107,121}
{109}
{110,124}
{111,125}
{123}
{126}
{129,161}
{131,145}
{133}
{135,149}
{137,193}
{139,171,185,205,209,227,241}
{141,197}
{143,213}
{150}
{151,159,183,191,215,222,223,247,254,255}
{153,165,195}
{155,211}
{157,199}
{158,214}
{163,177}
{167,181}
{169,225}
{173,203,217,229}
{175,187,189,207,219,221,231,243,245}
{182}
{188,230}
{190,246}
{201}
{233}
{235,249}
{237}
{239,251,253}
Equivalencies Based on the Middle Column
Rules in each of the lists below generate identical Middle Columns. And as a consequence, the three related sequences are identical.
{0,2,8,10,16,18,24,26,32,34,40,42,48,56,64,66,72,74,80,82,88,90,96,98,104,106,
112,120,128,130,136,138,144,146,152,153,154,160,162,168,170,176,184,192,194,
195,200,202,203,208,210,216,217,218,219,224,226,232,234,240,248}
{1,33,50,51,58,73,105,114,122,123,178,179,186,201,242,250}
{3,11,17,19,27,35,43,49,81,83,113,163,177}
{4,5,12,13,28,29,36,44,60,68,69,70,71,76,77,78,79,92,93,100,102,108,110,124, 132,133,140,141,150,151,156,157,159,164,165,172,173,182,183,188,189,191,196, 197,198,199,204,205,206,207,215,220,221,222,223,228,229,230,231,236,237,238, 239,247,252,253,254,255}
{6,14,20,22,38,46,52,84,94,116,134,142,148,166,174,180,212,244}
{7,15,21,23,31,39,47,53,55,63,85,87,95,117,119,127}
{9,65}
{25,67}
{30,86}
{37}
{41,97}
{45,101}
{54}
{57,99,131,145}
{59,115}
{61,103}
{62,118}
{75,89}
{91}
{107,121}
{109}
{111,125}
{126}
{129,161}
{135,149}
{137,193}
{139,155,171,185,209,211,227,235,241,249}
{143,213}
{147}
{158,190,214,246}
{167,181}
{169,225}
{175,245}
{187,243,251}
{233}
