A071036 -id:A071036 - cp's OEIS frontend

A071053 Number of ON cells at n-th generation of 1-D CA defined by Rule 150, starting with a single ON cell at generation 0.

1, 3, 3, 5, 3, 9, 5, 11, 3, 9, 9, 15, 5, 15, 11, 21, 3, 9, 9, 15, 9, 27, 15, 33, 5, 15, 15, 25, 11, 33, 21, 43, 3, 9, 9, 15, 9, 27, 15, 33, 9, 27, 27, 45, 15, 45, 33, 63, 5, 15, 15, 25, 15, 45, 25, 55, 11, 33, 33, 55, 21, 63, 43, 85, 3, 9, 9, 15, 9, 27, 15, 33, 9, 27, 27

Offset: 0

Hans Havermann, May 26 2002

Number of 1's in n-th row of triangle in A071036.
Number of odd coefficients in (x^2+x+1)^n. - Benoit Cloitre, Sep 05 2003. This result was given in Wolfram (1983). - N. J. A. Sloane, Feb 17 2015
This is also the odd-rule cellular automaton defined by OddRule 007 (see Ekhad-Sloane-Zeilberger "Odd-Rule Cellular Automata on the Square Grid" link). - N. J. A. Sloane, Feb 25 2015
This is the Run Length Transform of S(n) = Jacobsthal(n+2) (cf. A001045). 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, Sep 05 2014

			May be arranged into blocks of sizes 1,1,2,4,8,16,...:
1,
3,
3, 5,
3, 9, 5, 11,
3, 9, 9, 15, 5, 15, 11, 21,
3, 9, 9, 15, 9, 27, 15, 33, 5, 15, 15, 25, 11, 33, 21, 43,
3, 9, 9, 15, 9, 27, 15, 33, 9, 27, 27, 45, 15, 45, 33, 63, 5, 15, 15, 25, 15, 45, 25, 55, 11, 33, 33, 55, 21, 63, 43, 85,
3, 9, 9, 15, 9, 27, 15, 33, 9, 27, 27, ...
... - _N. J. A. Sloane_, Sep 05 2014
.
From _Omar E. Pol_, Mar 15 2015: (Start)
Apart from the initial 1, the sequence can be written also as an irregular tetrahedron T(s,r,k) = A001045(r+2) * a(k), s>=1, 1<=r<=s, 0<=k<=(A011782(s-r)-1) as shown below (see also _Joerg Arndt_'s equivalent program):
3;
..
3;
5;
.......
3,   9;
5;
11;
...............
3,   9,  9, 15;
5,  15;
11;
21;
...............................
3,   9,  9, 15,  9, 27, 15, 33;
5,  15, 15, 25;
11, 33;
21;
43;
..............................................................
3,   9,  9, 15,  9, 27, 15, 33, 9, 27, 27, 45, 15, 45, 33, 63;
5,  15, 15, 25, 15, 45, 25, 55;
11, 33, 33, 55;
21, 63;
43;
85;
...
Note that every row r is equal to A001045(r+2) times the beginning of the sequence itself, thus in 3D every column contains the same number.
(End)

S. Wolfram, A New Kind of Science, Wolfram Media, 2002; Chapter 3.

N. J. A. Sloane, Table of n, a(n) for n = 0..16383 (first 1024 terms from T. D. Noe)
Joerg Arndt, A071053 (number of odd terms in expansion of (1+x+x^2)^n), SeqFan Mailing List, Mar 09 2015.
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.
S. R. Finch, P. Sebah and Z.-Q. Bai, Odd Entries in Pascal's Trinomial Triangle, arXiv:0802.2654 [math.NT], 2008.
Janko Gravner and Alexander E. Holroyd, Percolation and Disorder-Resistance in Cellular Automata, Annals of Probability, volume 43, number 4, 2015, pages 1731-1776. Also arxiv:1304.7301 [math.PR], 2013-2015 and second author's copy. See Fig. 1.1 (left).
S. Kropf, S. Wagner, q-Quasiadditive functions, arXiv:1605.03654 [math.CO], 2016.
N. Pitsianis, P. Tsalides, G. L. Bleris, A. Thanailakis & H. C. Card, Deterministic one-dimensional cellular automata, Journal of Statistical Physics, 56(1-2), 99-112, 1989. [Discusses Rule 150]
T. Sillke and Helmut Postl, Odd trinomials: t(n) = (1+x+x^2)^n
T. Sillke and Helmut Postl, Odd trinomials: t(n) = (1+x+x^2)^n [Cached copy, with permission]
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, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015.
S. Wolfram, Statistical mechanics of cellular automata, Rev. Mod. Phys., 55 (1983), 601--644.
Index entries for sequences related to cellular automata

Cf. A038184, A118110, A071036, A001045, A253102, A020987, A246035, A245562, A087206.

a[n_] := Total[CoefficientList[(x^2 + x + 1)^n, x, Modulus -> 2]];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Aug 05 2018 *)

