This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A000120 M0105 N0041 #477 Apr 03 2025 09:42:03
%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,
%T A000120 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,1,2,2,3,
%U A000120 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,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 The binary weight of n is also called Hamming weight of n. [The term "Hamming weight" was named after the American mathematician Richard Wesley Hamming (1915-1998). - _Amiram Eldar_, Jun 16 2021]
%C A000120 a(n) is also the largest integer such that 2^a(n) divides binomial(2n, n) = A000984(n). - _Benoit Cloitre_, 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 first 2^k terms, then the next 2^k terms are a(0) + 1, a(1) + 1, ..., a(2^k-1) + 1. - _Benoit Cloitre_, 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_, 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
%C A000120 a(n) is the number of times n appears among the mystery calculator sequences: A005408, A042964, A047566, A115419, A115420, A115421. - _Jeremy Gardiner_, Jan 25 2006
%C A000120 a(n) is the 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_, 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 Sequence is given by T^(infinity)(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. - _Benoit Cloitre_, Mar 04 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. - _Vladimir Shevelev_, Jun 05 2009
%C A000120 Triangle inequality: a(k+m) <= a(k) + a(m). Equality holds if and only if C(k+m, m) is odd. - _Vladimir Shevelev_, Jul 19 2009
%C A000120 a(k*m) <= a(k) * a(m). - _Robert Israel_, Sep 03 2023
%C A000120 The number of occurrences of value k in the first 2^n terms of the sequence is equal to binomial(n, k), and also equal to the sum of the first n - k + 1 terms of column k in the array A071919. Example with k = 2, n = 7: there are 21 = binomial(7,2) = 1 + 2 + 3 + 4 + 5 + 6 2's in a(0) to a(2^7-1). - Brent Spillner (spillner(AT)acm.org), Sep 01 2010, simplified by _R. J. Mathar_, Jan 13 2017
%C A000120 Let m be the number of parts in the listing of the compositions of n as lists of parts in lexicographic order, a(k) = n - length(composition(k)) for all k < 2^n and all n (see example); A007895 gives the equivalent for compositions into odd parts. - _Joerg Arndt_, Nov 09 2012
%C A000120 From _Daniel Forgues_, Mar 13 2015: (Start)
%C A000120 Just tally up row k (binary weight equal k) from 0 to 2^n - 1 to get the binomial coefficient C(n,k). (See A007318.)
%C A000120 0 1 3 7 15
%C A000120 0: O | . | . . | . . . . | . . . . . . . . |
%C A000120 1: | O | O . | O . . . | O . . . . . . . |
%C A000120 2: | | O | O O . | O O . O . . . |
%C A000120 3: | | | O | O O O . |
%C A000120 4: | | | | O |
%C A000120 Due to its fractal nature, the sequence is quite interesting to listen to.
%C A000120 (End)
%C A000120 The binary weight of n is a particular case of the digit sum (base b) of n. - _Daniel Forgues_, Mar 13 2015
%C A000120 The mean of the first n terms is 1 less than the mean of [a(n+1),...,a(2n)], which is also the mean of [a(n+2),...,a(2n+1)]. - _Christian Perfect_, Apr 02 2015
%C A000120 a(n) is also the largest part of the integer partition having viabin number n. The viabin number of an integer partition is defined in the following way. Consider the southeast border of the Ferrers board of the integer partition and consider the binary number obtained by replacing each east step with 1 and each north step, except the last one, with 0. The corresponding decimal form is, by definition, the viabin number of the given integer partition. "Viabin" is coined from "via binary". For example, consider the integer partition [2, 2, 2, 1]. The southeast border of its Ferrers board yields 10100, leading to the viabin number 20. - _Emeric Deutsch_, Jul 20 2017
%C A000120 a(n) is also known as the population count of the binary representation of n. - _Chai Wah Wu_, May 19 2020
%D A000120 Jean-Paul Allouche and Jeffrey Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 119.
%D A000120 Donald E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.1.3, Problem 41, p. 589. - _N. J. A. Sloane_, Aug 03 2012
%D A000120 Manfred R. Schroeder, Fractals, Chaos, Power Laws. W.H. Freeman, 1991, p. 383.
%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="/A000120/b000120.txt">Table of n, a(n) for n = 0..10000</a>
%H A000120 Franklin T. Adams-Watters, and Frank Ruskey, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Ruskey2/ruskey14.html">Generating Functions for the Digital Sum and Other Digit Counting Sequences</a>, JIS, Vol. 12 (2009), Article 09.5.6.
%H A000120 J.-P. Allouche, <a href="http://math.colgate.edu/~integers/graham2/graham2.Abstract.html">On an Inequality in a 1970 Paper of R. L. Graham</a>, INTEGERS 21A (2021), #A2.
%H A000120 Jean-Paul Allouche and Jeffrey Shallit, <a href="http://dx.doi.org/10.1016/0304-3975(92)90001-V">The ring of k-regular sequences</a>, Theoretical Computer Sci., Vol. 98 (1992), pp. 163-197. (<a href="http://www.cs.uwaterloo.ca/~shallit/Papers/as0.ps">PS file on author's web page.</a>)
%H A000120 Jean-Paul Allouche, Jeffrey Shallit and Jonathan Sondow, <a href="http://arxiv.org/abs/math/0512399">Summation of Series Defined by Counting Blocks of Digits</a>, arXiv:math/0512399 [math.NT], 2005-2006.
%H A000120 Jean-Paul Allouche, Jeffrey Shallit and Jonathan Sondow, <a href="http://dx.doi.org/10.1016/j.jnt.2006.06.001">Summation of series defined by counting blocks of digits</a>, J. Number Theory, Vol. 123 (2007), pp. 133-143.
%H A000120 Richard Bellman and Harold N. Shapiro, <a href="http://www.jstor.org/stable/1969281">On a problem in additive number theory</a>, Annals Math., Vol. 49, No. 2 (1948), pp. 333-340. - _N. J. A. Sloane_, Mar 12 2009
%H A000120 C. Cobeli and A. Zaharescu, <a href="http://dx.doi.org/10.1080/10236198.2014.940337">A game with divisors and absolute differences of exponents</a>, Journal of Difference Equations and Applications, Vol. 20, #11 (2014) pp. 1489-1501, DOI: 10.1080/10236198.2014.940337. Also available as <a href="http://arxiv.org/abs/1411.1334">arXiv:1411.1334 [math.NT]</a>, 2014. See delta_n.
%H A000120 Jean Coquet, <a href="http://dx.doi.org/10.1016/0022-314X(86)90067-3">Power sums of digital sums</a>, J. Number Theory, Vol. 22, No. 2 (1986), pp. 161-176.
%H A000120 F. M. Dekking, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Dekking/dek25.html">The Thue-Morse Sequence in Base 3/2</a>, J. Int. Seq., Vol. 26 (2023), Article 23.2.3.
%H A000120 Karl Dilcher and Larry Ericksen, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p24">Hyperbinary expansions and Stern polynomials</a>, Elec. J. Combin, Vol. 22 (2015), #P2.24.
%H A000120 Josef Eschgfäller and Andrea Scarpante, <a href="http://arxiv.org/abs/1603.08500">Dichotomic random number generators</a>, arXiv:1603.08500 [math.CO], 2016.
%H A000120 Emmanuel Ferrand, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL10/Ferrand/ferrand8.html">Deformations of the Taylor Formula</a>, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.7.
%H A000120 Steven R. Finch, Pascal Sebah and Zai-Qiao Bai, <a href="http://arXiv.org/abs/0802.2654">Odd Entries in Pascal's Trinomial Triangle</a>, arXiv:0802.2654 [math.NT], 2008.
%H A000120 Philippe Flajolet, Peter Grabner, Peter Kirschenhofer, Helmut Prodinger and Robert F. Tichy, <a href="http://algo.inria.fr/flajolet/Publications/FlGrKiPrTi94.pdf">Mellin Transforms And Asymptotics: Digital Sums</a>, Theoret. Computer Sci., Vol. 123, No. 2 (1994), pp. 291-314.
%H A000120 Michael Gilleland, <a href="/selfsimilar.html">Some Self-Similar Integer Sequences</a>.
%H A000120 P. J. Grabner, P. Kirschenhofer, H. Prodinger and R. F. Tichy, <a href="https://doi.org/10.1007/978-94-011-2058-6_25">On the moments of the sum-of-digits function</a>, Applications of Fibonacci numbers, Vol. 5 (St. Andrews, 1992), Kluwer Acad. Publ., Dordrecht, 1993, 263-271.
%H A000120 Ronald L. Graham, <a href="http://dx.doi.org/10.1111/j.1749-6632.1970.tb56468.x">On primitive graphs and optimal vertex assignments</a>, Internat. Conf. Combin. Math. (New York, 1970), Annals of the NY Academy of Sciences, Vol. 175, 1970, pp. 170-186.
%H A000120 Khodabakhsh Hessami Pilehrood and Tatiana Hessami Pilehrood, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Pilehrood/pilehrood2.html">Vacca-Type Series for Values of the Generalized Euler Constant Function and its Derivative</a>, J. Integer Sequences, Vol. 13 (2010), Article 10.7.3.
%H A000120 Nick Hobson, <a href="/A000120/a000120.py.txt">Python program for this sequence</a>.
%H A000120 Kathy Q. Ji and Herbert S. Wilf, <a href="https://arxiv.org/abs/math/0611465">Extreme Palindromes</a>, arXiv:math/0611465 [math.CO], 2006.
%H A000120 Guy Louchard and Helmut Prodinger, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Prodinger/prodinger29.html">The Largest Missing Value in a Composition of an Integer and Some Allouche-Shallit-Type Identities</a>, J. Int. Seq., Vol. 16 (2013), Article 13.2.2.
%H A000120 J.-L. Mauclaire and Leo Murata, <a href="http://dx.doi.org/10.3792/pjaa.59.274">On q-additive functions, I</a>, Proc. Japan Acad. Ser. A Math. Sci., Vol. 59, No. 6 (1983), pp. 274-276.
%H A000120 J.-L. Mauclaire and Leo Murata, <a href="http://dx.doi.org/10.3792/pjaa.59.441">On q-additive functions, II</a>, Proc. Japan Acad. Ser. A Math. Sci., Vol. 59, No. 9 (1983), pp. 441-444.
%H A000120 M. D. McIlroy, <a href="http://dx.doi.org/10.1137/0203020">The number of 1's in binary integers: bounds and extremal properties</a>, SIAM J. Comput., Vol. 3 (1974), pp. 255-261.
%H A000120 Kerry Mitchell, <a href="http://kerrymitchellart.com/articles/Spirolateral-Type_Images_from_Integer_Sequences.pdf">Spirolateral-Type Images from Integer Sequences</a>, 2013.
%H A000120 Sam Northshield, <a href="http://www.jstor.org/stable/10.4169/000298910X496714">Stern's Diatomic Sequence 0,1,1,2,1,3,2,3,1,4,...</a>, Amer. Math. Month., Vol. 117, No. 7 (2010), pp. 581-598.
%H A000120 Theophanes E. Raptis, <a href="https://arxiv.org/abs/1805.06341">Finite Information Numbers through the Inductive Combinatorial Hierarchy</a>, arXiv:1805.06301 [physics.gen-ph], 2018.
%H A000120 Carlo Sanna, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Sanna/sanna3.html">On Arithmetic Progressions of Integers with a Distinct Sum of Digits</a>, Journal of Integer Sequences, Vol. 15 (2012), Article 12.8.1. - _N. J. A. Sloane_, Dec 29 2012
%H A000120 Nanci Smith, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/4-4/elementary4-4.pdf">Problem B-82</a>, Fib. Quart., Vol. 4, No. 4 (1966), pp. 374-375.
%H A000120 Jonathan Sondow, <a href="https://doi.org/10.1007/978-0-387-68361-4_23">New Vacca-type rational series for Euler's constant and its "alternating" analog ln 4/Pi</a>, arXiv:<a href="https://arxiv.org/abs/math/0508042">math/0508042</a> [math.NT] 2005; Additive Number Theory, D. and G. Chudnovsky, eds., Springer, 2010, pp. 331-340.
%H A000120 Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences with (relatively) simple ordinary generating functions</a>, 2004.
%H A000120 Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>.
%H A000120 Ralf Stephan, <a href="https://arxiv.org/abs/math/0307027">Divide-and-conquer generating functions. I. Elementary sequences</a>, arXiv:math/0307027 [math.CO], 2003.
%H A000120 Kenneth B. Stolarsky, <a href="http://dx.doi.org/10.1137/0132060">Power and exponential sums of digital sums related to binomial coefficient parity</a>, SIAM J. Appl. Math., Vol. 32 (1977), pp. 717-730. See B(n). - _N. J. A. Sloane_, Apr 05 2014
%H A000120 J. R. Trollope, <a href="http://www.jstor.org/stable/2687954">An explicit expression for binary digital sums</a>, Math. Mag., Vol. 41, No. 1 (1968), pp. 21-25.
%H A000120 Robert Walker, <a href="http://robertinventor.com/ftswiki/Self_Similar_Sloth_Canon_Number_Sequences">Self Similar Sloth Canon Number Sequences</a>.
%H A000120 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Binary.html">Binary</a>, <a href="https://mathworld.wolfram.com/DigitCount.html">Digit Count</a>, <a href="https://mathworld.wolfram.com/Stolarsky-HarborthConstant.html">Stolarsky-Harborth Constant</a>, <a href="https://mathworld.wolfram.com/DigitSum.html">Digit Sum</a>.
%H A000120 Wikipedia, <a href="https://en.wikipedia.org/wiki/Hamming_weight">Hamming weight</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="/index/Cor#core">Index entries for "core" sequences</a>
%H A000120 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%H A000120 <a href="/index/Coi#Colombian">Index entries for Colombian or self numbers and related sequences</a>
%H A000120 <a href="/index/Fi#FIXEDPOINTS">Index entries for sequences that are fixed points of mappings</a>
%F A000120 a(0) = 0, a(2*n) = a(n), a(2*n+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) = log_2(A001316(n)) = 2n - A005187(n) = A070939(n) - A023416(n). - _Henry Bottomley_, Apr 04 2001; corrected by _Ralf Stephan_, Apr 15 2002
%F A000120 a(n) = log_2(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_, Oct 19 2002
%F A000120 a(n) = n - Sum_{k>=1} 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_, Apr 19 2003
%F A000120 a(0) = 0, a(n) = a(n - 2^floor(log_2(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_, 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), ... - _Philippe Deléham_, 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_{k=2..n} Sum_{j|n, j >= 2} (floor(log_2(j)) - floor(log_2(j-1))). - _Hieronymus Fischer_, Jun 18 2007
%F A000120 a(n) = A138530(n, 2) for n > 1. - _Reinhard Zumkeller_, Mar 26 2008
%F A000120 a(A077436(n)) = A159918(A077436(n)); a(A000290(n)) = A159918(n). - _Reinhard Zumkeller_, Apr 25 2009
%F A000120 a(n) = A063787(n) - A007814(n). - _Gary W. Adamson_, Jun 04 2009
%F A000120 a(n) = A007814(C(2n, n)) = 1 + A007814(C(2n-1, n)). - _Vladimir Shevelev_, Jul 20 2009
%F A000120 For odd m >= 1, a((4^m-1)/3) = a((2^m+1)/3) + (m-1)/2 (mod 2). - _Vladimir Shevelev_, Sep 03 2010
%F A000120 a(n) - a(n-1) = { 1 - a(n-1) if and only if A007814(n) = a(n-1), 1 if and only if A007814(n) = 0, -1 for all other A007814(n) }. - Brent Spillner (spillner(AT)acm.org), Sep 01 2010
%F A000120 a(A001317(n)) = 2^a(n). - _Vladimir Shevelev_, Oct 25 2010
%F A000120 a(n) = A139351(n) + A139352(n) = Sum_k {A030308(n, k)}. - _Philippe Deléham_, Oct 14 2011
%F A000120 From _Hieronymus Fischer_, Jun 10 2012: (Start)
%F A000120 a(n) = Sum_{j = 1..m+1} (floor(n/2^j + 1/2) - floor(n/2^j)), where m = floor(log_2(n)).
%F A000120 General formulas for the number of digits >= d in the base p representation of n, where 1 <= d < p: a(n) = Sum_{j = 1..m+1} (floor(n/p^j + (p-d)/p) - floor(n/p^j)), where m=floor(log_p(n)); g.f.: g(x) = (1/(1-x))*Sum_{j>=0} (x^(d*p^j) - x^(p*p^j))/(1-x^(p*p^j)). (End)
%F A000120 a(n) = A213629(n, 1) for n > 0. - _Reinhard Zumkeller_, Jul 04 2012
%F A000120 a(n) = A240857(n,n). - _Reinhard Zumkeller_, Apr 14 2014
%F A000120 a(n) = log_2(C(2*n,n) - (C(2*n,n) AND C(2*n,n)-1)). - _Gary Detlefs_, Jul 10 2014
%F A000120 Sum_{n >= 1} a(n)/2n(2n+1) = (gamma + log(4/Pi))/2 = A344716, where gamma is Euler's constant A001620; see Sondow 2005, 2010 and Allouche, Shallit, Sondow 2007. - _Jonathan Sondow_, Mar 21 2015
%F A000120 For any integer base b >= 2, the sum of digits s_b(n) of expansion base b of n is the solution of this recurrence relation: s_b(n) = 0 if n = 0 and s_b(n) = s_b(floor(n/b)) + (n mod b). Thus, a(n) satisfies: a(n) = 0 if n = 0 and a(n) = a(floor(n/2)) + (n mod 2). This easily yields a(n) = Sum_{i = 0..floor(log_2(n))} (floor(n/2^i) mod 2). From that one can compute a(n) = n - Sum_{i = 1..floor(log_2(n))} floor(n/2^i). - _Marek A. Suchenek_, Mar 31 2016
%F A000120 Sum_{k>=1} a(k)/2^k = 2 * Sum_{k >= 0} 1/(2^(2^k)+1) = 2 * A051158. - _Amiram Eldar_, May 15 2020
%F A000120 Sum_{k>=1} a(k)/(k*(k+1)) = A016627 = log(4). - _Bernard Schott_, Sep 16 2020
%F A000120 a(m*(2^n-1)) >= n. Equality holds when 2^n-1 >= A000265(m), but also in some other cases, e.g., a(11*(2^2-1)) = 2 and a(19*(2^3-1)) = 3. - _Pontus von Brömssen_, Dec 13 2020
%F A000120 G.f.: A(x) satisfies A(x) = (1+x)*A(x^2) + x/(1-x^2). - _Akshat Kumar_, Nov 04 2023
%e A000120 Using the formula a(n) = a(floor(n / floor_pow4(n))) + a(n mod floor_pow4(n)):
%e A000120 a(4) = a(1) + a(0) = 1,
%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 W. 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 From _Joerg Arndt_, Nov 09 2012: (Start)
%e A000120 Connection to the compositions of n as lists of parts (see comment):
%e A000120 [ #]: a(n) composition
%e A000120 [ 0]: [0] 1 1 1 1 1
%e A000120 [ 1]: [1] 1 1 1 2
%e A000120 [ 2]: [1] 1 1 2 1
%e A000120 [ 3]: [2] 1 1 3
%e A000120 [ 4]: [1] 1 2 1 1
%e A000120 [ 5]: [2] 1 2 2
%e A000120 [ 6]: [2] 1 3 1
%e A000120 [ 7]: [3] 1 4
%e A000120 [ 8]: [1] 2 1 1 1
%e A000120 [ 9]: [2] 2 1 2
%e A000120 [10]: [2] 2 2 1
%e A000120 [11]: [3] 2 3
%e A000120 [12]: [2] 3 1 1
%e A000120 [13]: [3] 3 2
%e A000120 [14]: [3] 4 1
%e A000120 [15]: [4] 5
%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;
%p A000120 A000120 := n -> add(i, i=convert(n,base,2)): # _Peter Luschny_, Feb 03 2011
%p A000120 with(Bits): p:=n->ilog2(n-And(n,n-1)): seq(p(binomial(2*n,n)),n=0..200) # _Gary Detlefs_, Jan 27 2019
%t A000120 Table[DigitCount[n, 2, 1], {n, 0, 105}]
%t A000120 Nest[Flatten[# /. # -> {#, # + 1}] &, {0}, 7] (* _Robert G. Wilson v_, Sep 27 2011 *)
%t A000120 Table[Plus @@ IntegerDigits[n, 2], {n, 0, 104}]
%t A000120 Nest[Join[#, # + 1] &, {0}, 7] (* _IWABUCHI Yu(u)ki_, Jul 19 2012 *)
%t A000120 Log[2, Nest[Join[#, 2#] &, {1}, 14]] (* gives 2^14 term, _Carlos Alves_, Mar 30 2014 *)
%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 (PARI) a(n)=my(v=binary(n));sum(i=1,#v,v[i]) \\ _Charles R Greathouse IV_, Jun 24 2011
%o A000120 (PARI) a(n)=norml2(binary(n)) \\ better use {A000120=hammingweight}. - _M. F. Hasler_, Oct 09 2012, edited Feb 27 2020
%o A000120 (PARI) a(n)=hammingweight(n) \\ _Michel Marcus_, Oct 19 2013
%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) (n-th 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 (Fortran) c See link in A139351
%o A000120 (Haskell)
%o A000120 import Data.Bits (Bits, popCount)
%o A000120 a000120 :: (Integral t, Bits t) => t -> Int
%o A000120 a000120 = popCount
%o A000120 a000120_list = 0 : c [1] where c (x:xs) = x : c (xs ++ [x,x+1])
%o A000120 -- _Reinhard Zumkeller_, Aug 26 2013, Feb 19 2012, Jun 16 2011, Mar 07 2011
%o A000120 (Haskell)
%o A000120 a000120 = concat r
%o A000120 where r = [0] : (map.map) (+1) (scanl1 (++) r)
%o A000120 -- _Luke Palmer_, Feb 16 2014
%o A000120 (SageMath)
%o A000120 def A000120(n):
%o A000120 if n <= 1: return Integer(n)
%o A000120 return A000120(n//2) + n%2
%o A000120 [A000120(n) for n in range(105)] # _Peter Luschny_, Nov 19 2012
%o A000120 (SageMath) def A000120(n) : return sum(n.digits(2)) # _Eric M. Schmidt_, Apr 26 2013
%o A000120 (Python) def A000120(n): return bin(n).count('1') # _Chai Wah Wu_, Sep 03 2014
%o A000120 (Python)
%o A000120 import numpy as np
%o A000120 A000120 = np.array([0], dtype="uint8")
%o A000120 for bitrange in range(25): A000120 = np.append(A000120, np.add(A000120, 1))
%o A000120 print([A000120[n] for n in range(0, 105)]) # _Karl-Heinz Hofmann_, Nov 07 2022
%o A000120 (Python) def A000120(n): return n.bit_count() # Requires Python 3.10 or higher. - _Pontus von Brömssen_, Nov 08 2022
%o A000120 (Python) # Also see links.
%o A000120 (Scala) (0 to 127).map(Integer.bitCount(_)) // _Alonso del Arte_, Mar 05 2019
%o A000120 (Magma) [Multiplicity(Intseq(n, 2), 1): n in [0..104]]; // _Marius A. Burtea_, Jan 22 2020
%o A000120 (Magma) [&+Intseq(n, 2):n in [0..104]]; // _Marius A. Burtea_, Jan 22 2020
%Y A000120 The basic sequences concerning the binary expansion of n are this one, A000788, A000069, A001969, A023416, A059015, A007088.
%Y A000120 Partial sums see A000788. For run lengths see A131534. See also A001792, A010062.
%Y A000120 Number of 0's in n: A023416 and A080791.
%Y A000120 a(n) = n - A011371(n).
%Y A000120 Sum of digits of n written in bases 2-16: this sequence, A053735, A053737, A053824, A053827, A053828, A053829, A053830, A007953, A053831, A053832, A053833, A053834, A053835, A053836.
%Y A000120 Cf. A001620, A344716, A007814, A063787.
%Y A000120 This is Guy Steele's sequence GS(3, 4) (see A135416).
%Y A000120 Cf. A055640, A055641, A102669-A102685, A117804, A122840, A122841, A160093, A160094, A196563, A196564 (for base 10).
%Y A000120 Cf. A230952 (boustrophedon transform).
%Y A000120 Cf. A070939 (length of binary representation of n).
%K A000120 nonn,easy,core,nice,hear,look,base
%O A000120 0,4
%A A000120 _N. J. A. Sloane_