

A071053


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


43



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

Number of 1's in nth 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 oddrule cellular automaton defined by OddRule 007 (see EkhadSloaneZeilberger "OddRule 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


REFERENCES

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


LINKS

T. D. Noe and 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 MetaAlgorithm for Creating Fast Algorithms for Counting ON Cells in OddRule Cellular Automata, arXiv:1503.01796 [math.CO], 2015; see also the Accompanying Maple Package.
Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, OddRule 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 DisorderResistance in Cellular Automata, Annals of Probability, 2014. See Fig. 1.1 (left).
S. Kropf, S. Wagner, qQuasiadditive functions, arXiv:1605.03654 [math.CO], 2016.
N. Pitsianis, P. Tsalides, G. L. Bleris, A. Thanailakis & H. C. Card, Deterministic onedimensional cellular automata, Journal of Statistical Physics, 56(12), 99112, 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), 601644.
Index entries for sequences related to cellular automata


FORMULA

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


EXAMPLE

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(sr)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)


MATHEMATICA

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


PROG

(PARI)
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^(k1)
\\ a( 2^k + 2^(k1) + t ) = 5 * a(t) if t <= 2^(k2)
\\ a( 2^k + 2^(k1) + 2^(k2) + t ) = 11* a(t) if t <= 2^(k3)
\\ ... etc. ...
\\ a( 2^k + ... + 2^(ks) + t ) = A001045(s+2) * a(t) if t <= 2^((k1)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


CROSSREFS

Cf. A038184, A118110, A071036, A001045, A253102, A020987, A246035, A245562.
Sequence in context: A204100 A048691 A248955 * A298398 A094439 A122037
Adjacent sequences: A071050 A071051 A071052 * A071054 A071055 A071056


KEYWORD

nonn,tabf


AUTHOR

Hans Havermann, May 26 2002


EXTENSIONS

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


STATUS

approved



