A102669 -id:A102669 - cp's OEIS frontend

A000120 1's-counting sequence: number of 1's in binary expansion of n (or the binary weight of n).

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

Offset: 0

N. J. A. Sloane

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]
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 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
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) is the number of times n appears among the mystery calculator sequences: A005408, A042964, A047566, A115419, A115420, A115421. - Jeremy Gardiner, Jan 25 2006
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
The first appearance of k, k >= 0, is at a(2^k-1). - Robert G. Wilson v, Jul 27 2006
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
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
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
a(k*m) <= a(k) * a(m). - Robert Israel, Sep 03 2023
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
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
From Daniel Forgues, Mar 13 2015: (Start)
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.)
     0   1       3               7                              15
  0: O | . | .   . | .   .   .   . | .   .   .   .   .   .   .   . |
  1:   | O | O   . | O   .   .   . | O   .   .   .   .   .   .   . |
  2:   |   |     O |     O   O   . |     O   O   .   O   .   .   . |
  3:   |   |       |             O |             O       O   O   . |
  4:   |   |       |               |                             O |
Due to its fractal nature, the sequence is quite interesting to listen to.
(End)
The binary weight of n is a particular case of the digit sum (base b) of n. - Daniel Forgues, Mar 13 2015
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
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
a(n) is also known as the population count of the binary representation of n. - Chai Wah Wu, May 19 2020

			Using the formula a(n) = a(floor(n / floor_pow4(n))) + a(n mod floor_pow4(n)):
  a(4) = a(1) + a(0) = 1,
  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 _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)

Jean-Paul Allouche and Jeffrey Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 119.
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
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).

N. J. A. Sloane, Table of n, a(n) for n = 0..10000
Franklin T. Adams-Watters, and Frank Ruskey, Generating Functions for the Digital Sum and Other Digit Counting Sequences, JIS, Vol. 12 (2009), Article 09.5.6.
J.-P. Allouche, On an Inequality in a 1970 Paper of R. L. Graham, INTEGERS 21A (2021), #A2.
Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Sci., Vol. 98 (1992), pp. 163-197. (PS file on author's web page.)
Jean-Paul Allouche, Jeffrey Shallit and Jonathan Sondow, Summation of Series Defined by Counting Blocks of Digits, arXiv:math/0512399 [math.NT], 2005-2006.
Jean-Paul Allouche, Jeffrey Shallit and Jonathan Sondow, Summation of series defined by counting blocks of digits, J. Number Theory, Vol. 123 (2007), pp. 133-143.
Richard Bellman and Harold N. Shapiro, On a problem in additive number theory, Annals Math., Vol. 49, No. 2 (1948), pp. 333-340. - _N. J. A. Sloane_, Mar 12 2009
C. Cobeli and A. Zaharescu, A game with divisors and absolute differences of exponents, Journal of Difference Equations and Applications, Vol. 20, #11 (2014) pp. 1489-1501, DOI: 10.1080/10236198.2014.940337. Also available as arXiv:1411.1334 [math.NT], 2014. See delta_n.
Jean Coquet, Power sums of digital sums, J. Number Theory, Vol. 22, No. 2 (1986), pp. 161-176.
F. M. Dekking, The Thue-Morse Sequence in Base 3/2, J. Int. Seq., Vol. 26 (2023), Article 23.2.3.
Karl Dilcher and Larry Ericksen, Hyperbinary expansions and Stern polynomials, Elec. J. Combin, Vol. 22 (2015), #P2.24.
Josef Eschgfäller and Andrea Scarpante, Dichotomic random number generators, arXiv:1603.08500 [math.CO], 2016.
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 [math.NT], 2008.
Philippe Flajolet, Peter Grabner, Peter Kirschenhofer, Helmut Prodinger and Robert F. Tichy, Mellin Transforms And Asymptotics: Digital Sums, Theoret. Computer Sci., Vol. 123, No. 2 (1994), pp. 291-314.
Michael Gilleland, Some Self-Similar Integer Sequences.
P. J. Grabner, P. Kirschenhofer, H. Prodinger and R. F. Tichy, On the moments of the sum-of-digits function, Applications of Fibonacci numbers, Vol. 5 (St. Andrews, 1992), Kluwer Acad. Publ., Dordrecht, 1993, 263-271.
Ronald L. Graham, On primitive graphs and optimal vertex assignments, Internat. Conf. Combin. Math. (New York, 1970), Annals of the NY Academy of Sciences, Vol. 175, 1970, pp. 170-186.
Khodabakhsh Hessami Pilehrood and Tatiana Hessami Pilehrood, Vacca-Type Series for Values of the Generalized Euler Constant Function and its Derivative, J. Integer Sequences, Vol. 13 (2010), Article 10.7.3.
Nick Hobson, Python program for this sequence.
Kathy Q. Ji and Herbert S. Wilf, Extreme Palindromes, arXiv:math/0611465 [math.CO], 2006.
Guy Louchard and Helmut Prodinger, The Largest Missing Value in a Composition of an Integer and Some Allouche-Shallit-Type Identities, J. Int. Seq., Vol. 16 (2013), Article 13.2.2.
J.-L. Mauclaire and Leo Murata, On q-additive functions, I, Proc. Japan Acad. Ser. A Math. Sci., Vol. 59, No. 6 (1983), pp. 274-276.
J.-L. Mauclaire and Leo Murata, On q-additive functions, II, Proc. Japan Acad. Ser. A Math. Sci., Vol. 59, No. 9 (1983), pp. 441-444.
M. D. McIlroy, The number of 1's in binary integers: bounds and extremal properties, SIAM J. Comput., Vol. 3 (1974), pp. 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, No. 7 (2010), pp. 581-598.
Theophanes E. Raptis, Finite Information Numbers through the Inductive Combinatorial Hierarchy, arXiv:1805.06301 [physics.gen-ph], 2018.
Carlo Sanna, On Arithmetic Progressions of Integers with a Distinct Sum of Digits, Journal of Integer Sequences, Vol. 15 (2012), Article 12.8.1. - _N. J. A. Sloane_, Dec 29 2012
Nanci Smith, Problem B-82, Fib. Quart., Vol. 4, No. 4 (1966), pp. 374-375.
Jonathan Sondow, New Vacca-type rational series for Euler's constant and its "alternating" analog ln 4/Pi, arXiv:math/0508042 [math.NT] 2005; Additive Number Theory, D. and G. Chudnovsky, eds., Springer, 2010, pp. 331-340.
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions, 2004.
Ralf Stephan, Table of generating functions.
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
Kenneth B. Stolarsky, Power and exponential sums of digital sums related to binomial coefficient parity, SIAM J. Appl. Math., Vol. 32 (1977), pp. 717-730. See B(n). - _N. J. A. Sloane_, Apr 05 2014
J. R. Trollope, An explicit expression for binary digital sums, Math. Mag., Vol. 41, No. 1 (1968), pp. 21-25.
Robert Walker, Self Similar Sloth Canon Number Sequences.
Eric Weisstein's World of Mathematics, Binary, Digit Count, Stolarsky-Harborth Constant, Digit Sum.
Wikipedia, Hamming weight.
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
Index entries for sequences that are fixed points of mappings

The basic sequences concerning the binary expansion of n are this one, A000788, A000069, A001969, A023416, A059015, A007088.
Partial sums see A000788. For run lengths see A131534. See also A001792, A010062.
Number of 0's in n: A023416 and A080791.
a(n) = n - A011371(n).
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. A001620, A344716, A007814, A063787.
This is Guy Steele's sequence GS(3, 4) (see A135416).
Cf. A055640, A055641, A102669-A102685, A117804, A122840, A122841, A160093, A160094, A196563, A196564 (for base 10).
Cf. A230952 (boustrophedon transform).
Cf. A070939 (length of binary representation of n).

Fortran
```
c See link in A139351
```

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

a000120 = concat r
    where r = [0] : (map.map) (+1) (scanl1 (++) r)
-- Luke Palmer, Feb 16 2014

[Multiplicity(Intseq(n, 2), 1): n in [0..104]]; // Marius A. Burtea, Jan 22 2020

[&+Intseq(n, 2):n in [0..104]]; // Marius A. Burtea, Jan 22 2020

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 := n -> add(i, i=convert(n,base,2)): # Peter Luschny, Feb 03 2011
with(Bits): p:=n->ilog2(n-And(n,n-1)): seq(p(binomial(2*n,n)),n=0..200) # Gary Detlefs, Jan 27 2019

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 *)

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

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

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

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

