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

 

Logo

Annual Appeal: Please make a donation (tax deductible in USA) to keep the OEIS running. Over 5000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".

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

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_{k=1..n} A000120(A240857(n,k)). - 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.

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.

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

Laurent Feuilloley, Brief Announcement: Average Complexity for the LOCAL Model, arXiv preprint, 2015.

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

Lagarias, Jeffrey C. 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. Also arXiv:1112.4502.

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} 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 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

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

License Agreements, Terms of Use, Privacy Policy .

Last modified December 6 06:58 EST 2016. Contains 278775 sequences.