login
This site is supported by donations to The OEIS Foundation.

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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).
(Formerly M0297 N0109)
121

%I M0297 N0109

%S 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,

%T 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,

%U 32,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 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 Also called Dress's sequence.

%C 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_, Dec 06 2000

%C a(n) is the highest power of 2 dividing C(2n,n)=A000984(n) - _Benoit Cloitre_, Jan 23 2002

%C Also number of 1's in n-th row of triangle in A070886. - _Hans Havermann_, May 26 2002. Equivalently, number of live cells in generation n of a one-dimensional cellular automaton, Rule 90. - _Ben Branman_, Feb 28 2009

%C 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_, Jan 28 2003

%C 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_, Jan 30 2003

%C Also, numerator((2^k)/k!). - Mohammed Bouayoun (mohammed.bouayoun(AT)sanef.com), Mar 03 2004

%C The odd entries in Pascal's triangle form the Sierpinski Gasket (a fractal). - _Amarnath Murthy_, Nov 20 2004.

%C Row sums of Sierpinski’s Gasket A047999. - _Johannes W. Meijer_, Jun 05 2011

%C 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 Deléham_, Jun 18 2005

%C 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 a[33..63]=A117973[1..31] - _Stephen Crowley_, Mar 21 2007

%C Or the number of solutions of the equation: A000120(x)+A000120(n-x)=A000120(n). - _Vladimir Shevelev_, Jul 19 2009

%C For positive n, a(n) equals the denominator of the permanent of the n X n matrix consisting entirely of (1/2)'s. - _John M. Campbell_, May 26, 2011

%C Companions to A001316 are A048896, A105321, A117973, A151930 and A191488. They all have the same structure. We observe that for all these sequences a((2*n+1)*2^p-1) = C(p)*A001316(n), p>=0. If C(p) = 2^p then a(n) = A001316(n), if C(p) = 1 then a(n) = A048896(n), if C(p) = 2^p+2 then a(n) = A105321(n+1), if C(p) = 2^(p+1) then a(n) = A117973(n), if C(p) = 2^p-2 then a(n) = (-1)*A151930(n) and if C(p) = 2^(p+1)+2 then a(n) = A191488(n). Furthermore for all a(2^p - 1) = C(p). - _Johannes W. Meijer_, Jun 05 2011

%C a(n) = number of zeros in n-th row of A219463 = number of ones in n-th row of A047999. - _Reinhard Zumkeller_, Nov 30 2012

%C a(n) = A226078(n,1). - _Reinhard Zumkeller_, May 25 2013

%D A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 75ff.

%D S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 145-151.

%D H. W. Gould, Exponential Binomial Coefficient Series. Tech. Rep. 4, Math. Dept., West Virginia Univ., Morgantown, WV, Sep 1961.

%D Sam Northshield, "Stern's Diatomic Sequence 0,1,1,2,1,3,2,3,1,4,...", Amer. Math. Month., Vol. 117 (7), pp. 581-598, 2010.

%D D. G. Poole, The towers and triangles of Professor Claus (or, Pascal knows Hanoi), Math. Mag., 67 (1994), 323-344.

%D M. R. Schroeder, Fractals, Chaos, Power Laws, W.H. Freeman, NY, 1991, page 383.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H T. D. Noe, <a href="/A001316/b001316.txt">Table of n, a(n) for n = 0..1000</a>

%H David Applegate, Omar E. Pol and N. J. A. Sloane, <a href="http://neilsloane.com/doc/tooth.pdf">The Toothpick Sequence and Other Sequences from Cellular Automata</a>

%H N. J. A. Sloane, <a href="http://neilsloane.com/doc/toothlist.html">Catalog of Toothpick and Cellular Automata Sequences in the OEIS</a>

%H 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 E. Deutsch and B. E. Sagan, <a href="http://arxiv.org/abs/math.CO/0407326">Congruences for Catalan and Motzkin numbers and related sequences</a>, J. Num. Theory 117 (2006), 191-215.

%H Philippe Dumas, <a href="http://algo.inria.fr/dumas/DC/asympt.html">Diviser pour regner Comportement asymptotique</a> (has many references)

%H S. R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/constant/stlrsky/stlrsky.html">Stolarsky-Harborth Constant</a>

%H Michael Gilleland, <a href="/selfsimilar.html">Some Self-Similar Integer Sequences</a>

%H T. Pisanski and T. W. Tucker, <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.5375">Growth in Repeated Truncations of Maps</a>, Atti Sem. Mat. Fis. Univ. Modena 49 (2001), suppl., 167-176.

%H R. Stephan, <a href="http://arXiv.org/abs/math.CO/0307027">Divide-and-conquer generating functions. I. Elementary sequences</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ElementaryCellularAutomaton.html">Elementary Cellular Automaton</a>

%H <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>

%F a(n) = 2^A000120(n).

%F a(0) = 1; for n>0, write n = 2^i + j where 0 <= j < 2^i; then a(n) = 2*a(j).

%F a(n) = 2a(n-1)/A006519(n) = A000079(n)*A049606(n)/A000142(n)

%F a(n) = A038573(n) + 1