a(n)=norml2(binary(n)) \\ better use {A000120=hammingweight}. - M. F. Hasler, Oct 09 2012, edited Feb 27 2020

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

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

import numpy as np
A000120 = np.array([0], dtype="uint8")
for bitrange in range(25): A000120 = np.append(A000120, np.add(A000120, 1))
print([A000120[n] for n in range(0, 105)]) # Karl-Heinz Hofmann, Nov 07 2022

def A000120(n): return n.bit_count() # Requires Python 3.10 or higher. - Pontus von Brömssen, Nov 08 2022

Python
```
# Also see links.
```

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

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

(0 to 127).map(Integer.bitCount()) // _Alonso del Arte, Mar 05 2019

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) = log_2(A001316(n)) = 2n - A005187(n) = A070939(n) - A023416(n). - Henry Bottomley, Apr 04 2001; corrected by Ralf Stephan, Apr 15 2002
a(n) = log_2(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>=1} 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^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
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_{k=2..n} Sum_{j|n, j >= 2} (floor(log_2(j)) - floor(log_2(j-1))). - Hieronymus Fischer, Jun 18 2007
a(n) = A138530(n, 2) for n > 1. - Reinhard Zumkeller, Mar 26 2008
a(A077436(n)) = A159918(A077436(n)); a(A000290(n)) = A159918(n). - Reinhard Zumkeller, Apr 25 2009
a(n) = A063787(n) - A007814(n). - Gary W. Adamson, Jun 04 2009
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
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) = A213629(n, 1) for n > 0. - Reinhard Zumkeller, Jul 04 2012
a(n) = A240857(n,n). - Reinhard Zumkeller, Apr 14 2014
a(n) = log_2(C(2*n,n) - (C(2*n,n) AND C(2*n,n)-1)). - Gary Detlefs, Jul 10 2014
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
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
Sum_{k>=1} a(k)/2^k = 2 * Sum_{k >= 0} 1/(2^(2^k)+1) = 2 * A051158. - Amiram Eldar, May 15 2020
Sum_{k>=1} a(k)/(k*(k+1)) = A016627 = log(4). - Bernard Schott, Sep 16 2020
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
G.f.: A(x) satisfies A(x) = (1+x)*A(x^2) + x/(1-x^2). - Akshat Kumar, Nov 04 2023

