login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A023416 Number of 0's in binary expansion of n. 188

%I

%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-Waters, 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 J.-P. Allouche, J. 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 K. Hessami Pilehrood, 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), #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, 12 (2012), #A1. - From _N. J. A. Sloane_, Feb 07 2013

%H Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>

%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

%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)=n=binary(n); sum(i=1, #n, !n[i]) \\ _Charles R Greathouse IV_, Jun 10 2011

%o (PARI) a(n)=#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

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

%K nonn,nice,easy,base

%O 0,5

%A _David W. Wilson_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 19:58 EDT 2019. Contains 321293 sequences. (Running on oeis4.)