login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000788 Total number of 1's in binary expansions of 0, ..., n.
(Formerly M0964 N0360)
56
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. - Jonathan Vos Post, Feb 10 2010

a(A000225(n))=A173921(A000225(n))=A001787(n); a(A000079(n))=A005183(n). - Reinhard Zumkeller, Mar 04 2010

a(n) = Sum(A000120(A240857(n,k)): k = 1..n). - Reinhard Zumkeller, Apr 14 2014

REFERENCES

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]

L. E. BUSH, An asymptotic formula for the average sums of the digits of integers, Amer. Math. Monthly, 47 (1940), pp. 154-156.  [From the bibliography of Stolarsky, 1977]

P. CHEO AND S. YIEN, A problem on the k-adic representation of positive integers (Chinese; English summary), Acta Math. Sinica, 5 (1955), pp. 433-438.  [From the bibliography of Stolarsky, 1977]

G. F. CLEMENTS AND B. LINDSTROM, A sequence of (+-1) determinants with large values, Proc. Amer. Math. Soc., 16 (1965), pp. 548-550.  [From the bibliography of Stolarsky, 1977]

Coquet, Jean; Power sums of digital sums. J. Number Theory 22 (1986), no. 2, 161-176.

H. DELANGE, Sur la fonction sommatoire de la fonction "somme des chiffres", Enseignement Math., (2), 21 (1975), pp. 31-47.  [From the bibliography of Stolarsky, 1977]

M. P. DRAZIN AND J. S. GRIFFITH, On the decimal representation of integers, Proc. Cambridge Philos. Soc., (4), 48 (1952), pp. 555-565.  [From the bibliography of Stolarsky, 1977]

E. N. Gilbert, Games of identification or convergence, SIAM Review, 4 (1962), 16-24.

Grabner, P. J.; Kirschenhofer, P.; Prodinger, H.; Tichy, R. F.; On the moments of the sum-of-digits function. Applications of Fibonacci numbers, Vol. 5 (St. Andrews, 1992), 263-271, Kluwer Acad. Publ., Dordrecht, 1993.

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.

E. GROSSWALD, Properties of some arithmetic functions, J. Math. Anal. Appl., 28 (1969), pp.405-430.  [From the bibliography of Stolarsky, 1977]

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.

Mauclaire, J.-L.; Murata, Leo; On q-additive functions. I. Proc. Japan Acad. Ser. A Math. Sci. 59 (1983), no. 6, 274-276.

Mauclaire, J.-L.; Murata, Leo; On q-additive functions. II. Proc. Japan Acad. Ser. A Math. Sci. 59 (1983), no. 9, 441-444.

M. D. McIlroy, The number of 1's in binary integers: bounds and extremal properties, SIAM J. Comput., 3 (1974), 255-261.

L. MIRSKY, A theorem on representations of integers in the scale of r, Scripta Math., 15 (1949), pp. 11-12.  [From the bibliography of Stolarsky, 1977]

D. J. NEWMAN, On the number of binary digits in a multiple of three, Proc. Amer. Math. Soc., 21 (1969), pp. 719-721.  [From the bibliography of Stolarsky, 1977]

I. SHIOKAWA, On a problem in additive number theory, Math. J. Okayama Univ., 16 (1974), pp.167-176. [From the bibliography of Stolarsky, 1977]

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).

K. B. Stolarsky, Power and exponential sums of digital sums related to binomial coefficient parity, SIAM J. Appl. Math., 32 (1977), 717-730.

S. C. TANG, An improvement and generalization of Bellman-Shapiro's theorem on a problem in additive number theory, Proc. Amer. Math. Soc., 14 (1963), pp. 199-204.  [From the bibliography of Stolarsky, 1977]

Trollope, J. R. An explicit expression for binary digital sums. Math. Mag. 41 1968 21-25.

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).

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

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

Raoul Nakhmanson-Kulish, Graphic representation of K(n)=a(n)/(n log2(n)/2) from n=63 to 131071

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

McIlroy (1974) gives bounds and recurrences. - N. J. A. Sloane, Mar 24 2014

Stolarsky (1977) studies the asymptotics, and gives at least nine references to earlier work on the problem. I have added all the references that were not here already. - N. J. A. Sloane, Apr 06 2014

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)=n*log_2(n)/2 + O(n); a(2^n)=n*2^(n-1)+1. - Benoit Cloitre, Sep 25 2003 (The first result is due to Bellman and Shapiro, - N. J. A. Sloane, Mar 24 2014)

a(n)=n*log_2(n)/2+n*F(log_2(n)) 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). - 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)).

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 bits.)

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 digits 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}] (* Jean-Fran├žois Alcover, Dec 16 2011 *)

Table[Plus@@Flatten[IntegerDigits[Range[n], 2]], {n, 0, 62}] (* Alonso del Arte, Dec 16 2011 *)

Accumulate[DigitCount[Range[0, 70], 2, 1]] (* Harvey P. Dale, Jun 08 2013 *)

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

(PARI) a(n)=sum(k=1, n, hammingweight(k)) \\ Charles R Greathouse IV, Oct 04 2013

(C++) /* See David W. Wilson link. */

(Haskell) a000788_list = scanl1 (+) A000120_list

-- Walt Rorie-Baety, Jun 30 2012

(Haskell) {a000788 0 = 0; a00788 n = a000788 n2 + a000788 (n-n2-1) + (n-n2) where n2 = n `div` 2}

-- Walt Rorie-Baety, Jul 15 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 A245783

Adjacent sequences:  A000785 A000786 A000787 * A000789 A000790 A000791

KEYWORD

nonn,nice,easy,changed

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Larry Reeves (larryr(AT)acm.org), Jan 15 2001

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified October 25 03:21 EDT 2014. Contains 248517 sequences.