A059015 Total number of 0's in binary expansions of 0, ..., n.
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, 45, 46, 48, 49, 50, 50, 55, 59, 63, 66, 70, 73, 76, 78, 82, 85, 88, 90, 93, 95, 97, 98, 102, 105, 108, 110, 113, 115, 117, 118, 121, 123, 125, 126, 128, 129, 130, 130, 136, 141
Offset: 0
Links
- T. D. Noe and Hieronymus Fischer, Table of n, a(n) for n = 0..10000 (terms up to n=1023 by T. D. Noe)
- Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint 2016.
- Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
- Jeffrey C. Lagarias, The Takagi function and its properties, arXiv:1112.4205 [math.CA], 2011-2012.
- Jeffrey C. Lagarias, The Takagi function and its properties, 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.
- Ralf Stephan, Some divide-and-conquer sequences ...
- Ralf Stephan, Table of generating functions
- Index entries for sequences related to binary expansion of n
Crossrefs
Programs
-
Haskell
a059015 n = a059015_list !! n a059015_list = scanl1 (+) $ map a023416 [0..] -- Reinhard Zumkeller, Jul 15 2011
-
Maple
a:= proc(n) option remember; `if`(n=0, 1, a(n-1)+add(1-i, i=Bits[Split](n))) end: seq(a(n), n=0..65); # Alois P. Heinz, Nov 11 2024
-
Mathematica
Accumulate[ Table[ Count[ IntegerDigits[n, 2], 0], {n, 0, 65}]] (* Jean-François Alcover, Oct 03 2012 *) Accumulate[DigitCount[Range[0,70],2,0]] (* Harvey P. Dale, Jun 24 2017 *) -
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
-
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))<
-
Python
def A059015(n): return 2+(n+1)*(m:=(n+1).bit_length())-(1<
-
Python
def A059015(n): return 2+(n+1)*((t:=(n+1).bit_length())-n.bit_count())-(1<
Formula
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
From Hieronymus Fischer, Jun 10 2012: (Start)
With m = floor(log_2(n)):
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)).
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.
a(2^m-1) = 2 + (m-2)*2^(m-1)
(this is the total number of zero digits occurring in all the numbers with <= m places).
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
General formulas for the number of digits <= d in the base p representations of all integers from 0 to n, where 0 <= d < p.
With m = floor(log_p(n)):
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)).
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.
a(p^m-1) = 1 + (d+1)*m*p^(m-1) - (p^m-1)/(p-1).
(this is the total number of digits <= d occurring in all the numbers with <= m places in base p representation).
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)
Comments