A055642 Number of digits in the decimal expansion of n.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3

Offset: 0

Henry Bottomley, Jun 06 2000

From Hieronymus Fischer, Jun 08 2012: (Start)
For n > 0 the first differences of A117804.
The total number of digits necessary to write down all the numbers 0, 1, 2, ..., n is A117804(n+1). (End)
Here a(0) = 1, but a different common convention is to consider that the expansion of 0 in any base b > 0 has 0 terms and digits. - M. F. Hasler, Dec 07 2018

			Examples:
999: 1 + floor(log_10(999)) = 1 + floor(2.x) = 1 + 2 = 3 or
      ceiling(log_10(999+1)) = ceiling(log_10(1000)) = ceiling(3) = 3;
1000: 1 + floor(log_10(1000)) = 1 + floor(3) = 1 + 3 = 4 or
      ceiling(log_10(1000+1)) = ceiling(log_10(1001)) = ceiling(3.x) = 4;
1001: 1 + floor(log_10(1001)) = 1 + floor(3.x) = 1 + 3 = 4 or
      ceiling(log_10(1001+1)) = ceiling(log_10(1002)) = ceiling(3.x) = 4;

Charles R Greathouse IV, Table of n, a(n) for n = 0..10000

Cf. A043537, A178788, A046034, A019546, A054899, A122840, A055640, A055641, A102669-A102685, A117804, A160093, A160094, A196563, A196564, A000120, A000788, A023416, A059015 (for base 2).
Cf. A262190, A262198.
Cf. A007953: sum of digits.

a055642 :: Integer -> Int
a055642 = length . show  -- Reinhard Zumkeller, Feb 19 2012, Apr 26 2011

