cp's OEIS Frontend

A102376 a(n) = 4^A000120(n).

%I A102376 #74 Feb 21 2025 16:44:15
%S A102376 1,4,4,16,4,16,16,64,4,16,16,64,16,64,64,256,4,16,16,64,16,64,64,256,
%T A102376 16,64,64,256,64,256,256,1024,4,16,16,64,16,64,64,256,16,64,64,256,64,
%U A102376 256,256,1024,16,64,64,256,64,256,256,1024,64,256,256,1024,256,1024,1024
%N A102376 a(n) = 4^A000120(n).
%C A102376 Consider a simple cellular automaton, a grid of binary cells c(i,j), where the next state of the grid is calculated by applying the following rule to each cell: c(i,j) = ( c(i+1,j-1) + c(i+1,j+1) + c(i-1,j-1) + c(i-1,j+1) ) mod 2 If we start with a single cell having the value 1 and all the others 0, then the aggregate values of the subsequent states of the grid will be the terms in this sequence. - Andras Erszegi (erszegi.andras(AT)chello.hu), Mar 31 2006. See link for initial states. - _N. J. A. Sloane_, Feb 12 2015
%C A102376 This is the odd-rule cellular automaton defined by OddRule 033 (see Ekhad-Sloane-Zeilberger "Odd-Rule Cellular Automata on the Square Grid" link). - _N. J. A. Sloane_, Feb 25 2015
%C A102376 First differences of A116520. - _Omar E. Pol_, May 05 2010
%H A102376 N. J. A. Sloane, <a href="/A102376/b102376.txt">Table of n, a(n) for n = 0..10000</a>
%H A102376 David Applegate, Omar E. Pol, and N. J. A. Sloane, <a href="/A000695/a000695_1.pdf">The Toothpick Sequence and Other Sequences from Cellular Automata</a>, 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.]
%H A102376 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 A102376 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 A102376 Nathan Epstein, <a href="https://giant.gfycat.com/QueasyNeatHadrosaurus.webm">Animation of CA generating A102376</a>
%H A102376 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 A102376 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 A102376 N. J. A. Sloane, <a href="/A102376/a102376.png">Illustration of generations 0-15 of the cellular automaton</a>
%H A102376 N. J. A. Sloane, <a href="/wiki/Catalog_of_Toothpick_and_CA_Sequences_in_OEIS">Catalog of Toothpick and Cellular Automata Sequences in the OEIS</a>
%H A102376 Alexander Yu. Vlasov, <a href="https://arxiv.org/abs/2312.13034">Modelling reliability of reversible circuits with 2D second-order cellular automata</a>, arXiv:2312.13034 [nlin.CG], 2023. See page 13.
%H A102376 <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>
%F A102376 Formulas due to _Paul D. Hanna_: (Start)
%F A102376 G.f.: Product_{k>=0} 1 + 4x^(2^k).
%F A102376 a(n) = Product_{k=0..log_2(n)} 4^b(n, k), b(n, k)=coefficient of 2^k in binary expansion of n.
%F A102376 a(n) = Sum_{k=0..n} (C(n, k) mod 2)*3^A000120(n-k). (End)
%F A102376 a(n) = Sum_{k=0..n} (C(n, k) mod 2) * Sum_{j=0..k} (C(k, j) mod 2) * Sum_{i=0..j} (C(j, i) mod 2). - _Paul Barry_, Apr 01 2005
%F A102376 G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^4)) where f(u, v, w) = w * (u^2 - 2*u*v + 5*v^2) - 4*v^3. - _Michael Somos_, May 29 2008
%F A102376 Run length transform of A000302. - _N. J. A. Sloane_, Feb 23 2015
%e A102376 1 + 4*x + 4*x^2 + 16*x^3 + 4*x^4 + 16*x^5 + 16*x^6 + 64*x^7 + 4*x^8 + ...
%e A102376 From _Omar E. Pol_, Jun 07 2009: (Start)
%e A102376 Triangle begins:
%e A102376   1;
%e A102376   4;
%e A102376   4,16;
%e A102376   4,16,16,64;
%e A102376   4,16,16,64,16,64,64,256;
%e A102376   4,16,16,64,16,64,64,256,16,64,64,256,64,256,256,1024;
%e A102376   4,16,16,64,16,64,64,256,16,64,64,256,64,256,256,1024,16,64,64,256,64,256,...
%e A102376 (End)
%p A102376 seq(4^convert(convert(n,base,2),`+`),n=0..100); # _Robert Israel_, Apr 30 2017
%t A102376 Table[4^DigitCount[n, 2, 1], {n, 0, 100}] (* _Indranil Ghosh_, Apr 30 2017 *)
%o A102376 (PARI) {a(n) = if( n<0, 0, 4^subst( Pol( binary(n)), x, 1))} /* _Michael Somos_, May 29 2008 */
%o A102376 a(n) = 4^hammingweight(n); \\ _Michel Marcus_, Apr 30 2017
%o A102376 (Haskell)
%o A102376 a102376 = (4 ^) . a000120  -- _Reinhard Zumkeller_, Feb 13 2015
%o A102376 (Python)
%o A102376 def a(n): return 4**bin(n)[2:].count("1") # _Indranil Ghosh_, Apr 30 2017
%o A102376 (Python)
%o A102376 def A102376(n): return 1<<(n.bit_count()<<1) # _Chai Wah Wu_, Nov 15 2022
%Y A102376 For generating functions Prod_{k>=0} (1+a*x^(b^k)) for the following values of (a,b) see: (1,2) A000012 and A000027, (1,3) A039966 and A005836, (1,4) A151666 and A000695, (1,5) A151667 and A033042, (2,2) A001316, (2,3) A151668, (2,4) A151669, (2,5) A151670, (3,2) A048883, (3,3) A117940, (3,4) A151665, (3,5) A151671, (4,2) A102376, (4,3) A151672, (4,4) A151673, (4,5) A151674.
%Y A102376 A151783 is a very similar sequence.
%Y A102376 Cf. A001316, A048883, A000079, A116520, A000302.
%Y A102376 See A160239 for the analogous CA defined by Rule 204 on an 8-celled neighborhood.
%K A102376 easy,nonn,tabf
%O A102376 0,2
%A A102376 _Paul Barry_, Jan 05 2005