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
Links
- 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 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.
- Alex S. A. Alochukwu, Audace A. V. Dossou-Olory, Fadekemi J. Osaye, Valisoa R. M. Rakotonarivo, Shashank Ravichandran, Sarah J. Selkirk, Hua Wang, and Hays Whitlatch, Characterization of Trees with Maximum Security, arXiv:2411.19188 [math.CO], 2024. See p. 12.
- Khodabakhsh Hessami Pilehrood and Tatiana 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
Crossrefs
Programs
-
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
-
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 *) -
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
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) = A008687(n+1) - 1.
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.: 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
Comments