%I A001316 M0297 N0109
%S A001316 1,2,2,4,2,4,4,8,2,4,4,8,4,8,8,16,2,4,4,8,4,8,8,16,4,8,8,16,8,16,16,32,
%T A001316 2,4,4,8,4,8,8,16,4,8,8,16,8,16,16,32,4,8,8,16,8,16,16,32,8,16,16,32,
%U A001316 16,32,32,64,2,4,4,8,4,8,8,16,4,8,8,16,8,16,16,32,4,8,8,16,8,16,16,32
%N A001316 Gould's sequence: a(n) = Sum_{k=0..n} (C(n,k) mod 2); number of odd entries 
               in row n of Pascal's triangle (A007318); 2^A000120(n).
%C A001316 Also called Dress's sequence.
%C A001316 All terms are powers of 2. The first occurrence of 2^k is when n = 2^k 
               - 1: e.g. the first occurrence of 16 is at n = 15 - Robert G. Wilson 
               v (rgwv(AT)rgwv.com), Dec 06 2000
%C A001316 a(n) is the highest power of 2 dividing C(2n,n)=A000984(n) - Benoit Cloitre 
               (benoit7848c(AT)orange.fr), Jan 23 2002
%C A001316 Also number of 1's in n-th row of triangle in A070886. - Hans Havermann 
               (pxp(AT)rogers.com), May 26 2002. Equivalently, number of live cells 
               in generation n of a one-dimensional cellular automaton, Rule 90. 
               [Ben Branman (137ben(AT)comcast.net), Feb 28 2009]
%C A001316 Also number of numbers k, 0<=k<=n, such that (k OR n) = n (bitwise logical 
               OR): a(n) = #{k : T(n,k)=n, 0<=k<=n}, where T is defined as in A080098. 
               - Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Jan 28 2003
%C A001316 To construct the sequence, start with 1 and use the rule: If k>=0 and 
               a(0),a(1),...,a(2^k-1) are the 2^k first terms, then the next 2^k 
               terms are 2*a(0),2*a(1),...,2*a(2^k-1). - Benoit Cloitre (benoit7848c(AT)orange.fr), 
               Jan 30 2003
%C A001316 Also, numerator((2^k)/k!). - Mohammed Bouayoun (mohammed.bouayoun(AT)sanef.com), 
               Mar 03 2004
%C A001316 The odd entries in Pascal's triangle form the Seirpinski Gasket (a fractal). 
               - Amarnath Murthy (amarnath_murthy(AT)yahoo.com), Nov 20 2004
%C A001316 Fixed point of the morphism "1" -> "1,2", "2" -> "2,4", "4" -> "4,8", 
               ..., "2^k" -> "2^k,2^(k+1)", ... starting with a(0) = 1; 1 -> 12 
               -> 1224 -> = 12242448 -> 122424482448488(16) -> . . . - Philippe 
               DELEHAM (kolotoko(AT)wanadoo.fr), Jun 18 2005
%C A001316 a(n) = number of 1's of stage n of the one-dimensional cellular automaton 
               with Rule 90. - Andras Erszegi (erszegi.andras(AT)chello.hu), Apr 
               01 2006
%C A001316 a[33..63]=A117973[1..31] - Stephen Crowley (crow(AT)crowlogic.net), Mar 
               21 2007
%C A001316 Or the number of solutions of the equation: A000120(x)+A000120(n-x)=A000120(n). 
               [From Vladimir Shevelev (shevelev(AT)bgu.ac.il), Jul 19 2009]
%C A001316 Equals left border of triangle A166548 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), 
               Oct 16 2009]
%D A001316 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A001316 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 
               (includes this sequence).
%D A001316 A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of 
               combinatorial proof, M.A.A. 2003, p. 75ff.
%D A001316 S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 145-151.
%D A001316 H. W. Gould, Exponential Binomial Coefficient Series. Tech. Rep. 4, Math. 
               Dept., West Virginia Univ., Morgantown, WV, Sep 1961.
%D A001316 D. G. Poole, The towers and triangles of Professor Claus (or, Pascal 
               knows Hanoi), Math. Mag., 67 (1994), 323-344.
%D A001316 M. R. Schroeder, "Fractals, Chaos, Power Laws," W.H. Freeman, NY, 1991, 
               page 383.
