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.
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.: 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
KEYWORD
nonn,nice,easy,base
AUTHOR
STATUS
approved