%I A000120 M0105 N0041
%S A000120 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,1,2,2,
%T A000120 3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,1,2,2,3,2,3,
%U A000120 3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3
%N A000120 1's-counting sequence: number of 1's in binary expansion of n (or the 
               binary weight of n).
%C A000120 a(n) is also the largest integer such that 2^a(n) divides binomial(2n,
               n)=A000984(n) - Benoit Cloitre (benoit7848c(AT)orange.fr), Mar 27 
               2002
%C A000120 To construct the sequence, start with 0 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 a(0)+1,a(1)+1,...,a(2^k-1)+1. - Benoit Cloitre (benoit7848c(AT)orange.fr), 
               Jan 30 2003
%C A000120 An example of a fractal sequence. That is, if you omit every other number 
               in the sequence, you get the original sequence. And of course this 
               can be repeated. So if you form the sequence a(0 * 2^n), a(1 * 2^n), 
               a(2 * 2^n), a(3 * 2^n), ... (for any integer n > 0), you get the 
               original sequence. - Christopher.Hills(AT)sepura.co.uk, May 14, 2003
%C A000120 The n-th row of Pascal's triangle has 2^k distinct odd binomial coefficients 
               where k=a(n)-1. - Lekraj Beedassy (blekraj(AT)yahoo.com), May 15 
               2003
%C A000120 Fixed point of the morphism 0 -> 01, 1 -> 12, 2 -> 23, 3 -> 34, 4 -> 
               45, etc., starting from a(0) = 0. - Robert G. Wilson v, Jan 24 2006. 
               - Jeremy Gardiner (jeremy.gardiner(AT)btinternet.com), Jan 25 2006
%C A000120 a(n) = number of times n appears among the mystery calculator sequences: 
               A005408, A042964, A047566, A115419, A115420, A115421. - Jeremy Gardiner 
               (jeremy.gardiner(AT)btinternet.com), Jan 25 2006
%C A000120 a(n) = number of solutions of the Diophantine equation 2^m*k+2^(m-1)+i=n, 
               where m>=1, k>=0, 0<=i<2^(m-1); a(5)=2 because only (m,k,i)=(1,2,
               0) [2^1*2+2^0+0=5] and (m,k,i)=(3,0,1) [2^3*0+2^2+1=5] are solutions. 
               - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Jan 31 2006
%C A000120 The first appearance of k, k=>0, is at a(2^k-1). - Robert G. Wilson v 
               Jul 27 2006
%C A000120 a(n) = A138530(n,2) for n > 1. - Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), 
               Mar 26 2008
%C A000120 Sequence is given by T^(infty)(0) where T is the operator transforming 
               any word w=w(1)w(2)...w(m) into T(w)=w(1)(w(1)+1)w(2)(w(2)+1)...w(m)(w(m)+1). 
               i.e. T(0)=01, T(01)=0112, T(0112)=01121223. [From Benoit Cloitre 
               (benoit7848c(AT)orange.fr), Mar 04 2009]
%C A000120 a(A077436(n))=A159918(A077436(n)); a(A000290(n))=A159918(n). [From Reinhard 
               Zumkeller (reinhard.zumkeller(AT)gmail.com), Apr 25 2009]
%C A000120 For n>=2, the minimal k for which a(k(2^n-1)) is not multiple of n is 
               2^n+3. [From Vladimir Shevelev (shevelev(AT)bgu.ac.il), Jun 05 2009]
%C A000120 a(n) = A063787(n) - A007814(n). [From Gary W. Adamson (qntmpkt(AT)yahoo.com), 
               Jun 04 2009]
%C A000120 Triangle inequality: a(k+m)<=a(k)+a(m). Equality holds iff C(k+m,m) is 
               odd. [From Vladimir Shevelev (shevelev(AT)bgu.ac.il), Jul 19 2009]
%D A000120 J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical 
               Computer Sci., 98 (1992), 163-197.
%D A000120 R. Bellman and H. N. Shapiro, On a problem in additive number theory, 
               Annals Math., 49 (1948), 333-340. [From N. J. A. Sloane, Mar 12 2009]
%D A000120 Emmanuel Ferrand, Deformations of the Taylor Formula, Journal of Integer 
               Sequences, Vol. 10 (2007), Article 07.1.7.
%D A000120 R. L. Graham, On primitive graphs and optimal vertex assignments, pp. 
               170-186 of Internat. Conf. Combin. Math. (New York, 1970), Annals 
               of the NY Academy of Sciences, Vol. 175, 1970.
%D A000120 M. D. McIlroy, The number of 1's in binary integers: bounds and extremal 
               properties, SIAM J. Comput., 3 (1974), 255-261.
%D A000120 Problem B-82, Fib. Quart., 4 (1966), 374-375.
%D A000120 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 
               (includes this sequence).
