|
%I #118 Oct 30 2023 07:56:19
%S 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,
%T 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,
%U 45,25,55,11,33,33,55,21,63,43,85,3,9,9,15,9,27,15,33,9,27,27
%N 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.
%C Number of 1's in n-th row of triangle in A071036.
%C 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
%C 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
%C 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
%D S. Wolfram, A New Kind of Science, Wolfram Media, 2002; Chapter 3.
%H N. J. A. Sloane, <a href="/A071053/b071053.txt">Table of n, a(n) for n = 0..16383</a> (first 1024 terms from T. D. Noe)
%H Joerg Arndt, <a href="http://list.seqfan.eu/oldermail/seqfan/2015-March/014530.html">A071053 (number of odd terms in expansion of (1+x+x^2)^n)</a>, SeqFan Mailing List, Mar 09 2015.
%H Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, <a href="http://arxiv.org/abs/1503.01796">A Meta-Algorithm for Creating Fast Algorithms for Counting ON Cells in Odd-Rule Cellular Automata</a>, arXiv:1503.01796 [math.CO], 2015; see also the <a href="http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/CAcount.html">Accompanying Maple Package</a>.
%H Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, <a href="http://arxiv.org/abs/1503.04249">Odd-Rule Cellular Automata on the Square Grid</a>, arXiv:1503.04249 [math.CO], 2015.
%H S. R. Finch, P. Sebah and Z.-Q. Bai, <a href="http://arXiv.org/abs/0802.2654">Odd Entries in Pascal's Trinomial Triangle</a>, arXiv:0802.2654 [math.NT], 2008.
%H Janko Gravner and Alexander E. Holroyd, <a href="https://dx.doi.org/10.1214/14-AOP918">Percolation and Disorder-Resistance in Cellular Automata</a>, Annals of Probability, volume 43, number 4, 2015, pages 1731-1776. Also <a href="https://arxiv.org/abs/1304.7301">arxiv:1304.7301</a> [math.PR], 2013-2015 and <a href="http://aeholroyd.org/papers/resistance.pdf">second author's copy</a>. See Fig. 1.1 (left).
%H S. Kropf, S. Wagner, <a href="https://arxiv.org/abs/1605.03654">q-Quasiadditive functions</a>, arXiv:1605.03654 [math.CO], 2016.
%H N. Pitsianis, P. Tsalides, G. L. Bleris, A. Thanailakis & H. C. Card, <a href="https://www.researchgate.net/publication/226210273_Deterministic_one-dimensional_cellular_automata">Deterministic one-dimensional cellular automata</a>, Journal of Statistical Physics, 56(1-2), 99-112, 1989. [Discusses Rule 150]
%H T. Sillke and Helmut Postl, <a href="http://www.mathematik.uni-bielefeld.de/~sillke/PUZZLES/trinomials">Odd trinomials: t(n) = (1+x+x^2)^n</a>
%H T. Sillke and Helmut Postl, <a href="/A071053/a071053.txt">Odd trinomials: t(n) = (1+x+x^2)^n</a> [Cached copy, with permission]
%H 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: <a href="https://vimeo.com/119073818">Part 1</a>, <a href="https://vimeo.com/119073819">Part 2</a>
%H N. J. A. Sloane, <a href="http://arxiv.org/abs/1503.01168">On the Number of ON Cells in Cellular Automata</a>, arXiv:1503.01168 [math.CO], 2015.
%H S. Wolfram, <a href="http://dx.doi.org/10.1103/RevModPhys.55.601">Statistical mechanics of cellular automata</a>, Rev. Mod. Phys., 55 (1983), 601--644.
%H <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>
%F 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
%F Floor((a(n)-1)/4) mod 2 = A020987(n). - _Ralf Stephan_, Mar 18 2004
%F a(2*n) = a(n); a(2*n+1) = a(n) + 2*a(floor(n/2)). - _Peter J. Taylor_, Mar 26 2020
%e May be arranged into blocks of sizes 1,1,2,4,8,16,...:
%e 1,
%e 3,
%e 3, 5,
%e 3, 9, 5, 11,
%e 3, 9, 9, 15, 5, 15, 11, 21,
%e 3, 9, 9, 15, 9, 27, 15, 33, 5, 15, 15, 25, 11, 33, 21, 43,
%e 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,
%e 3, 9, 9, 15, 9, 27, 15, 33, 9, 27, 27, ...
%e ... - _N. J. A. Sloane_, Sep 05 2014
%e .
%e From _Omar E. Pol_, Mar 15 2015: (Start)
%e 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):
%e 3;
%e ..
%e 3;
%e 5;
%e .......
%e 3, 9;
%e 5;
%e 11;
%e ...............
%e 3, 9, 9, 15;
%e 5, 15;
%e 11;
%e 21;
%e ...............................
%e 3, 9, 9, 15, 9, 27, 15, 33;
%e 5, 15, 15, 25;
%e 11, 33;
%e 21;
%e 43;
%e ..............................................................
%e 3, 9, 9, 15, 9, 27, 15, 33, 9, 27, 27, 45, 15, 45, 33, 63;
%e 5, 15, 15, 25, 15, 45, 25, 55;
%e 11, 33, 33, 55;
%e 21, 63;
%e 43;
%e 85;
%e ...
%e 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.
%e (End)
%t a[n_] := Total[CoefficientList[(x^2 + x + 1)^n, x, Modulus -> 2]];
%t Table[a[n], {n, 0, 100}] (* _Jean-François Alcover_, Aug 05 2018 *)
%o (PARI)
%o b(n) = { (2^n - (-1)^n) / 3; } \\ A001045
%o a(n)=
%o {
%o if ( n==0, return(1) );
%o \\ Use a( 2^k * t ) = a(t)
%o n \= 2^valuation(n,2);
%o if ( n==1, return(3) ); \\ Use a(2^k) == 3
%o \\ now n is odd
%o my ( v1 = valuation(n+1, 2) );
%o \\ Use a( 2^k - 1 ) = A001045( 2 + k ):
%o if ( n == 2^v1 - 1 , return( b( v1 + 2 ) ) );
%o my( k2 = 1, k = 0 );
%o while ( k2 < n, k2 <<= 1; k+=1 );
%o if ( k2 > n, k2 >>= 1; k-=1 );
%o my( t = n - k2 );
%o \\ here n == 2^k + 1 where k maximal
%o \\ Use the following:
%o \\ a( 2^k + t ) = 3 * a(t) if t <= 2^(k-1)
%o \\ a( 2^k + 2^(k-1) + t ) = 5 * a(t) if t <= 2^(k-2)
%o \\ a( 2^k + 2^(k-1) + 2^(k-2) + t ) = 11* a(t) if t <= 2^(k-3)
%o \\ ... etc. ...
%o \\ a( 2^k + ... + 2^(k-s) + t ) = A001045(s+2) * a(t) if t <= 2^((k-1)-s)
%o my ( s=1 );
%o while ( 1 ,
%o k2 >>= 1;
%o if ( t <= k2 , return( b(s+2) * a(t) ) );
%o t -= k2;
%o s += 1;
%o );
%o }
%o \\ _Joerg Arndt_, Mar 15 2015, from SeqFan Mailing List, Mar 09 2015
%Y Cf. A038184, A118110, A071036, A001045, A253102, A020987, A246035, A245562.
%K nonn,tabf
%O 0,2
%A _Hans Havermann_, May 26 2002
%E Entry revised by _N. J. A. Sloane_, Aug 13 2014
|