b(n) = { (2^n - (-1)^n) / 3; }  \\ A001045
a(n)=
{
    if ( n==0, return(1) );
    \\ Use  a( 2^k * t ) = a(t)
    n \= 2^valuation(n,2);
    if ( n==1, return(3) );  \\ Use a(2^k) == 3
    \\ now n is odd
    my ( v1 = valuation(n+1, 2) );
    \\ Use a( 2^k - 1 ) = A001045( 2 + k ):
    if ( n == 2^v1 - 1 ,  return( b( v1 + 2 ) ) );
    my( k2 = 1, k = 0 );
    while ( k2 < n,  k2 <<= 1; k+=1 );
    if ( k2 > n, k2 >>= 1; k-=1 );
    my( t = n - k2 );
    \\ here  n == 2^k + 1 where k maximal
    \\ Use the following:
    \\ a( 2^k + t ) =  3 * a(t)  if  t <= 2^(k-1)
    \\ a( 2^k + 2^(k-1) + t ) =  5 * a(t)  if  t <= 2^(k-2)
    \\ a( 2^k + 2^(k-1) + 2^(k-2) + t ) =  11* a(t)  if  t <= 2^(k-3)
    \\  ... etc. ...
    \\ a( 2^k + ... + 2^(k-s) + t ) = A001045(s+2) * a(t)  if  t <= 2^((k-1)-s)
    my ( s=1 );
    while ( 1 ,
        k2 >>= 1;
        if ( t <= k2 ,  return(  b(s+2) * a(t) ) );
        t -= k2;
        s += 1;
    );
}
\\ Joerg Arndt, Mar 15 2015, from SeqFan Mailing List, Mar 09 2015

a(n) = Product_{i in row n of A245562} A001045(i+2) [Sillke]. For example, a(11) = A001045(3)*A001045(4) = 3*5 = 15. - N. J. A. Sloane, Aug 10 2014
Floor((a(n)-1)/4) mod 2 = A020987(n). - Ralf Stephan, Mar 18 2004
a(2*n) = a(n); a(2*n+1) = a(n) + 2*a(floor(n/2)). - Peter J. Taylor, Mar 26 2020
Sum_{k = 0..2^n-1} a(k) = A087206(n). - Linhua Zou, Jun 13 2025

Entry revised by N. J. A. Sloane, Aug 13 2014

A038184 State of one-dimensional cellular automaton 'sigma' (Rule 150): 000,001,010,011,100,101,110,111 -> 0,1,1,0,1,0,0,1 at generation n, converted to a decimal number.

Original entry on oeis.org

1, 7, 21, 107, 273, 1911, 5189, 28123, 65793, 460551, 1381653, 7039851, 17829905, 124809335, 340873541, 1840690907, 4295032833, 30065229831, 90195689493, 459568513131, 1172543963409, 8207807743863, 22286925370437

Offset: 0

Antti Karttunen, Feb 15 1999

nonn