%D A000120 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%H A000120 N. J. A. Sloane, <a href="b000120.txt">Table of n, a(n) for n = 0..10000</
               a>
%H A000120 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 A000120 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)
%H A000120 P. Flajolet et al., <a href="http://algo.inria.fr/flajolet/Publications/
               FlGrKiPrTi94.pdf">Mellin Transforms And Asymptotics: Digital Sums</
               a>, Theoret. Computer Sci. 23 (1994), 291-314.
%H A000120 Michael Gilleland, <a href="selfsimilar.html">Some Self-Similar Integer 
               Sequences</a>
%H A000120 Nick Hobson, <a href="a000120.py.txt">Python program for this sequence</
               a>
%H A000120 K. Q. Ji and H. S. Wilf, <a href="http://arXiv.org/abs/math.CO/0611465">
               Extreme Palindromes</a>
%H A000120 R. Stephan, <a href="somedcgf.html">Some divide-and-conquer sequences 
               ...</a>
%H A000120 R. Stephan, <a href="a079944.ps">Table of generating functions</a>
%H A000120 R. Stephan, <a href="http://arXiv.org/abs/math.CO/0307027">Divide-and-conquer 
               generating functions. I. Elementary sequences</a>
%H A000120 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               Binary.html">Link to a section of The World of Mathematics.</a>
%H A000120 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               DigitCount.html">Link to a section of The World of Mathematics.</
               a>
%H A000120 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               Stolarsky-HarborthConstant.html">Link to a section of The World of 
               Mathematics.</a>
%H A000120 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               DigitSum.html">Digit Sum</a>
%H A000120 Wolfram Research, <a href="http://functions.wolfram.com/NumberTheoryFunctions/
               DigitCount/31/01/ShowAll.html">Numbers in Pascal's triangle</a>
%H A000120 <a href="Sindx_Cor.html#core">Index entries for "core" sequences</a>
%H A000120 <a href="Sindx_Bi.html#binary">Index entries for sequences related to 
               binary expansion of n</a>
%F A000120 a(0) = 0, a(2n) = a(n), a(2n+1) = a(n) + 1.
%F A000120 a(0) = 0, a(2^i) = 1; otherwise if n = 2^i + j with 0 < j < 2^i, a(n) 
               = a(j) + 1.
%F A000120 G.f.: Product_{k >= 0} (1 + y*x^(2^k)) = Sum_{n >= 0} y^a(n)*x^n. - N. 
               J. A. Sloane, Jun 04 2009
%F A000120 a(n) = a(n-1)+1-A007814(n) = log2[A001316(n)] = 2n-A005187(n) = A070939(n)-A023416(n). 
               - Henry Bottomley (se16(AT)btinternet.com), Apr 04 2001; corrected 
               by Ralf Stephan (ralf(AT)ark.in-berlin.de), Apr 15 2002
%F A000120 a(n)=log2(A000984(n)/A001790(n) ). - Benoit Cloitre, Oct 02 2002
%F A000120 For n>0, a(n)=n-sum(k=1, n, A007814(k)). - Benoit Cloitre (benoit7848c(AT)orange.fr), 
               Oct 19 2002
%F A000120 a(n)=n-sum(k>0, floor(n/2^k))=n-A011371(n). - Benoit Cloitre, Dec 19 
               2002
%F A000120 G.f.: 1/(1-x) * Sum(k>=0, x^(2^k)/(1+x^(2^k))). - Ralf Stephan (ralf(AT)ark.in-berlin.de), 
               Apr 19 2003
%F A000120 a(0)=0, a(n)=a(n-2^log_2(floor(n)))+1. Examples: a(6)=a(6-2^2)+1=a(2)+1=a(2-2^1)+1+1=a(0)+2=2; 
               a(101)=a(101-2^6)+1=a(37)+1=a(37-2^5)+2=a(5-2^2)+3=a(1-2^0)+4=a(0)+4=4; 
               a(6275)=a(6275-2^12)+1=a(2179-2^11)+2=a(131-2^7)+3=a(3-2^1)+4=a(1-2^0)+5=5; 
               a(4129)=a(4129-2^12)+1=a(33-2^5)+2=a(1-2^0)+3=3; - Hieronymus Fischer 
               (Hieronymus.Fischer(AT)gmx.de), Jan 22 2006
%F A000120 A fixed point of the mapping 0 -> 01, 1 -> 12, 2 -> 23, 3 -> 34, 4 -> 
               45, ... With f(i) = floor(n/2^i), a(n) is the number of odd numbers 
               in the sequence f(0), f(1), f(2), f(3), f(4), f(5), ... - DELEHAM 
               Philippe (kolotoko(AT)wanadoo.fr), Jan 04 2004
