cp's OEIS Frontend

A059015 Total number of 0's in binary expansions of 0, ..., n.

%I A059015 #75 Apr 05 2025 04:54:35
%S A059015 1,1,2,2,4,5,6,6,9,11,13,14,16,17,18,18,22,25,28,30,33,35,37,38,41,43,
%T A059015 45,46,48,49,50,50,55,59,63,66,70,73,76,78,82,85,88,90,93,95,97,98,
%U A059015 102,105,108,110,113,115,117,118,121,123,125,126,128,129,130,130,136,141
%N A059015 Total number of 0's in binary expansions of 0, ..., n.
%C A059015 Partial sums of A023416. - _Reinhard Zumkeller_, Jul 15 2011
%C A059015 The graph of this sequence is a version of the Takagi curve: see Lagarias (2012), Section 9, especially Theorem 9.1. - _N. J. A. Sloane_, Mar 12 2016
%H A059015 T. D. Noe and Hieronymus Fischer, <a href="/A059015/b059015.txt">Table of n, a(n) for n = 0..10000</a> (terms up to n=1023 by T. D. Noe)
%H A059015 Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, <a href="http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf">Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications</a>, Preprint 2016.
%H A059015 Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, <a href="https://doi.org/10.1145/3127585">Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications</a>, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
%H A059015 Jeffrey C. Lagarias, <a href="https://arxiv.org/abs/1112.4205">The Takagi function and its properties</a>, arXiv:1112.4205 [math.CA], 2011-2012.
%H A059015 Jeffrey C. Lagarias, <a href="http://hdl.handle.net/2433/198081">The Takagi function and its properties</a>, In Functions in number theory and their probabilistic aspects, 153--189, RIMS Kôkyûroku Bessatsu, B34, Res. Inst. Math. Sci. (RIMS), Kyoto, 2012. MR3014845.
%H A059015 Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>
%H A059015 Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>
%H A059015 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%F A059015 a(n) = b(n)+1, with b(2n) = b(n)+b(n-1)+n, b(2n+1) = 2b(n)+n. - _Ralf Stephan_, Sep 13 2003
%F A059015 From _Hieronymus Fischer_, Jun 10 2012: (Start)
%F A059015 With m = floor(log_2(n)):
%F A059015 a(n) = 2 + (m+1)*(n+1) - 2^(m+1) + (1/2)*Sum_{j=1..m+1} (floor(n/2^j)*(2*n + 2 - (1 + floor(n/2^j))*2^j) - floor(n/2^j + 1/2)*(2*n + 2 - floor(n/2^j + 1/2)*2^j)).
%F A059015 a(n) = A083652(n) - (n+1)*A000120(n) + 2^(m-1) - (1/4) + (1/2)*sum_{j=1..m+1} (floor(n/2^j + 1/2)^2 - (floor(n/2^j) + 1/2)^2)*2^j.
%F A059015 a(2^m-1) = 2 + (m-2)*2^(m-1)
%F A059015 (this is the total number of zero digits occurring in all the numbers with <= m places).
%F A059015 G.f.: 1/(1 - x) + (1/(1 - x)^2)*Sum_{j>=0} x^(2*2^j)/(1 + x^(2^j)); corrected by _Ilya Gutkovskiy_, Mar 28 2018
%F A059015 General formulas for the number of digits <= d in the base p representations of all integers from 0 to n, where 0 <= d < p.
%F A059015 With m = floor(log_p(n)):
%F A059015 a(n) = 1 + (m+1)*(n+1) - (p^(m+1)-1)/(p-1) + (1/2)*sum_{j=1..m+1} (floor(n/p^j)*(2n + 2 - (1 + floor(n/p^j))*p^j) - floor(n/p^j + (p-d-1)/p)*(2n + 2 + ((p-2*d-2)/p - floor(n/p^j + (p-d-1)/p))*p^j)).
%F A059015 a(n) = H(n,p) - (n+1)*F(n,p,d+1) + (1/2)*sum_{j=1..m+1} ((floor(n/p^j + (p-d-1)/p)^2 - floor(n/p^j)^2)*p^j - (((p - 2*d-2)/p)*floor(n/p^j + (p-d-1)/p) + floor(n/p^j))*p^j), where H(n,p) = sum of number of digits in the base p representations of 0 to n and F(n,p,d) = number of digits >=d in the base p representation of n.
%F A059015 a(p^m-1) = 1 + (d+1)*m*p^(m-1) - (p^m-1)/(p-1).
%F A059015 (this is the total number of digits <= d occurring in all the numbers with <= m places in base p representation).
%F A059015 G.f.: 1/(1-x) + (1/(1-x)^2)*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)
%p A059015 a:= proc(n) option remember; `if`(n=0, 1, a(n-1)+add(1-i, i=Bits[Split](n))) end:
%p A059015 seq(a(n), n=0..65);  # _Alois P. Heinz_, Nov 11 2024
%t A059015 Accumulate[ Table[ Count[ IntegerDigits[n, 2], 0], {n, 0, 65}]] (* _Jean-François Alcover_, Oct 03 2012 *)
%t A059015 Accumulate[DigitCount[Range[0,70],2,0]] (* _Harvey P. Dale_, Jun 24 2017 *)
%o A059015 (Haskell)
%o A059015 a059015 n = a059015_list !! n
%o A059015 a059015_list = scanl1 (+) $ map a023416 [0..]
%o A059015 -- _Reinhard Zumkeller_, Jul 15 2011
%o A059015 (PARI) v=vector(100,i,1);for(i=1,#v-1,v[i+1] = v[i] + #binary(i) - hammingweight(i)); v \\ _Charles R Greathouse IV_, Nov 20 2012
%o A059015 (PARI) a(n)=if(n, my(m=logint(n,2)); 2 + (m+1)*(n+1) - 2^(m+1) + sum(j=1,m+1, my(t=floor(n/2^j + 1/2)); (n>>j)*(2*n + 2 - (1 + (n>>j))<<j) - (2*n + 2 - t<<j)*t)/2, 1) \\ _Charles R Greathouse IV_, Dec 14 2015
%o A059015 (Python)
%o A059015 def A059015(n): return 2+(n+1)*(m:=(n+1).bit_length())-(1<<m)-sum(i.bit_count() for i in range(1,n+1)) # _Chai Wah Wu_, Mar 01 2023
%o A059015 (Python)
%o A059015 def A059015(n): return 2+(n+1)*((t:=(n+1).bit_length())-n.bit_count())-(1<<t)-(sum((m:=1<<j)*((k:=n>>j)-(r if n<<1>=m*(r:=k<<1|1) else 0)) for j in range(1,n.bit_length()+1))>>1) # _Chai Wah Wu_, Nov 11 2024
%Y A059015 The basic sequences concerning the binary expansion of n are A000120, A000788, A000069, A001969, A023416, A059015, A070939, A083652.
%Y A059015 Cf. A055640, A055641, A102669-A102685, A117804, A122840, A122841, A160093, A160094, A196563, A196564 (for base 10).
%K A059015 nonn,easy,nice
%O A059015 0,3
%A A059015 _Patrick De Geest_, Dec 15 2000