A023416 Number of 0's in binary expansion of n.

1, 0, 1, 0, 2, 1, 1, 0, 3, 2, 2, 1, 2, 1, 1, 0, 4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0, 5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1, 4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0, 6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2, 5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1, 5, 4, 4, 3, 4, 3, 3, 2, 4

Offset

0,5

Comments

Another version (A080791) has a(0) = 0.

Links

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

F. T. Adams-Watters and F. Ruskey, Generating Functions for the Digital Sum and Other Digit Counting Sequences, JIS 12 (2009) 09.5.6.

Jean-Paul Allouche and Jeffrey O. Shallit, Infinite products associated with counting blocks in binary strings, J. London Math. Soc.39 (1989) 193-204.

Jean-Paul Allouche and Jeffrey Shallit, Sums of digits and the Hurwitz zeta function, in: K. Nagasaka and E. Fouvry (eds.), Analytic Number Theory, Lecture Notes in Mathematics, Vol. 1434, Springer, Berlin, Heidelberg, 1990, pp. 19-30.

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

Vladimir Shevelev, The number of permutations with prescribed up-down structure as a function of two variables, INTEGERS, Vol. 12 (2012), #A1. - From N. J. A. Sloane, Feb 07 2013

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.

Index entries for sequences related to binary expansion of n

Formula

a(n) = 1, if n = 0; 0, if n = 1; a(n/2)+1 if n even; a((n-1)/2) if n odd.

a(n) = 1 - (n mod 2) + a(floor(n/2)). - Marc LeBrun, Jul 12 2001

G.f.: 1 + 1/(1-x) * Sum_{k>=0} x^(2^(k+1))/(1+x^2^k). - Ralf Stephan, Apr 15 2002

a(n) = A070939(n) - A000120(n).

a(n) = A008687(n+1) - 1.

a(n) = A000120(A035327(n)).

From Hieronymus Fischer, Jun 12 2012: (Start)

a(n) = m + 1 + Sum_{j=1..m+1} (floor(n/2^j) - floor(n/2^j + 1/2)), where m=floor(log_2(n)).

General formulas for the number of digits <= d in the base p representation n, where 0 <= d < p.

a(n) = m + 1 + Sum_{j=1..m+1} (floor(n/p^j) - floor(n/p^j + (p-d-1)/p)), where m=floor(log_p(n)).

G.f.: g(x) = 1 + (1/(1-x))*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)

Product_{n>=1} ((2*n)/(2*n+1))^((-1)^a(n)) = sqrt(2)/2 (A010503) (see Allouche & Shallit link). - Michel Marcus, Aug 31 2014

Sum_{n>=1} a(n)/(n*(n+1)) = 2 - 2*log(2) (A188859) (Allouche and Shallit, 1990). - Amiram Eldar, Jun 01 2021

Maple

A023416 := proc(n)
    if n = 0 then
        1;
    else
        add(1-e, e=convert(n, base, 2)) ;
    end if;
end proc: # R. J. Mathar, Jul 21 2012

Mathematica

Table[ Count[ IntegerDigits[n, 2], 0], {n, 0, 100} ]
DigitCount[Range[0, 110], 2, 0] (* Harvey P. Dale, Jan 10 2013 *)

Prog

(Haskell)
a023416 0 = 1
a023416 1 = 0
a023416 n = a023416 n' + 1 - m where (n', m) = divMod n 2
a023416_list = 1 : c [0] where c (z:zs) = z : c (zs ++ [z+1, z])
-- Reinhard Zumkeller, Feb 19 2012, Jun 16 2011, Mar 07 2011
(PARI) a(n)=if(n==0, 1, n=binary(n); sum(i=1, #n, !n[i])) \\ Charles R Greathouse IV, Jun 10 2011
(PARI) a(n)=if(n==0, 1, #binary(n)-hammingweight(n)) \\ Charles R Greathouse IV, Nov 20 2012
(PARI) a(n) = if(n == 0, 1, 1+logint(n, 2) - hammingweight(n))  \\ Gheorghe Coserea, Sep 01 2015
(Python)
def A023416(n): return n.bit_length()-n.bit_count() if n else 1 # Chai Wah Wu, Mar 13 2023

Crossrefs

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

With initial zero and shifted right, same as A080791.

Cf. A055641 (for base 10), A188859.

Sequence in context: A050606 A352521 A277721 * A080791 A336361 A364260

Adjacent sequences: A023413 A023414 A023415 * A023417 A023418 A023419

Keyword

nonn,nice,easy,base

Author

David W. Wilson

Status

approved