|
%I #101 Mar 14 2023 03:36:12
%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 F. T. Adams-Watters and F. 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 K. Hessami Pilehrood and T. 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_
|