%F A000120 When read mod 2 gives the Morse-Thue sequence A010060.
%F A000120 Let floor_pow4(n) denote n rounded down to the next power of four, floor_pow4(n) 
               = 4 ^ floor(log4 n). Then a(0) = 0, a(1) = 1, a(2) = 1, a(3) = 2, 
               a(n) = a(floor(n / floor_pow4(n))) + a(n % floor_pow4(n)) - Stephen 
               K. Touset (stephen(AT)touset.org), Apr 04 2007
%F A000120 a(n)=n-sum{2<=k<=n, sum{j|n,j>=2, floor(log_2(j))-floor(log_2(j-1))}}. 
               - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Jun 18 2007
%F A000120 a(n)=A007814(C(2n,n))=1+A007814(C(2n-1,n)). [From Vladimir Shevelev (shevelev(AT)bgu.ac.il), 
               Jul 20 2009]
%e A000120 a(4) = a(0) + a(0) = 0
%e A000120 a(8) = a(2) + a(0) = 1
%e A000120 a(13) = a(3) + a(1) = 2 + 1 = 3
%e A000120 a(23) = a(1) + a(7) = 1 + a(1) + a(3) = 1 + 1 + 2 = 4
%e A000120 Gary Adamson points out (Jun 03 2009) that this can be written as a triangle:
%e A000120 .0,
%e A000120 .1,
%e A000120 .1,2,
%e A000120 .1,2,2,3,
%e A000120 .1,2,2,3,2,3,3,4,
%e A000120 .1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
%e A000120 .1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
%e A000120 .1,2,2,3,2,3,...
%e A000120 where the rows converge to A063787.
%e A000120 Contribution from Omar E. Pol (info(AT)polprimos.com), Jun 07 2009: (Start)
%e A000120 Also, triangle begins:
%e A000120 0;
%e A000120 1,1;
%e A000120 2,1,2,2;
%e A000120 3,1,2,2,3,2,3,3;
%e A000120 4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4;
%e A000120 5,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5;
%e A000120 6,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,
               3,4,...
%e A000120 (End)
%p A000120 A000120 := proc(n) local w,m,i; w := 0; m := n; while m > 0 do i := m 
               mod 2; w := w+i; m := (m-i)/2; od; w; end: wt := A000120;
%t A000120 Table[ Count[ IntegerDigits[n, 2], 1], {n, 0, 100} ]
%t A000120 Nest[ Flatten[ #1 /. a_Integer -> {a, a + 1}] &, {0}, 7] (* Robert G. 
               Wilson v Jul 27 2006 *)
%t A000120 Table[Plus @@ IntegerDigits[n, 2], {n, 0, 104}]
%o A000120 (PARI) a(n)=if(n<0,0,2*n-valuation((2*n)!,2))
%o A000120 (PARI) a(n)=if(n<0,0,subst(Pol(binary(n)),x,1))
%o A000120 (PARI) a(n)=if(n<1,0,a(n\2)+n%2) - Michael Somos Mar 06 2004
%o A000120 Common LISP: (defun floor-to-power (n pow) (declare (fixnum pow)) (expt 
               pow (floor (log n pow)))) (defun enabled-bits (n) (if (< n 4) (nth 
               n (list 0 1 1 2)) (+ (enabled-bits (floor (/ n (floor-to-power n 
               4)))) (enabled-bits (mod n (floor-to-power n 4)))))) - Stephen K. 
               Touset (stephen(AT)touset.org), Apr 04 2007
%o A000120 See link in A139351 for Fortran program.
%Y A000120 The basic sequences concerning the binary expansion of n are this one, 
               A000788, A000069, A001969, A023416, A059015, A007088.
%Y A000120 a(n)=n-A011371[n]. - Labos E. (labos(AT)ana.sote.hu), Jul 27 2000
%Y A000120 Sum of digits of n written in base 2-16: this sequence, A053735, A053737, 
               A053824, A053827, A053828, A053829, A053830, A007953, A053831, A053832, 
               A053833, A053834, A053835, A053836.
%Y A000120 Cf. A007953.
%Y A000120 This is Guy Steele's sequence GS(3, 4) (see A135416).
%Y A000120 Cf. A007814.
%Y A000120 Cf. A000079. [From Omar E. Pol (info(AT)polprimos.com), Jun 07 2009]
%Y A000120 Sequence in context: A105056 A105061 A105164 this_sequence A105062 A106487 
               A105102
%Y A000120 Adjacent sequences: A000117 A000118 A000119 this_sequence A000121 A000122 
               A000123
%K A000120 nonn,easy,core,nice
%O A000120 0,4
%A A000120 N. J. A. Sloane (njas(AT)research.att.com).
%E A000120 More terms from Stephen K. Touset (stephen(AT)touset.org), Apr 04 2007