A000788 Total number of 1's in binary expansions of 0, ..., n. (Formerly M0964 N0360)

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

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

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]

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

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. Lindström, 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.

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.

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 [math.CO], 2011.

G. Agnarsson, Induced subgraphs of hypercubes, arXiv preprint arXiv:1112.3015 [math.CO], 2011.

G. Agnarsson and K. Lauria, Extremal subgraphs of the d-dimensional grid graph, arXiv preprint arXiv:1302.6517 [math.CO], 2013.

J.-P. Allouche, On an Inequality in a 1970 Paper of R. L. Graham, INTEGERS 21A (2021), #A2.

Mathias Hauan Arbo, Esten Ingar Grøtli, and Jan Tommy Gravdahl, CASCLIK: CasADi-Based Closed-Loop Inverse Kinematics, arXiv:1901.06713 [cs.RO], 2019.

Johann Cigler, A curious class of Hankel determinants, arXiv:1803.05164 [math.CO], 2018.

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

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]

Laurent Feuilloley, Brief Announcement: Average Complexity for the LOCAL Model, arXiv preprint arXiv:1505.05072 [cs.DC], 2015.

S. R. Finch, P. Sebah and Z.-Q. Bai, Odd Entries in Pascal's Trinomial Triangle, arXiv:0802.2654 [math.NT], 2008.

Oscar E. González, An observation of Rankin on Hankel determinants, Department of Mathematics, University of Illinois at Urbana-Champaign, 2018.

P. J. Grabner and H.-K. Hwang, Digital sums and divide-and-conquer recurrences: Fourier expansions and absolute convergence

Milton W. Green, Letter to N. J. A. Sloane, 1973 (note "A360" refers to N0360 which is the present sequence).

Hsien-Kuei Hwang, S. Janson, and 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, and 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.

Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 36 and 44.

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.

Julien Leroy, Michel Rigo, and Manon Stipulanti, Behavior of Digital Sequences Through Exotic Numeration Systems, Electronic Journal of Combinatorics 24(1) (2017), #P1.44.

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

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]

R. Stephan, Some divide-and-conquer sequences ...

R. Stephan, Table of generating functions

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]

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

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

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)

a(n) = Sum_{k=1..n} A000120(A240857(n,k)). - Reinhard Zumkeller, Apr 14 2014

For n > 0, if n is written as 2^m + r with 0 <= r < 2^m, then a(n) = m*2^(m-1) + r + 1 + a(r). - Shreevatsa R, Mar 20 2018

a(n) = n*(n+1)/2 + Sum_{k=1..floor(n/2)} ((2k-1)((g(n,k)-1)*2^(g(n,k) + 1) + 2) - (n+1)*(g(n,k)+1)*g(n,k)/2), where g(n,k) = floor(log_2(n/(2k-1))). - Fabio Visonà, Mar 17 2020

From Jeffrey Shallit, Aug 07 2021: (Start)

A 2-regular sequence, satisfying the identities

a(4n+1) = -a(2n) + a(2n+1) + a(4n)

a(4n+2) = -2a(2n) + 2a(2n+1) + a(4n)

a(4n+3) = -4a(n) + 4a(2n+1)

a(8n) = 4a(n) - 8a(2n) + 5a(4n)

a(8n+4) = -9a(2n) + 5a(2n+1) + 4a(4n)

for n>=0. (End)

a(n) = Sum_{k=0..floor(log_2(n+1))} k * A360189(n,k). - Alois P. Heinz, Mar 06 2023

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
(PARI) a(n) = if (n==0, 0, m = logint(n, 2); r = n % 2^m; m*2^(m-1) + r + 1 + a(r)); \\ Michel Marcus, Mar 27 2018
(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
(Python)
def A000788(n): return sum(i.bit_count() for i in range(1, n+1)) # Chai Wah Wu, Mar 01 2023

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, A360189.

Cf. A027868, A054899, A055640, A055641, A102669-A102685, A117804, A122840, A122841, A160093, A160094, A196563, A196564 (for base 10).

Sequence in context: A140206 A007818 A158618 * A053039 A286753 A325543

Adjacent sequences: A000785 A000786 A000787 * A000789 A000790 A000791

Keyword

nonn,nice,base,easy,changed

Author

N. J. A. Sloane

Extensions

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

Status

approved