A023416 - OEIS

%I #106 Dec 05 2024 12:57:29

%S 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,

%T 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,

%U 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

%N Number of 0's in binary expansion of n.

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

%H N. J. A. Sloane, <a href="/A023416/b023416.txt">Table of n, a(n) for n = 0..10000</a>

%H 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 12 (2009) 09.5.6.

%H Jean-Paul Allouche and Jeffrey O. Shallit, <a href="http://dx.doi.org/10.1112/jlms/s2-39.2.193">Infinite products associated with counting blocks in binary strings</a>, J. London Math. Soc.39 (1989) 193-204.

%H Jean-Paul Allouche and Jeffrey Shallit, <a href="https://doi.org/10.1007/BFb0097122">Sums of digits and the Hurwitz zeta function</a>, in: K. Nagasaka and E. Fouvry (eds.), Analytic Number Theory, Lecture Notes in Mathematics, Vol. 1434, Springer, Berlin, Heidelberg, 1990, pp. 19-30.

%H 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, <a href="https://arxiv.org/abs/2411.19188">Characterization of Trees with Maximum Security</a>, arXiv:2411.19188 [math.CO], 2024. See p. 12.

%H 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, 13 (2010), Article 10.7.3.

%H Vladimir Shevelev, <a href="http://www.emis.de/journals/INTEGERS/papers/m1/m1.Abstract.html">The number of permutations with prescribed up-down structure as a function of two variables</a>, INTEGERS, Vol. 12 (2012), #A1. - From _N. J. A. Sloane_, Feb 07 2013

%H Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences with (relatively) simple ordinary generating functions</a>, 2004.

%H Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>.

%H Ralf Stephan, <a href="http://arXiv.org/abs/math.CO/0307027">Divide-and-conquer generating functions. I. Elementary sequences</a>, arXiv:math/0307027 [math.CO], 2003.

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

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

%F a(n) = 1 - (n mod 2) + a(floor(n/2)). - _Marc LeBrun_, Jul 12 2001

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

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

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

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

%F From _Hieronymus Fischer_, Jun 12 2012: (Start)

%F 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)).

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

%F 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)).

%F 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)

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

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

%p A023416 := proc(n)

%p     if n = 0 then

%p         1;

%p     else

%p         add(1-e,e=convert(n,base,2)) ;

%p     end if;

%p end proc: # _R. J. Mathar_, Jul 21 2012

%t Table[ Count[ IntegerDigits[n, 2], 0], {n, 0, 100} ]

%t DigitCount[Range[0,110],2,0] (* _Harvey P. Dale_, Jan 10 2013 *)

%o (Haskell)

%o a023416 0 = 1

%o a023416 1 = 0

%o a023416 n = a023416 n' + 1 - m where (n', m) = divMod n 2

%o a023416_list = 1 : c [0] where c (z:zs) = z : c (zs ++ [z+1,z])

%o -- _Reinhard Zumkeller_, Feb 19 2012, Jun 16 2011, Mar 07 2011

%o (PARI) a(n)=if(n==0,1,n=binary(n); sum(i=1, #n, !n[i])) \\ _Charles R Greathouse IV_, Jun 10 2011

%o (PARI) a(n)=if(n==0,1,#binary(n)-hammingweight(n)) \\ _Charles R Greathouse IV_, Nov 20 2012

%o (PARI) a(n) = if(n == 0, 1, 1+logint(n,2) - hammingweight(n))  \\ _Gheorghe Coserea_, Sep 01 2015

%o (Python)

%o def A023416(n): return n.bit_length()-n.bit_count() if n else 1 # _Chai Wah Wu_, Mar 13 2023

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

%Y With initial zero and shifted right, same as A080791.

%Y Cf. A055641 (for base 10), A188859.

%K nonn,nice,easy,base

%O 0,5

%A _David W. Wilson_