%H A001316 T. D. Noe, <a href="b001316.txt">Table of n, a(n) for n=0..1000</a>
%H A001316 J.-P. Allouche and J. Shallit, <a href="http://www.cs.uwaterloo.ca/~shallit/
               Papers/as0.ps">The ring of k-regular sequences</a>, Theoretical Computer 
               Sci., 98 (1992), 163-197.
%H A001316 E. Deutsch and B. E. Sagan, <a href="http://arxiv.org/pdf/math.CO/0407326">
               Congruences for Catalan and Motzkin numbers and related sequences</
               a>, J. Num. Theory 117 (2006), 191-215.
%H A001316 Philippe Dumas, <a href="http://algo.inria.fr/dumas/DC/asympt.html">Diviser 
               pour regner Comportement asymptotique</a> (has many references)
%H A001316 S. R. Finch, <a href="http://algo.inria.fr/bsolve/constant/stlrsky/stlrsky.html">
               Stolarsky-Harborth Constant</a>
%H A001316 Michael Gilleland, <a href="selfsimilar.html">Some Self-Similar Integer 
               Sequences</a>
%H A001316 T. Pisanski and T. W. Tucker, <a href="http://citeseer.ist.psu.edu/rd/
               18543120%2C441149%2C1%2C0.25%2CDownload/http://citeseer.ist.psu.edu/
               cache/papers/cs/22018/http:zSzzSzwww.ijp.sizSzftpzSzpubzSzpreprintszSzpszSz2000zSzpp696.pdf/
               pisanski00growth.pdf">Growth in Repeated Truncations of Maps</a>, 
               Atti Sem. Mat. Fis. Univ. Modena 49 (2001), suppl., 167-176.
%H A001316 R. Stephan, <a href="http://arXiv.org/abs/math.CO/0307027">Divide-and-conquer 
               generating functions. I. Elementary sequences</a>
%H A001316 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               ElementaryCellularAutomaton.html">Elementary Cellular Automaton</
               a>
%H A001316 <a href="Sindx_Ce.html#cell">Index entries for sequences related to cellular 
               automata</a>
%F A001316 a(n) = 2^A000120(n).
%F A001316 a(0) = 1; for n>0, write n = 2^i + j where 0 <= j < 2^i; then a(n) = 
               2*a(j).
%F A001316 a(n) = 2a(n-1)/A006519(n) = A000079(n)*A049606(n)/A000142(n)
%F A001316 a(n) = A038573(n) + 1
%F A001316 G.f.: Prod_{k>=0} (1+2*z^(2^k)). - Ralf Stephan (ralf(AT)ark.in-berlin.de), 
               Apr 06 2003.
%F A001316 a(n)=sum(i=0, 2*n, (binomial(2*n, i) (mod 2))*(-1)^i) - Benoit Cloitre 
               (benoit7848c(AT)orange.fr), Nov 16 2003
%F A001316 a(n) {mod 3}=A001285(n) - Benoit Cloitre (benoit7848c(AT)orange.fr), 
               May 09 2004
%F A001316 2^n-2*sum{k=0..n, floor(C(n, k)/2)} - Paul Barry (pbarry(AT)wit.ie), 
               Dec 24 2004
%F A001316 a(n)=product{k=0..log_2(n), 2^b(n, k)}, b(n, k)=coefficient of 2^k in 
               binary expansion of n. Formula from Paul D. Hanna.
%F A001316 Sum_{k<n} a(k) = A006046(n).
%F A001316 a(n)=(n/2)+(1/2)+(sum(-(-1)^binomial(n,k),k=0..n)/2) - Stephen Crowley 
               (crow(AT)crowlogic.net), Mar 21 2007
%F A001316 Contribution from Johannes W. Meijer (meijgia(AT)hotmail.com), Feb 20 
               2009: G.f.: (1/2)*z^(1/2)*sinh(2*z^(1/2))
%F A001316 Equals infinite convolution product of [1,2,0,0,0,0,0,0,0] aerated A000079 
               - 1 times, i.e. [1,2,0,0,0,0,0,0,0] * [1,0,2,0,0,0,0,0,0] * [1,0,
               0,0,2,0,0,0,0]. [From Mats Granvik, Gary W. Adamson (mats.granvik(AT)abo.fi), 
               Oct 02 2009]