Generation n (starting from the generation 0: 1) interpreted as a binary number, but written in base 10.
Rows of the mod 2 trinomial triangle (A027907), interpreted as binary numbers: 1, 111, 10101, 1101011, ... (A118110). - Jacob A. Siehler, Aug 25 2006
See A071053 for number of ON cells. - N. J. A. Sloane, Jul 28 2014

			Bit patterns with "0" replaced by "." for visibilty [_Georg Fischer_, Dec 16 2021]:
  0:                    1
  1:                   111
  2:                  1.1.1
  3:                 11.1.11
  4:                1...1...1
  5:               111.111.111
  6:              1.1...1...1.1
  7:             11.11.111.11.11
  8:            1.......1.......1
  9:           111.....111.....111
  10:         1.1.1...1.1.1...1.1.1
  11:        11.1.11.11.1.11.11.1.11
  12:       1...1.......1.......1...1
  13:      111.111.....111.....111.111
  14:     1.1...1.1...1.1.1...1.1...1.1
  15:    11.11.11.11.11.1.11.11.11.11.11

Gheorghe Coserea, Table of n, a(n) for n = 0..200
Alan J. Macfarlane, On generating functions of some sequences of integers defined in the evolution of the cellular automaton Rule 150, Preprint 2016.
Eric Weisstein's World of Mathematics, Rule 150
Index entries for sequences related to cellular automata

Cf. A006977, A006978, A038183, A038185 (other cellular automata).
Cf. A048710, A048720, A027907, A001317, A071053.
This sequence, A071036 and A118110 are equivalent descriptions of the Rule 150 automaton.

bit_n := (x,n) -> `mod`(floor(x/(2^n)),2);
sigmagen := proc(n) option remember: if (0 = n) then (1)
else sum('((bit_n(sigmagen(n-1),i)+bit_n(sigmagen(n-1),i-1)+bit_n(sigmagen(n-1),i-2)) mod 2)*(2^i)', 'i'=0..(2*n)) fi: end:

