|
| |
|
|
A000788
|
|
Total number of 1's in binary expansions of 0, ..., n.
(Formerly M0964 N0360)
|
|
48
|
|
|
|
0, 1, 2, 4, 5, 7, 9, 12, 13, 15, 17, 20, 22, 25, 28, 32, 33, 35, 37, 40, 42, 45, 48, 52, 54, 57, 60, 64, 67, 71, 75, 80, 81, 83, 85, 88, 90, 93, 96, 100, 102, 105, 108, 112, 115, 119, 123, 128, 130, 133, 136, 140, 143, 147, 151, 156, 159, 163, 167, 172, 176, 181, 186
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
Partial sums of A000120.
The subsequence of primes begins: 2, 5, 7, 13, 17, 37, 67, 71, 83, 151, 163, 167, 181, 193, 197, 227, 263, 271, 293, 379, 449, 461, 487, 491, 599. [From Jonathan Vos Post, Feb 10 2010]
a(A000225(n))=A173921(A000225(n))=A001787(n); a(A000079(n))=A005183(n). [From Reinhard Zumkeller, Mar 04 2010]
|
|
|
REFERENCES
|
G. Agnarsson, On the number of hypercubic bipartitions of an integer, Arxiv preprint arXiv:1106.4997, 2011
G. Agnarsson, Induced subgraphs of hypercubes, Arxiv preprint arXiv:1112.3015, 2011
G. Agnarsson and K. Lauria, Extremal subgraphs of the d-dimensional grid graph, arXiv preprint arXiv:1302.6517, 2013
J.-P. Allouche & J. Shallit, Automatic sequences, Cambridge University Press, 2003, p. 94
R. Bellman and H. N. Shapiro, On a problem in additive number theory, Annals Math., 49 (1948), 333-340. See Eq. 1.9. [From N. J. A. Sloane, Mar 12 2009]
E. N. Gilbert, Games of identification or convergence, SIAM Review, 4 (1962), 16-24.
R. L. Graham, On primitive graphs and optimal vertex assignments, pp. 170-186 of Internat. Conf. Combin. Math. (New York, 1970), Annals of the NY Academy of Sciences, Vol. 175, 1970.
Hiu-Fai Law, Spanning tree congestion of the hypercube, Discrete Math., 309 (2009), 6644-6648 (see p(m) on page 6647).
Z. Li and E. M. Reingold, Solution of a divide-and-conquer maximin recurrence, SIAM J. Comput., 18 (1989), 1188-1200.
B. Lindstrom, On a combinatorial problem in number theory, Canad. Math. Bull., 8 (1965), 477-490.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
T. D. Noe and Hieronymus Fischer, Table of n, a(n) for n = 0..10000 (terms up to n=1000 by T. D. Noe).
S. R. Finch, P. Sebah and Z.-Q. Bai, Odd Entries in Pascal's Trinomial Triangle (arXiv:0802.2654)
P. J. Grabner, H.-K. Hwang, Digital sums and divide-and-conquer recurrences: Fourier expansions and absolute convergence
R. Stephan, Some divide-and-conquer sequences ...
R. Stephan, Table of generating functions
Eric Weisstein's World of Mathematics, Binary
David W. Wilson, Fast C++ function for computing a(n)
Index entries for sequences related to binary expansion of n
|
|
|
FORMULA
|
a(n)=sum(k=1, n, A000120(k)). - Benoit Cloitre, Dec 19, 2002
a(0) = 0, a(2n) = a(n)+a(n-1)+n, a(2n+1) = 2a(n)+n+1. - Ralf Stephan, Sep 13 2003
a(n)=(1/2)*log2(n)*n + O(n); a(2^n)=n*2^(n-1)+1 - Benoit Cloitre, Sep 25 2003
a(n)=(1/2)*n*log(n)/log(2)+n*F(log(n)/log(2)) where F is a nowhere differentiable continuous function of period 1 (see Allouche & Shallit) - Benoit Cloitre, Jun 08 2004
G.f.: 1/(1-x)^2 * Sum(k>=0, x^2^k/(1+x^2^k)). - Ralf Stephan, Apr 19 2003
a(2^n-1) = A001787(n) = n*2^(n-1). [From M. F. Hasler, Nov 22 2009]
a(4^n-2) = n(4^n-2)
For real n, let f(n) = [n]/2 if [n] even, n-[n+1]/2 otherwise. Then a(n) = SUM(k = 0..inf; 2^k*f((n+1)/2^k)).
Contribution from Hieronymus Fischer, Jun 10 2012: (Start)
a(n) = (1/2)*sum_{j=1..m+1} (floor(n/2^j + 1/2)*(2n + 2 - floor(n/2^j + 1/2))*2^j - floor(n/2^j)*(2n + 2 - (1 + floor(n/2^j)) * 2^j)), where m=floor(log_2(n)).
a(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, where m=floor(log_2(n)).
a(2^m-1) = m*2^(m-1).
(this is the total number of 1' digits occurring in all the numbers with <= m places).
Generic formulas for the number of digits >= d in the base p representations of all integers from 0 to n, where 1<= d < p.
a(n) = (1/2)*sum_{j=1..m+1} (floor(n/p^j + (p-d)/p)*(2n + 2 + ((p-2*d)/p - floor(n/p^j + (p-d)/p))*p^j) - floor(n/p^j)*(2n + 2 - (1+floor(n/p^j)) * p^j)), where m=floor(log_p(n)).
a(n) = (n+1)*F(n,p,d) + (1/2)*sum_{j=1..m+1} ((((p-2*d)/p)*floor(n/p^j+(p-d)/p) + floor(n/p^j))*p^j - (floor(n/p^j+(p-d)/p)^2 - floor(n/p^j)^2)*p^j), where m=floor(log_p(n)) and F(n,p,d) = number of digits >= d in the base p representation of n.
a(p^m-1) = (p-d)*m*p^(m-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-x)^2)*sum_{j>=0} (x^(d*p^j) - x^(p*p^j))/(1-x^(p*p^j)). (End)
|
|
|
MATHEMATICA
|
a[n_] := Count[ Table[ IntegerDigits[k, 2], {k, 0, n}], 1, 2]; Table[a[n], {n, 0, 62}] (* From Jean-François Alcover, Dec 16 2011 *)
Table[Plus@@Flatten[IntegerDigits[Range[n], 2]], {n, 0, 62}] (* Alonso del Arte, Dec 16 2011 *)
|
|
|
PROG
|
(PARI) A000788(n)={ n<3 & return(n); if( bittest(n, 0) \\
, n+1 == 1<<valuation(n+1, 2) && return(valuation(n+1, 2)*(n+1)/2) \\
; A000788(n>>1)*2+n>>1+1 \\
, n == 1<<valuation(n, 2) && return(valuation(n, 2)*n/2+1) \\
; A000788(n>>=1)+A000788(n-1)+n )} \\
/* M. F. Hasler, Nov 22 2009 */
(C++) /* See David W. Wilson link. */
(Haskell) a000788_list = scanl1 (+) A000120_list
-- Walt Rorie-Baety, 30 June 2012
(Haskell) {a000788 0 = 0; a00788 n = a000788 n2 + a000788 (n-n2-1) + (n-n2) where n2 = n `div` 2}
-- Walt Rorie-Baety, 15 July 2012
|
|
|
CROSSREFS
|
For number of 0's in binary expansion of 0, ..., n see A059015.
The basic sequences concerning the binary expansion of n are A000120, A000788, A000069, A001969, A023416, A059015, A070939, A083652.
Cf. A005183.
Cf. A027868, A054899, A055640, A055641, A102669-A102685, A117804, A122840, A122841, A160093, A160094, A196563, A196564 (for base 10).
Sequence in context: A140206 A007818 A158618 * A053039 A214051 A027861
Adjacent sequences: A000785 A000786 A000787 * A000789 A000790 A000791
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
EXTENSIONS
|
More terms from Larry Reeves (larryr(AT)acm.org), Jan 15 2001
|
|
|
STATUS
|
approved
|
| |
|
|
