OFFSET
0,3
COMMENTS
Partial sums of A023416. - Reinhard Zumkeller, Jul 15 2011
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
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, 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, 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.
R. Stephan, Some divide-and-conquer sequences ...
R. Stephan, Table of generating functions
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.: g(x) = 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.: g(x) = 1 + (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)
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 *)
PROG
(Haskell)
a059015 n = a059015_list !! n
a059015_list = scanl1 (+) $ map a023416 [0..]
-- Reinhard Zumkeller, Jul 15 2011
(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))<<j) - (2*n + 2 - t<<j)*t)/2, 1) \\ Charles R Greathouse IV, Dec 14 2015
(Python)
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
(Python)
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
CROSSREFS
KEYWORD
nonn,easy,nice,changed
AUTHOR
Patrick De Geest, Dec 15 2000
STATUS
approved