%F G.f.: Prod_{k>=0} (1+2*z^(2^k)). - _Ralf Stephan_, Apr 06 2003.

%F a(n)=sum(i=0, 2*n, (binomial(2*n, i) (mod 2))*(-1)^i) - _Benoit Cloitre_, Nov 16 2003

%F a(n) {mod 3}=A001285(n) - _Benoit Cloitre_, May 09 2004

%F 2^n-2*sum{k=0..n, floor(C(n, k)/2)} - _Paul Barry_, Dec 24 2004

%F 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 Sum_{k<n} a(k) = A006046(n).

%F a(n)=(n/2)+(1/2)+(sum(-(-1)^binomial(n,k),k=0..n)/2) - _Stephen Crowley_, Mar 21 2007

%F G.f.: (1/2)*z^(1/2)*sinh(2*z^(1/2)) - _Johannes W. Meijer_, Feb 20 2009

%F 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]. - _Mats Granvik_, _Gary W. Adamson_, Oct 02 2009

%F a(n) = f(n, 1) with f(x, y) = if x = 0 then y else f(floor(x/2), y*(1 + x mod 2)). - _Reinhard Zumkeller_, Nov 21 2009

%F a(n) = 2 ^ (number of 1's in binary form of (n-1)) - _Gabriel C. Benamy_, Dec 08 2009

%F a((2*n+1)*2^p-1) = (2^p)*a(n), p>=0. - _Johannes W. Meijer_, Jun 05 2011

%F a(n) = A000120(A001317(n)). - _Reinhard Zumkeller_, Nov 24 2012

%e Has a natural structure as a triangle:

%e .1,

%e .2,

%e .2,4,

%e .2,4,4,8,

%e .2,4,4,8,4,8,8,16,

%e .2,4,4,8,4,8,8,16,4,8,8,16,8,16,16,32,

%e .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 ....

%e The rows converge to A117973.

%e Contribution from _Omar E. Pol_, Jun 07 2009: (Start)

%e Also, triangle begins:

%e .1;

%e .2,2;

%e .4,2,4,4;

%e .8,2,4,4,8,4,8,8;

%e 16,2,4,4,8,4,8,8,16,4,8,8,16,8,16,16;

%e 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 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 (End)

%p A001316 := proc(n) local k; add(binomial(n,k) mod 2, k=0..n); end;

%p S:=[1]; S:=[op(S),op(2*s)]; # repeat ad infinitum!

%p a := n -> 2^add(i,i=convert(n,base,2)); # _Peter Luschny_, Mar 11 2009

%t Table[ Sum[ Mod[ Binomial[n, k], 2], {k, 0, n} ], {n, 0, 100} ]

%t Flatten[ Nest[ Flatten[ # /. a_Integer -> {a, 2a}] &, {1}, 7]] (* _Robert G. Wilson v_, Jan 24 2006 *)

%t Map[Function[Apply[Plus,Flatten[ #1]]], CellularAutomaton[90,{{1},0},100]] (* _N. J. A. Sloane_, Aug 10 2009 *)

%t Table[2^(RealDigits[n - 1, 2][[1]] // Total), {n, 1, 100}] (* _Gabriel C. Benamy_, Dec 08 2009 *)

%t CoefficientList[Series[Exp[2*x], {x, 0, 100}], x] // Numerator (* _Jean-François Alcover_, Oct 25 2013 *)

%o (PARI) a(n)=if(n<0,0,numerator(2^n/n!))

%o (PARI) A001316(n)=1<<norml2(binary(n)) \\ _M. F. Hasler_, May 03 2009

%o (PARI) a(n)=2^hammingweight(n) \\ _Charles R Greathouse IV_, Jan 04 2013

%o (Haskell)

%o a001316 = sum . a047999_row -- _Reinhard Zumkeller_, Nov 24 2012

%o a001316_list = 1 : gould [1] where

%o gould (x:xs) = zs ++ gould zs where

%o zs = (2*x) : xs ++ map (* 2) (x:xs)

%o -- _Reinhard Zumkeller_, Sep 16 2011

%o (Sage)

%o def A001316(n):

%o if n <= 1: return Integer(n+1)

%o return A001316(n//2) << n%2

%o [A001316(n) for n in range(88)] # _Peter Luschny_, Nov 19 2012

%Y Equals left border of triangle A166548. - _Gary W. Adamson_, Oct 16 2009

%Y 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 For partial sums see A006046. For first differences see A151930.

%Y This is the numerator of 2^n/n!, while A049606 gives the denominator.

%Y Cf. A051638, A048967, A007318, A094959, A048896, A117973, A008977, A139541, A048883, A102376.

%Y Cf. A156769 = Gould's sequence appears in the numerators. - _Johannes W. Meijer_, Feb 20 2009

%Y Cf. A038573, A159913, A000079, A166548.

%K nonn,easy,nice

%O 0,2

%A _N. J. A. Sloane_.

%E Additional comments from _Henry Bottomley_, Mar 12 2001

%E Additional comments from _N. J. A. Sloane_, May 30 2009

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified April 24 19:08 EDT 2014. Contains 240988 sequences.