%F A001316 a(n) = f(n, 1) with f(x, y) = if x = 0 then y else f(floor(x/2), y*(1 
               + x mod 2)). [From Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), 
               Nov 21 2009]
%e A001316 Has a natural structure as a triangle:
%e A001316 .1,
%e A001316 .2,
%e A001316 .2,4,
%e A001316 .2,4,4,8,
%e A001316 .2,4,4,8,4,8,8,16,
%e A001316 .2,4,4,8,4,8,8,16,4,8,8,16,8,16,16,32,
%e A001316 .2,4,4,8,4,8,8,16,4,8,8,16,8,16,16,32,4,8,8,16,8,16,16,32,8,16,16,32,
               16,32,32,64,
%e A001316 ....
%e A001316 The rows converge to A117973.
%e A001316 Contribution from Omar E. Pol (info(AT)polprimos.com), Jun 07 2009: (Start)
%e A001316 Also, triangle begins:
%e A001316 .1;
%e A001316 .2,2;
%e A001316 .4,2,4,4;
%e A001316 .8,2,4,4,8,4,8,8;
%e A001316 16,2,4,4,8,4,8,8,16,4,8,8,16,8,16,16;
%e A001316 32,2,4,4,8,4,8,8,16,4,8,8,16,8,16,16,32,4,8,8,16,8,16,16,32,8,16,16,32,
               16,32,32;
%e A001316 64,2,4,4,8,4,8,8,16,4,8,8,16,8,16,16,32,4,8,8,16,8,16,16,32,8,16,16,32,
               16,32,...
%e A001316 (End)
%p A001316 A001316 := proc(n) local k; add(binomial(n,k) mod 2, k=0..n); end;
%p A001316 S:=[1]; S:=[op(S),op(2*s)]; # repeat ad infinitum!
%p A001316 a := n -> 2^add(i,i=convert(n,base,2)); [From Peter Luschny (peter(AT)luschny.de), 
               Mar 11 2009]
%t A001316 Table[ Sum[ Mod[ Binomial[n, k], 2], {k, 0, n} ], {n, 0, 100} ]
%t A001316 Flatten[ Nest[ Flatten[ # /. a_Integer -> {a, 2a}] &, {1}, 7]] (from 
               Robert G. Wilson v (rgwv(at)rgwv.com), Jan 24 2006)
%t A001316 Map[Function[Apply[Plus,Flatten[ #1]]], CellularAutomaton[90,{{1},0},
               100]] (N. J. A. Sloane, Aug 10 2009)
%o A001316 (PARI) a(n)=if(n<0,0,numerator(2^n/n!))
%o A001316 (PARI) A001316(n)=1<<norml2(binary(n)) [From M. F. Hasler (MHasler(AT)univ-ag.fr), 
               May 03 2009]
%Y A001316 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 A001316 For partial sums see A006046. Fir first differences see A151930.
%Y A001316 This is the numerator of 2^n/n!, while A049606 gives the denominator.
%Y A001316 Cf. A051638, A048967, A007318, A094959, A048896, A117973.
%Y A001316 Cf. A008977, A139541, A048883, A102376.
%Y A001316 Cf. A156769 = Gould's sequence appears in the numerators. - Johannes 
               W. Meijer (meijgia(AT)hotmail.com), Feb 20 2009
%Y A001316 Cf. A038573, A159913. [From M. F. Hasler (MHasler(AT)univ-ag.fr), May 
               03 2009]
%Y A001316 Cf. A000079. [From Omar E. Pol (info(AT)polprimos.com), Jun 07 2009]
%Y A001316 A166548 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Oct 16 2009]
%Y A001316 Sequence in context: A094269 A157227 A054536 this_sequence A161831 A096865 
               A116466
%Y A001316 Adjacent sequences: A001313 A001314 A001315 this_sequence A001317 A001318 
               A001319
%K A001316 nonn,easy,nice,new
%O A001316 0,2
%A A001316 N. J. A. Sloane (njas(AT)research.att.com).
%E A001316 Additional comments from Henry Bottomley (se16(AT)btinternet.com), Mar 
               12 2001
%E A001316 Additional comments from N. J. A. Sloane, May 30 2009