|
| |
|
|
A059015
|
|
Total number of 0's in binary expansions of 0, ..., n.
|
|
48
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
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
|
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.
|
|
|
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
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)*(2n + 2 - (1 + floor(n/2^j))*2^j) - floor(n/2^j + 1/2)*(2n + 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)
|
|
|
MATHEMATICA
|
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..]
(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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