[ #Intseq(n): n in [0..105] ];   //  Bruno Berselli, Jun 30 2011
(Common Lisp) (defun A055642 (n) (if (zerop n) 1 (floor (log n 10)))) ; James Spahlinger, Oct 13 2012

A055642 := proc(n)
        max(1,ilog10(n)+1) ;
end proc:  # R. J. Mathar, Nov 30 2011

Join[{1}, Array[ Floor[ Log[10, 10# ]] &, 104]] (* Robert G. Wilson v, Jan 04 2006 *)
Join[{1},Table[IntegerLength[n],{n,104}]]
IntegerLength[Range[0,120]] (* Harvey P. Dale, Jul 02 2016 *)

a(n)=#Str(n) \\ M. F. Hasler, Nov 17 2008

A055642(n)=logint(n+!n,10)+1 \\ Increasingly faster than the above, for larger n. (About twice as fast for n ~ 10^7.) - M. F. Hasler, Dec 07 2018

def a(n): return len(str(n))
print([a(n) for n in range(121)]) # Michael S. Branicky, May 10 2022

def A055642(n): # Faster than len(str(n)) from ~ 50 digits on
    L = math.log10(n or 1)
    if L.is_integer() and 10**int(L)>n: return int(L or 1)
    return int(L)+1  # M. F. Hasler, Apr 08 2024

a(A046760(n)) < A050252(A046760(n)); a(A046759(n)) > A050252(A046759(n)). - Reinhard Zumkeller, Jun 21 2011
a(n) = A196563(n) + A196564(n).
a(n) = 1 + floor(log_10(n)) = 1 + A004216(n) = ceiling(log_10(n+1)) = A004218(n+1), if n >= 1. - Daniel Forgues, Mar 27 2014
a(A046758(n)) = A050252(A046758(n)). - Reinhard Zumkeller, Jun 21 2011
a(n) = A117804(n+1) - A117804(n), n > 0. - Hieronymus Fischer, Jun 08 2012
G.f.: g(x) = 1 + (1/(1-x))*Sum_{j>=0} x^(10^j). - Hieronymus Fischer, Jun 08 2012
a(n) = A262190(n) for n < 100; a(A262198(n)) != A262190(A262198(n)). - Reinhard Zumkeller, Sep 14 2015

A000788 Total number of 1's in binary expansions of 0, ..., n.

Original entry on oeis.org

0, 1, 2, 4, 5, 7, 9, 12, 13, 15, 17, 20, 22, 25, 28, 32, 33, 35, 37, 40, 42, 45, 48, 52, 54, 57, 60, 64, 67, 71, 75, 80, 81, 83, 85, 88, 90, 93, 96, 100, 102, 105, 108, 112, 115, 119, 123, 128, 130, 133, 136, 140, 143, 147, 151, 156, 159, 163, 167, 172, 176, 181, 186

Offset: 0

N. J. A. Sloane

Partial sums of A000120.
The graph of this sequence is a version of the Takagi curve: see Lagarias (2012), Section 9, especially Theorem 9.1. - N. J. A. Sloane, Mar 12 2016
a(n-1) is the largest possible number of ordered pairs (a,b) such that a/b is a prime in a subset of the positive integers with n elements. - Yifan Xie, Feb 21 2025

J.-P. Allouche & J. Shallit, Automatic sequences, Cambridge University Press, 2003, p. 94
R. Bellman and H. N. Shapiro, On a problem in additive number theory, Annals Math., 49 (1948), 333-340. See Eq. 1.9. [From N. J. A. Sloane, Mar 12 2009]
L. E. Bush, An asymptotic formula for the average sums of the digits of integers, Amer. Math. Monthly, 47 (1940), pp. 154-156. [From the bibliography of Stolarsky, 1977]
P. Cheo and S. Yien, A problem on the k-adic representation of positive integers (Chinese; English summary), Acta Math. Sinica, 5 (1955), pp. 433-438. [From the bibliography of Stolarsky, 1977]
M. P. Drazin and J. S. Griffith, On the decimal representation of integers, Proc. Cambridge Philos. Soc., (4), 48 (1952), pp. 555-565. [From the bibliography of Stolarsky, 1977]
E. N. Gilbert, Games of identification or convergence, SIAM Review, 4 (1962), 16-24.
Grabner, P. J.; Kirschenhofer, P.; Prodinger, H.; 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.
E. Grosswald, Properties of some arithmetic functions, J. Math. Anal. Appl., 28 (1969), pp.405-430.
Donald E. Knuth, The Art of Computer Programming, volume 3 Sorting and Searching, section 5.3.4, subsection Bitonic sorting, with C'(p) = a(p-1).
Hiu-Fai Law, Spanning tree congestion of the hypercube, Discrete Math., 309 (2009), 6644-6648 (see p(m) on page 6647).
Z. Li and E. M. Reingold, Solution of a divide-and-conquer maximin recurrence, SIAM J. Comput., 18 (1989), 1188-1200.
B. Lindström, On a combinatorial problem in number theory, Canad. Math. Bull., 8 (1965), 477-490.
Mauclaire, J.-L.; Murata, Leo; On q-additive functions. I. Proc. Japan Acad. Ser. A Math. Sci. 59 (1983), no. 6, 274-276.
Mauclaire, J.-L.; Murata, Leo; 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.
L. Mirsky, A theorem on representations of integers in the scale of r, Scripta Math., 15 (1949), pp. 11-12.
I. Shiokawa, On a problem in additive number theory, Math. J. Okayama Univ., 16 (1974), pp.167-176. [From the bibliography of Stolarsky, 1977]
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).
K. B. Stolarsky, Power and exponential sums of digital sums related to binomial coefficient parity, SIAM J. Appl. Math., 32 (1977), 717-730.
Trollope, J. R. An explicit expression for binary digital sums. Math. Mag. 41 1968 21-25.

T. D. Noe and Hieronymus Fischer, Table of n, a(n) for n = 0..10000 (terms up to n=1000 by T. D. Noe).
G. Agnarsson, On the number of hypercubic bipartitions of an integer, arXiv preprint arXiv:1106.4997 [math.CO], 2011.
G. Agnarsson, Induced subgraphs of hypercubes, arXiv preprint arXiv:1112.3015 [math.CO], 2011.
G. Agnarsson and K. Lauria, Extremal subgraphs of the d-dimensional grid graph, arXiv preprint arXiv:1302.6517 [math.CO], 2013.
J.-P. Allouche, On an Inequality in a 1970 Paper of R. L. Graham, INTEGERS 21A (2021), #A2.
Mathias Hauan Arbo, Esten Ingar Grøtli, and Jan Tommy Gravdahl, CASCLIK: CasADi-Based Closed-Loop Inverse Kinematics, arXiv:1901.06713 [cs.RO], 2019.
Venkata Sai Narayana Bavisetty, Matthew Wheeler, Reinhard Laubenbacher, and Claus Kadelka, Upper bound for the stability of Boolean networks, arXiv:2506.12310 [q-bio.MN], 2025. See p. 8.
Johann Cigler, A curious class of Hankel determinants, arXiv:1803.05164 [math.CO], 2018.
G. F. Clements and B. Lindström, A sequence of (+-1) determinants with large values, Proc. Amer. Math. Soc., 16 (1965), pp. 548-550. [From the bibliography of Stolarsky, 1977]
Jean Coquet, Power sums of digital sums, J. Number Theory 22 (1986), no. 2, 161-176.
H. Delange, Sur la fonction sommatoire de la fonction "somme des chiffres", Enseignement Math., (2), 21 (1975), pp. 31-47. [From the bibliography of Stolarsky, 1977]
Laurent Feuilloley, Brief Announcement: Average Complexity for the LOCAL Model, arXiv preprint arXiv:1505.05072 [cs.DC], 2015.
S. R. Finch, P. Sebah and Z.-Q. Bai, Odd Entries in Pascal's Trinomial Triangle, arXiv:0802.2654 [math.NT], 2008.
Oscar E. González, An observation of Rankin on Hankel determinants, Department of Mathematics, University of Illinois at Urbana-Champaign, 2018.
P. J. Grabner and H.-K. Hwang, Digital sums and divide-and-conquer recurrences: Fourier expansions and absolute convergence
Milton W. Green, Letter to N. J. A. Sloane, 1973 (note "A360" refers to N0360 which is the present sequence).
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint 2016.
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 36 and 44.
Jeffrey C. Lagarias, The Takagi function and its properties, arXiv:1112.4205 [math.CA], 2011-2012.
Jeffrey C. Lagarias, The Takagi function and its properties, In Functions in number theory and their probabilistic aspects, 153--189, RIMS Kôkyûroku Bessatsu, B34, Res. Inst. Math. Sci. (RIMS), Kyoto, 2012. MR3014845.
Julien Leroy, Michel Rigo, and Manon Stipulanti, Behavior of Digital Sequences Through Exotic Numeration Systems, Electronic Journal of Combinatorics 24(1) (2017), #P1.44.
Raoul Nakhmanson-Kulish, Graphic representation of K(n)=a(n)/(n log2(n)/2) from n=63 to 131071
D. J. Newman, On the number of binary digits in a multiple of three, Proc. Amer. Math. Soc., 21 (1969), pp. 719-721. [From the bibliography of Stolarsky, 1977]
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
S. C. Tang, An improvement and generalization of Bellman-Shapiro's theorem on a problem in additive number theory, Proc. Amer. Math. Soc., 14 (1963), pp. 199-204. [From the bibliography of Stolarsky, 1977]
Eric Weisstein's World of Mathematics, Binary
David W. Wilson, Fast C++ function for computing a(n)
Index entries for sequences related to binary expansion of n

For number of 0's in binary expansion of 0, ..., n see A059015.
The basic sequences concerning the binary expansion of n are A000120, A000788, A000069, A001969, A023416, A059015, A070939, A083652.
Cf. A005183, A360189.
Cf. A027868, A037123, A054899, A055640, A055641, A102669-A102685, A117804, A122840, A122841, A160093, A160094, A196563, A196564 (for base 10).

a000788_list = scanl1 (+) A000120_list
-- Walt Rorie-Baety, Jun 30 2012

{a000788 0 = 0; a00788 n = a000788 n2 + a000788 (n-n2-1) + (n-n2) where n2 = n `div` 2}
-- Walt Rorie-Baety, Jul 15 2012

a:= proc(n) option remember; `if`(n=0, 0, a(n-1)+add(i, i=Bits[Split](n))) end:
seq(a(n), n=0..62);  # Alois P. Heinz, Nov 11 2024

a[n_] := Count[ Table[ IntegerDigits[k, 2], {k, 0, n}], 1, 2]; Table[a[n], {n, 0, 62}] (* Jean-François Alcover, Dec 16 2011 *)
Table[Plus@@Flatten[IntegerDigits[Range[n], 2]], {n, 0, 62}] (* Alonso del Arte, Dec 16 2011 *)
Accumulate[DigitCount[Range[0,70],2,1]] (* Harvey P. Dale, Jun 08 2013 *)

A000788(n)={ n<3 && return(n); if( bittest(n,0) \\
, n+1 == 1<A000788(n>>1)*2+n>>1+1 \\
, n == 1<A000788(n>>=1)+A000788(n-1)+n )} \\ M. F. Hasler, Nov 22 2009

a(n)=sum(k=1,n,hammingweight(k)) \\ Charles R Greathouse IV, Oct 04 2013

a(n) = if (n==0, 0, m = logint(n, 2); r = n % 2^m; m*2^(m-1) + r + 1 + a(r)); \\ Michel Marcus, Mar 27 2018

a(n)={n++; my(t, i, s); c=n; while(c!=0, i++; c\=2); for(j=1, i, d=(n\2^(i-j))%2; t+=(2^(i-j)*(s*d+d*(i-j)/2)); s+=d); t} \\ David A. Corneth, Nov 26 2024
(C++) /* See David W. Wilson link. */

def A000788(n): return sum(i.bit_count() for i in range(1,n+1)) # Chai Wah Wu, Mar 01 2023

def A000788(n): return (n+1)*n.bit_count()+(sum((m:=1<>j)-(r if n<<1>=m*(r:=k<<1|1) else 0)) for j in range(1,n.bit_length()+1))>>1) # Chai Wah Wu, Nov 11 2024

McIlroy (1974) gives bounds and recurrences. - N. J. A. Sloane, Mar 24 2014
Stolarsky (1977) studies the asymptotics, and gives at least nine references to earlier work on the problem. I have added all the references that were not here already. - N. J. A. Sloane, Apr 06 2014
a(n) = Sum_{k=1..n} A000120(k). - Benoit Cloitre, Dec 19 2002
a(0) = 0, a(2n) = a(n)+a(n-1)+n, a(2n+1) = 2a(n)+n+1. - Ralf Stephan, Sep 13 2003
a(n) = n*log_2(n)/2 + O(n); a(2^n)=n*2^(n-1)+1. - Benoit Cloitre, Sep 25 2003 (The first result is due to Bellman and Shapiro, - N. J. A. Sloane, Mar 24 2014)
a(n) = n*log_2(n)/2+n*F(log_2(n)) where F is a nowhere differentiable continuous function of period 1 (see Allouche & Shallit). - Benoit Cloitre, Jun 08 2004
G.f.: (1/(1-x)^2) * Sum_{k>=0} x^2^k/(1+x^2^k). - Ralf Stephan, Apr 19 2003
a(2^n-1) = A001787(n) = n*2^(n-1). - M. F. Hasler, Nov 22 2009
a(4^n-2) = n(4^n-2).
For real n, let f(n) = [n]/2 if [n] even, n-[n+1]/2 otherwise. Then a(n) = Sum_{k>=0} 2^k*f((n+1)/2^k).
a(A000225(n)) = A173921(A000225(n)) = A001787(n); a(A000079(n)) = A005183(n). - Reinhard Zumkeller, Mar 04 2010
From Hieronymus Fischer, Jun 10 2012: (Start)
a(n) = (1/2)*Sum_{j=1..m+1} (floor(n/2^j + 1/2)*(2n + 2 - floor(n/2^j + 1/2))*2^j - floor(n/2^j)*(2n + 2 - (1 + floor(n/2^j)) * 2^j)), where m=floor(log_2(n)).
a(n) = (n+1)*A000120(n) - 2^(m-1) + 1/4 + (1/2)*Sum_{j=1..m+1} ((floor(n/2^j) + 1/2)^2 - floor(n/2^j + 1/2)^2)*2^j, where m=floor(log_2(n)).
a(2^m-1) = m*2^(m-1).
(This is the total number of '1' digits occurring in all the numbers with <= m bits.)
Generic formulas for the number of digits >= d in the base p representations of all integers from 0 to n, where 1<= d < p.
a(n) = (1/2)*Sum_{j=1..m+1} (floor(n/p^j + (p-d)/p)*(2n + 2 + ((p-2*d)/p - floor(n/p^j + (p-d)/p))*p^j) - floor(n/p^j)*(2n + 2 - (1+floor(n/p^j)) * p^j)), where m=floor(log_p(n)).
a(n) = (n+1)*F(n,p,d) + (1/2)*Sum_{j=1..m+1} ((((p-2*d)/p)*floor(n/p^j+(p-d)/p) + floor(n/p^j))*p^j - (floor(n/p^j+(p-d)/p)^2 - floor(n/p^j)^2)*p^j), where m=floor(log_p(n)) and F(n,p,d) = number of digits >= d in the base p representation of n.
a(p^m-1) = (p-d)*m*p^(m-1).
(This is the total number of digits >= d occurring in all the numbers  with <= m digits in base p representation.)
G.f.: g(x) = (1/(1-x)^2)*Sum_{j>=0} (x^(d*p^j) - x^(p*p^j))/(1-x^(p*p^j)). (End)
a(n) = Sum_{k=1..n} A000120(A240857(n,k)). - Reinhard Zumkeller, Apr 14 2014
For n > 0, if n is written as 2^m + r with 0 <= r < 2^m, then a(n) = m*2^(m-1) + r + 1 + a(r). - Shreevatsa R, Mar 20 2018
a(n) = n*(n+1)/2 + Sum_{k=1..floor(n/2)} ((2k-1)((g(n,k)-1)*2^(g(n,k) + 1) + 2) - (n+1)*(g(n,k)+1)*g(n,k)/2), where g(n,k) = floor(log_2(n/(2k-1))). - Fabio Visonà, Mar 17 2020
From Jeffrey Shallit, Aug 07 2021: (Start)
A 2-regular sequence, satisfying the identities
a(4n+1) = -a(2n) + a(2n+1) + a(4n)
a(4n+2) = -2a(2n) + 2a(2n+1) + a(4n)
a(4n+3) = -4a(n) + 4a(2n+1)
a(8n) = 4a(n) - 8a(2n) + 5a(4n)
a(8n+4) = -9a(2n) + 5a(2n+1) + 4a(4n)
for n>=0. (End)
a(n) = Sum_{k=0..floor(log_2(n+1))} k * A360189(n,k). - Alois P. Heinz, Mar 06 2023

More terms from Larry Reeves (larryr(AT)acm.org), Jan 15 2001

A055641 Number of zero digits in n.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 1, 1, 1, 1

Offset: 0

Henry Bottomley, Jun 06 2000

			a(99) = 0 because the digits of 99 are 9 and 9, a(100) = 2 because the digits of 100 are 1, 0 and 0 and there are two 0's.

Hieronymus Fischer, Table of n, a(n) for n = 0..10000

Cf. A011540, A004719, A052382, A054899, A055640, A102669-A102685, A122840, A160093, A160094, A196563, A195564, A000120, A000788, A023416, A059015 (for base 2), A085974.

a055641 n | n < 10    = 0 ^ n
          | otherwise = a055641 n' + 0 ^ d where (n',d) = divMod n 10
-- Reinhard Zumkeller, Apr 30 2013

Array[Last@ DigitCount@ # &, 105] (* Michael De Vlieger, Jul 02 2015 *)

a(n)=if(n,n=digits(n); sum(i=2,#n,n[i]==0), 1) \\ Charles R Greathouse IV, Sep 13 2015

A055641(n)=#select(d->!d,digits(n))+!n \\ M. F. Hasler, Jun 22 2018

def a(n): return str(n).count("0")
print([a(n) for n in range(106)]) # Michael S. Branicky, May 26 2022

From Hieronymus Fischer, Jun 06 2012: (Start)
a(n) = m + 1 - A055640(n) = Sum_{j=1..m+1} (1 + floor(n/10^j) - floor(n/10^j+0.9)), where m = floor(log_10(n)).
G.f.: g(x) = 1 + (1/(1-x))*Sum_{j>=0} (x^(10*10^j) - x^(11*10^j))/(1-x^10^(j+1)). (End)
a(n) = if n<10 then A000007(n) else a(A059995(n)) + A000007(A010879(n)). - Reinhard Zumkeller, Apr 30 2013, corrected by M. F. Hasler, Jun 22 2018

A196564 Number of odd digits in decimal representation of n.

Original entry on oeis.org

0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 0, 1, 0, 1, 0, 1

Offset: 0

Reinhard Zumkeller, Oct 04 2011

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Zachary P. Bradshaw and Christophe Vignat, Dubious Identities: A Visit to the Borwein Zoo, arXiv:2307.05565 [math.HO], 2023.

Cf. A014261, A014263, A027868, A046034, A055640, A055641, A055642, A061217, A102669-A102685, A122640, A196563.

a196564 n = length [d | d <- show n, d `elem` "13579"]
-- Reinhard Zumkeller, Feb 22 2012, Oct 04 2011

A196564 := proc(n)
        if n =0 then
                0;
        else
                convert(n,base,10) ;
                add(d mod 2,d=%) ;
        end if:
end proc: # R. J. Mathar, Jul 13 2012

Table[Total[Mod[IntegerDigits[n],2]],{n,0,100}] (* Zak Seidov, Oct 13 2015 *)

a(n) = #select(x->x%2, digits(n)); \\ Michel Marcus, Oct 14 2015

def a(n): return sum(1 for d in str(n) if d in "13579")
print([a(n) for n in range(100)]) # Michael S. Branicky, May 15 2022

a(n) = A055642(n) - A196563(n);
a(A014263(n)) = 0; a(A007957(n)) > 0.
From Hieronymus Fischer, May 30 2012: (Start)
a(n) = Sum_{j=0..m} (floor(n/(2*10^j) + (1/2)) - floor(n/(2*10^j))), where m=floor(log_10(n)).
a(10*n+k) = a(n) + a(k), 0<=k<10, n>=0.
a(n) = a(floor(n/10)) + a(n mod 10), n>=0.
a(n) = Sum_{j=0..m} a(floor(n/10^j) mod 10), n>=0.
a(A014261(n)) = floor(log_5(4*n+1)), n>0.
G.f.: g(x) = (1/(1-x))*Sum_{j>=0} x^10^j/(1+x^10^j). (End)

A196563 Number of even digits in decimal representation of n.

Original entry on oeis.org

1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 2, 1, 2, 1, 2, 1

Offset: 0

Reinhard Zumkeller, Oct 04 2011

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Zachary P. Bradshaw and Christophe Vignat, Dubious Identities: A Visit to the Borwein Zoo, arXiv:2307.05565 [math.HO], 2023.

Cf. A014261, A014263, A027868, A046034, A055640, A055641, A055642, A061217, A102669-A102685, A122640, A196564.

a196563 n = length [d | d <- show n, d `elem` "02468"]
-- Reinhard Zumkeller, Feb 22 2012, Oct 04 2011

A196563 := proc(n)
        if n =0 then
                1;
        else
                convert(n,base,10) ;
                add(1-(d mod 2),d=%) ;
        end if:
end proc: # R. J. Mathar, Jul 13 2012

Table[Count[Mod[IntegerDigits[n],2],0][n],{n,0,100}] (* Zak Seidov, Oct 13 2015 *)
Table[Count[IntegerDigits[n],?EvenQ],{n,0,120}] (* _Harvey P. Dale, Feb 22 2020 *)

a(n) = #select(x->(!(x%2)), if (n, digits(n), [0])); \\ Michel Marcus, Oct 14 2015

def a(n): return sum(1 for d in str(n) if d in "02468")
print([a(n) for n in range(100)]) # Michael S. Branicky, May 15 2022

a(n) = A055642(n) - A196564(n);
a(A014261(n)) = 0; a(A007928(n)) > 0.
From Hieronymus Fischer, May 30 2012: (Start)
a(n) = Sum_{j=0..m} (1 + floor(n/(2*10^j)) - floor(n/(2*10^j) + (1/2))), where m=floor(log_10(n)).
a(10*n+k) = a(n) + a(k), 0<=k<10, n>=1.
a(n) = a(floor(n/10))+a(n mod 10), n>=10.
a(n) = Sum_{j=0..m} a(floor(n/10^j) mod 10), n>=0.
a(A014263(n)) = 1 + floor(log_5(n-1)), n>1.
G.f.: g(x) = 1 + (1/(1-x))*Sum_{j>=0} x^(2*10^j)/(1+x^10^j). (End)

A059015 Total number of 0's in binary expansions of 0, ..., n.

Original entry on oeis.org

1, 1, 2, 2, 4, 5, 6, 6, 9, 11, 13, 14, 16, 17, 18, 18, 22, 25, 28, 30, 33, 35, 37, 38, 41, 43, 45, 46, 48, 49, 50, 50, 55, 59, 63, 66, 70, 73, 76, 78, 82, 85, 88, 90, 93, 95, 97, 98, 102, 105, 108, 110, 113, 115, 117, 118, 121, 123, 125, 126, 128, 129, 130, 130, 136, 141

Offset: 0

Patrick De Geest, Dec 15 2000

Partial sums of A023416. - Reinhard Zumkeller, Jul 15 2011

The graph of this sequence is a version of the Takagi curve: see Lagarias (2012), Section 9, especially Theorem 9.1. - N. J. A. Sloane, Mar 12 2016

T. D. Noe and Hieronymus Fischer, Table of n, a(n) for n = 0..10000 (terms up to n=1023 by T. D. Noe)
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint 2016.
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
Jeffrey C. Lagarias, The Takagi function and its properties, arXiv:1112.4205 [math.CA], 2011-2012.
Jeffrey C. Lagarias, The Takagi function and its properties, In Functions in number theory and their probabilistic aspects, 153--189, RIMS Kôkyûroku Bessatsu, B34, Res. Inst. Math. Sci. (RIMS), Kyoto, 2012. MR3014845.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Index entries for sequences related to binary expansion of n

The basic sequences concerning the binary expansion of n are A000120, A000788, A000069, A001969, A023416, A059015, A070939, A083652.

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

a059015 n = a059015_list !! n
a059015_list = scanl1 (+) $ map a023416 [0..]
-- Reinhard Zumkeller, Jul 15 2011

a:= proc(n) option remember; `if`(n=0, 1, a(n-1)+add(1-i, i=Bits[Split](n))) end:
seq(a(n), n=0..65);  # Alois P. Heinz, Nov 11 2024

Accumulate[ Table[ Count[ IntegerDigits[n, 2], 0], {n, 0, 65}]] (* Jean-François Alcover, Oct 03 2012 *)
Accumulate[DigitCount[Range[0,70],2,0]] (* Harvey P. Dale, Jun 24 2017 *)

v=vector(100,i,1);for(i=1,#v-1,v[i+1] = v[i] + #binary(i) - hammingweight(i)); v \\ Charles R Greathouse IV, Nov 20 2012

a(n)=if(n, my(m=logint(n,2)); 2 + (m+1)*(n+1) - 2^(m+1) + sum(j=1,m+1, my(t=floor(n/2^j + 1/2)); (n>>j)*(2*n + 2 - (1 + (n>>j))<Charles R Greathouse IV, Dec 14 2015

def A059015(n): return 2+(n+1)*(m:=(n+1).bit_length())-(1<Chai Wah Wu, Mar 01 2023

def A059015(n): return 2+(n+1)*((t:=(n+1).bit_length())-n.bit_count())-(1<>j)-(r if n<<1>=m*(r:=k<<1|1) else 0)) for j in range(1,n.bit_length()+1))>>1) # Chai Wah Wu, Nov 11 2024

a(n) = b(n)+1, with b(2n) = b(n)+b(n-1)+n, b(2n+1) = 2b(n)+n. - Ralf Stephan, Sep 13 2003
From Hieronymus Fischer, Jun 10 2012: (Start)
With m = floor(log_2(n)):
a(n) = 2 + (m+1)*(n+1) - 2^(m+1) + (1/2)*Sum_{j=1..m+1} (floor(n/2^j)*(2*n + 2 - (1 + floor(n/2^j))*2^j) - floor(n/2^j + 1/2)*(2*n + 2 - floor(n/2^j + 1/2)*2^j)).
a(n) = A083652(n) - (n+1)*A000120(n) + 2^(m-1) - (1/4) + (1/2)*sum_{j=1..m+1} (floor(n/2^j + 1/2)^2 - (floor(n/2^j) + 1/2)^2)*2^j.
a(2^m-1) = 2 + (m-2)*2^(m-1)
(this is the total number of zero digits occurring in all the numbers with <= m places).
G.f.: 1/(1 - x) + (1/(1 - x)^2)*Sum_{j>=0} x^(2*2^j)/(1 + x^(2^j)); corrected by Ilya Gutkovskiy, Mar 28 2018
General formulas for the number of digits <= d in the base p representations of all integers from 0 to n, where 0 <= d < p.
With m = floor(log_p(n)):
a(n) = 1 + (m+1)*(n+1) - (p^(m+1)-1)/(p-1) + (1/2)*sum_{j=1..m+1} (floor(n/p^j)*(2n + 2 - (1 + floor(n/p^j))*p^j) - floor(n/p^j + (p-d-1)/p)*(2n + 2 + ((p-2*d-2)/p - floor(n/p^j + (p-d-1)/p))*p^j)).
a(n) = H(n,p) - (n+1)*F(n,p,d+1) + (1/2)*sum_{j=1..m+1} ((floor(n/p^j + (p-d-1)/p)^2 - floor(n/p^j)^2)*p^j - (((p - 2*d-2)/p)*floor(n/p^j + (p-d-1)/p) + floor(n/p^j))*p^j), where H(n,p) = sum of number of digits in the base p representations of 0 to n and F(n,p,d) = number of digits >=d in the base p representation of n.
a(p^m-1) = 1 + (d+1)*m*p^(m-1) - (p^m-1)/(p-1).
(this is the total number of digits <= d occurring in all the numbers with <= m places in base p representation).
G.f.: 1/(1-x) + (1/(1-x)^2)*Sum_{j>=0} ((1-x^(d*p^j))*x^p^j + (1-x^p^j)*x^p^(j+1)/(1-x^p^(j+1))). (End)

cp's OEIS Frontend

A000120 1's-counting sequence: number of 1's in binary expansion of n (or the binary weight of n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Fortran

Haskell

Haskell

Magma

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

PARI

PARI

Python

Python

Python

Python

SageMath

SageMath

Scala

Formula

A055642 Number of digits in the decimal expansion of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Python

Formula

A000788 Total number of 1's in binary expansions of 0, ..., n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Haskell

Maple

Mathematica

PARI

PARI

PARI

PARI

Python

Python

Formula

Extensions

A055641 Number of zero digits in n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell