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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000120 1's-counting sequence: number of 1's in binary expansion of n (or the binary weight of n).
(Formerly M0105 N0041)
707
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, 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, 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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

The binary weight of n is also called Hamming weight of n.

a(n) is also the largest integer such that 2^a(n) divides binomial(2n, n) = A000984(n) - Benoit Cloitre, Mar 27 2002

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

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

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

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

a(n) = number of times n appears among the mystery calculator sequences: A005408, A042964, A047566, A115419, A115420, A115421. - Jeremy Gardiner, Jan 25 2006

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, Jan 31 2006

The first appearance of k, k => 0, is at a(2^k-1). - Robert G. Wilson v, Jul 27 2006

a(n) = A138530(n, 2) for n > 1. - Reinhard Zumkeller, Mar 26 2008

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. - Benoit Cloitre, Mar 04 2009

a(A077436(n)) = A159918(A077436(n)); a(A000290(n)) = A159918(n). - Reinhard Zumkeller, Apr 25 2009

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

a(n) = A063787(n) - A007814(n). - Gary W. Adamson, Jun 04 2009

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

The number of occurrences of value k in the first 2^n terms of A000120 is equal to the sum of the first n-k terms of the sequence T(k, i), where T(0, i) = 1, 0, 0, 0, 0, 0, ... (A000007), T(0, i) = 1, 1, 1, 1, 1, 1, ... (A000012), T(2, i) = 1, 2, 3, 4, 5, 6, ... (A000027), T(3, i) = 1, 3, 6, 10, 15, ... (A000217), T(4, i) = 1, 4, 10, 20, 35 ... (A000292), and in general T(u, 1) = 1; T(1, v) = 0 for v > 1; T(u, v) = T(u, v-1) + T(u-1, v) for u, v > 1. - Brent Spillner (spillner(AT)acm.org), Sep 01 2010

a(n) = A213629(n, 1) for n > 0. - Reinhard Zumkeller, Jul 04 2012

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

a(n) = A240857(n,n). - Reinhard Zumkeller, Apr 14 2014

REFERENCES

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 119.

D. 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

Manfred R. Schroeder, Fractals, Chaos, Power Laws. W.H. Freeman, 1991, p. 383.

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

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

LINKS

N. J. A. Sloane, Table of n, a(n) for n = 0..10000

J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.

J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.

R. Bellman and H. N. Shapiro, On a problem in additive number theory, Annals Math., 49 (1948), 333-340. - N. J. A. Sloane, Mar 12 2009

Jean Coquet, Power sums of digital sums, J. Number Theory 22 (1986), no. 2, 161-176.

Emmanuel Ferrand, Deformations of the Taylor Formula, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.7.

Steven R. Finch, Pascal Sebah and Zai-Qiao Bai, Odd Entries in Pascal's Trinomial Triangle (arXiv:0802.2654)

P. Flajolet et al., Mellin Transforms And Asymptotics: Digital Sums, Theoret. Computer Sci. 23 (1994), 291-314.

Michael Gilleland, Some Self-Similar Integer Sequences

P. J. Grabner, P. Kirschenhofer, H. Prodinger, R. F. Tichy, R. F., On the moments of the sum-of-digits function, Applications of Fibonacci numbers, Vol. 5 (St. Andrews, 1992), 263-271, Kluwer Acad. Publ., Dordrecht, 1993.

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

K. Hessami Pilehrood, T. Hessami Pilehrood, Vacca-Type Series for Values of the Generalized Euler Constant Function and its Derivative, J. Integer Sequences, 13 (2010), #10.7.3.

Nick Hobson, Python program for this sequence

Kathy Q. Ji and Herbert S. Wilf, Extreme Palindromes

J.-L. Mauclaire, Leo Murata, On q-additive functions, I, Proc. Japan Acad. Ser. A Math. Sci. 59 (1983), no. 6, 274-276.

J.-L. Mauclaire, Leo Murata, On q-additive functions, II, Proc. Japan Acad. Ser. A Math. Sci. 59 (1983), no. 9, 441-444.

M. D. McIlroy, The number of 1's in binary integers: bounds and extremal properties, SIAM J. Comput., 3 (1974), 255-261.

Kerry Mitchell, Spirolateral-Type Images from Integer Sequences, 2013

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.

C. Sanna, On Arithmetic Progressions of Integers with a Distinct Sum of Digits, Journal of Integer Sequences, Vol. 15 (2012), #12.8.1. - N. J. A. Sloane, Dec 29 2012

Nanci Smith, Problem B-82, Fib. Quart., 4 (1966), 374-375.

R. Stephan, Some divide-and-conquer sequences ...

R. Stephan, Table of generating functions

R. Stephan, Divide-and-conquer generating functions. I. Elementary sequences

K. B. Stolarsky, Power and exponential sums of digital sums related to binomial coefficient parity, SIAM J. Appl. Math., 32 (1977), 717-730. See B(n). - N. J. A. Sloane, Apr 05 2014

J. R. Trollope, An explicit expression for binary digital sums, Math. Mag. 41 1968 21-25.

Robert Walker, Self Similar Sloth Canon Number Sequences

Eric Weisstein's World of Mathematics, Binary, Digit Count, Stolarsky-Harborth Constant, Digit Sum.

Wolfram Research, Numbers in Pascal's triangle

Index entries for "core" sequences

Index entries for sequences related to binary expansion of n

Index entries for Colombian or self numbers and related sequences

FORMULA

a(0) = 0, a(2*n) = a(n), a(2*n+1) = a(n) + 1.

a(0) = 0, a(2^i) = 1; otherwise if n = 2^i + j with 0 < j < 2^i, a(n) = a(j) + 1.

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

a(n) = a(n-1) + 1 - A007814(n) = log2[A001316(n)] = 2n - A005187(n) = A070939(n) - A023416(n). - Henry Bottomley, Apr 04 2001; corrected by Ralf Stephan, Apr 15 2002

a(n) = log2(A000984(n)/A001790(n) ). - Benoit Cloitre, Oct 02 2002

For n > 0, a(n) = n - sum(k = 1, n, A007814(k)). - Benoit Cloitre, Oct 19 2002

a(n) = n - sum(k > 0, floor(n/2^k)) = n - A011371(n). - Benoit Cloitre, Dec 19 2002

G.f.: 1/(1-x) * Sum(k >= 0, x^(2^k)/(1+x^(2^k))). - Ralf Stephan, Apr 19 2003

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, Jan 22 2006

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

When read mod 2 gives the Morse-Thue sequence A010060.

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

a(n) = n - sum{2 <= k <= n, sum{j|n, j >= 2, floor(log_2(j)) - floor(log_2(j-1))}}. - Hieronymus Fischer, Jun 18 2007

a(n) = A007814(C(2n, n)) = 1 + A007814(C(2n-1, n)). - Vladimir Shevelev, Jul 20 2009

For odd m >= 1, a((4^m-1)/3) = a((2^m+1)/3) + (m-1)/2 (mod 2). - Vladimir Shevelev, Sep 03 2010

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

a(A001317(n)) = 2^a(n). - Vladimir Shevelev, Oct 25 2010

a(n) = A139351(n) + A139352(n) = Sum_k {A030308(n, k)}. - Philippe Deléham, Oct 14 2011

Contribution from Hieronymus Fischer, Jun 10 2012 (Start):

  a(n) = sum_{j = 1..m+1} (floor(n/2^j + 1/2)) - floor(n/2^j)), where m = floor(log_2(n)). 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)

a(n) = log_2(C(2*n,n) - (C(2*n,n) AND C(2*n,n)-1)),n< 61. - Gary Detlefs, Jul 10 2014

EXAMPLE

a(4) = a(0) + a(0) = 0

a(8) = a(2) + a(0) = 1

a(13) = a(3) + a(1) = 2 + 1 = 3

a(23) = a(1) + a(7) = 1 + a(1) + a(3) = 1 + 1 + 2 = 4

Gary W. Adamson points out (Jun 03 2009) that this can be written as a triangle:

.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,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,...

where the rows converge to A063787.

From Omar E. Pol, Jun 07 2009: (Start)

Also, triangle begins:

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,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,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,...

(End)

From Joerg Arndt, Nov 09 2012: (Start)

Connection to the compositions of n as lists of parts (see comment):

[ #]:   a(n)  composition

[ 0]:   [0]   1 1 1 1 1

[ 1]:   [1]   1 1 1 2

[ 2]:   [1]   1 1 2 1

[ 3]:   [2]   1 1 3

[ 4]:   [1]   1 2 1 1

[ 5]:   [2]   1 2 2

[ 6]:   [2]   1 3 1

[ 7]:   [3]   1 4

[ 8]:   [1]   2 1 1 1

[ 9]:   [2]   2 1 2

[10]:   [2]   2 2 1

[11]:   [3]   2 3

[12]:   [2]   3 1 1

[13]:   [3]   3 2

[14]:   [3]   4 1

[15]:   [4]   5

(End)

MAPLE

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;

A000120 := proc(n) add(i, i=convert(n, base, 2)) end: # Peter Luschny, Feb 03 2011

MATHEMATICA

Table[ DigitCount[n, 2, 1], {n, 0, 105}]

Nest[ Flatten[# /. # -> {#, # + 1}] &, {0}, 7] (* Robert G. Wilson v, Sep 27 2011 *)

Table[Plus @@ IntegerDigits[n, 2], {n, 0, 104}]

Nest[Join[#, # + 1] &, {0}, 7] (* IWABUCHI Yu(u)ki, Jul 19 2012 *)

Log[2, Nest[Join[#, 2#]&, {1}, 14]] (* gives 2^14 term, Carlos Alves, Mar 30 2014 *)

PROG

(PARI) {a(n) = if( n<0, 0, 2*n - valuation((2*n)!, 2))};

(PARI) {a(n) = if( n<0, 0, subst(Pol(binary(n)), x , 1))};

(PARI) {a(n) = if( n<1, 0, a(n\2) + n%2)}; /* Michael Somos, Mar 06 2004 */

(PARI) a(n)=my(v=binary(n)); sum(i=1, #v, v[i]) \\ Charles R Greathouse IV, Jun 24 2011

(PARI) A000120(n)=norml2(binary(n))  \\ M. F. Hasler, Oct 09 2012

(PARI) a(n)=hammingweight(n) \\ Michel Marcus, Oct 19 2013

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

See link in A139351 for Fortran program.

(Haskell)

import Data.Bits (Bits, popCount)

a000120 :: (Integral t, Bits t) => t -> Int

a000120 = popCount

a000120_list = 0 : c [1] where c (x:xs) = x : c (xs ++ [x, x+1])

-- Reinhard Zumkeller, Aug 26 2013, Feb 19 2012, Jun 16 2011, Mar 07 2011

(Haskell)

a000120 = concat r

    where r = [0] : (map.map) (+1) (scanl (++) r)

-- Luke Palmer, Feb 16 2014

(Sage)

def A000120(n):

    if n <= 1: return Integer(n)

    return A000120(n//2) + n%2

[A000120(n) for n in range(105)]  # Peter Luschny, Nov 19 2012

(Sage) def A000120(n) : return sum(n.digits(2)) # Eric M. Schmidt, Apr 26 2013

(Python)

def A000120(n):

....return bin(n).count('1') # Chai Wah Wu, Sep 03 2014

CROSSREFS

The basic sequences concerning the binary expansion of n are this one, A000788, A000069, A001969, A023416, A059015, A007088.

Partial sums see A000788. See also A001792, A010062.

0's counting sequence see A023416.

a(n) = n - A011371(n). - Labos Elemer, Jul 27 2000

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.

Cf. A007953.

This is Guy Steele's sequence GS(3, 4) (see A135416).

Cf. A007814.

Cf. A055640, A055641, A102669-A102685, A117804, A122840, A122841, A160093, A160094, A196563, A196564 (for base 10).

Cf. A230952 (boustrophedon transform).

Sequence in context: A105056 A105061 A105164 * A105062 A106487 A105102

Adjacent sequences:  A000117 A000118 A000119 * A000121 A000122 A000123

KEYWORD

nonn,easy,core,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Stephen K. Touset (stephen(AT)touset.org), Apr 04 2007

STATUS

approved

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 October 24 20:16 EDT 2014. Contains 248516 sequences.