f[n_] := Sum[2^k*Coefficient[ #, x, k], {k, 0, 2n}] & @ Expand[(1 + x + x^2)^n, Modulus -> 2] (* Jacob A. Siehler, Aug 25 2006 *)

a(n) = subst(lift(Pol(Mod([1,1,1],2),'x)^n),'x,2);
vector(23,n,a(n-1))  \\ Gheorghe Coserea, Jun 12 2016

A118110 State of one-dimensional cellular automaton 'sigma' (Rule 150): 000,001,010,011,100,101,110,111 -> 0,1,1,0,1,0,0,1 at generation n, when started with a single ON cell, regarded as a binary number.

Original entry on oeis.org

1, 111, 10101, 1101011, 100010001, 11101110111, 1010001000101, 110110111011011, 10000000100000001, 1110000011100000111, 101010001010100010101, 11010110110101101101011, 1000100000001000000010001

Offset: 0

Eric W. Weisstein, Apr 13 2006 and N. J. A. Sloane, Jul 28 2014, combined into one entry by N. J. A. Sloane, Oct 20 2015

nonn

See A038184 for decimal equivalents.

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

Eric Weisstein's World of Mathematics, Rule 150
Eric Weisstein's World of Mathematics, Elementary Cellular Automaton
S. Wolfram, A New Kind of Science
Index to Elementary Cellular Automata
Index entries for sequences related to cellular automata

This sequence, A038184 and A071036 are equivalent descriptions of the Rule 150 automaton.

See A071053 for number of ON cells.

rule = 150; rows = 20; Table[FromDigits[Table[Take[CellularAutomaton[rule, {{1}, 0}, rows-1, {All, All}][[k]], {rows-k+1, rows+k-1}], {k, 1, rows}][[k]]], {k, 1, rows}] (* Robert Price, Feb 21 2016 *)

A237120 Number of white areas in the graph of elementary cellular automaton with rule 150 at generation n.

Original entry on oeis.org

0, 0, 2, 2, 2, 2, 4, 4, 2, 2, 8, 8, 4, 4, 10, 10, 2, 2, 8, 8, 8, 8, 14, 14, 4, 4, 14, 14, 10, 10, 20, 20, 2, 2, 8, 8, 8, 8, 14, 14, 8, 8, 26, 26, 14, 14, 32, 32, 4, 4, 14, 14, 14, 14, 24, 24, 10, 10, 32, 32, 20, 20, 42, 42, 2, 2, 8, 8, 8, 8, 14, 14, 8, 8, 26, 26, 14, 14, 32, 32, 8, 8, 26, 26, 26, 26, 44, 44, 14, 14, 44, 44, 32, 32, 62, 62, 4, 4, 14, 14, 14, 14, 24, 24, 14, 14, 44

Offset: 0

Philippe Beaudoin, Feb 03 2014

nonn

a(n) is also the number of white regions on the line at generation n of rule 150.

Philippe Beaudoin, Table of n, a(n) for n = 0..999
Philippe Beaudoin, Python program for rule 30 (can be trivially modified for this sequence).
Eric Weisstein's World of Mathematics, Rule 150.

Cf. A071036 (rule 150), A237118 (rule 30), A237119 (rule 110).

A265223 Total number of OFF (white) cells after n iterations of the "Rule 150" elementary cellular automaton starting with a single ON (black) cell.

Original entry on oeis.org

0, 0, 2, 4, 10, 12, 20, 24, 38, 48, 60, 68, 88, 100, 118, 128, 158, 184, 212, 236, 268, 284, 314, 328, 372, 408, 446, 476, 522, 548, 588, 608, 670, 728, 788, 844, 908, 956, 1018, 1064, 1136, 1192, 1250, 1292, 1366, 1412, 1472, 1504, 1596, 1680, 1766, 1844

Offset: 0

Robert Price, Dec 07 2015

			From _Michael De Vlieger_, Dec 09 2015: (Start)
First 12 rows, replacing "1" with ".", ignoring "0" outside of range of 1's for better visibility of OFF cells, followed by total number of OFF cells per row and running total up to that row:
                        .                          =  0 ->   0
                      . . .                        =  0 ->   0
                    . 0 . 0 .                      =  2 ->   2
                  . . 0 . 0 . .                    =  2 ->   4
                . 0 0 0 . 0 0 0 .                  =  6 ->  10
              . . . 0 . . . 0 . . .                =  2 ->  12
            . 0 . 0 0 0 . 0 0 0 . 0 .              =  8 ->  20
          . . 0 . . 0 . . . 0 . . 0 . .            =  4 ->  24
        . 0 0 0 0 0 0 0 . 0 0 0 0 0 0 0 .          = 14 ->  38
      . . . 0 0 0 0 0 . . . 0 0 0 0 0 . . .        = 10 ->  48
    . 0 . 0 . 0 0 0 . 0 . 0 . 0 0 0 . 0 . 0 .      = 12 ->  60
  . . 0 . 0 . . 0 . . 0 . 0 . . 0 . . 0 . 0 . .    =  8 ->  68
. 0 0 0 . 0 0 0 0 0 0 0 . 0 0 0 0 0 0 0 . 0 0 0 .  = 20 ->  88
(End)

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

Robert Price, Table of n, a(n) for n = 0..999
Eric Weisstein's World of Mathematics, Elementary Cellular Automaton
Index entries for sequences related to cellular automata
Index to Elementary Cellular Automata

Cf. A071036.

lim = 51; a = {}; Do[AppendTo[a, Take[#, 2 (k - 1) + 1] &@ Take[#[[k]], -(lim + k)]], {k, Length@ #}] &@ CellularAutomaton[150, {{1}, 0}, lim]; Accumulate[Count[#, n_ /; n == 0] & /@ a] (* Michael De Vlieger, Dec 09 2015 *)

cp's OEIS Frontend

A071052 Number of 0's in n-th row of triangle in A071036 (cellular automaton "Rule 150").

Views

Author

Keywords

References

Links

Crossrefs

Formula

A071053 Number of ON cells at n-th generation of 1-D CA defined by Rule 150, starting with a single ON cell at generation 0.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A038184 State of one-dimensional cellular automaton 'sigma' (Rule 150): 000,001,010,011,100,101,110,111 -> 0,1,1,0,1,0,0,1 at generation n, converted to a decimal number.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A118110 State of one-dimensional cellular automaton 'sigma' (Rule 150): 000,001,010,011,100,101,110,111 -> 0,1,1,0,1,0,0,1 at generation n, when started with a single ON cell, regarded as a binary number.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

A237120 Number of white areas in the graph of elementary cellular automaton with rule 150 at generation n.

Views

Author

Keywords

Comments

Links

Crossrefs

A265223 Total number of OFF (white) cells after n iterations of the "Rule 150" elementary cellular automaton starting with a single ON (black) cell.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica