cp's OEIS Frontend

A000788 Total number of 1's in binary expansions of 0, ..., n.

%I A000788 M0964 N0360 #290 Jun 23 2025 15:11:37
%S A000788 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,
%T A000788 57,60,64,67,71,75,80,81,83,85,88,90,93,96,100,102,105,108,112,115,
%U A000788 119,123,128,130,133,136,140,143,147,151,156,159,163,167,172,176,181,186
%N A000788 Total number of 1's in binary expansions of 0, ..., n.
%C A000788 Partial sums of A000120.
%C A000788 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
%C A000788 a(n-1) is the largest possible number of ordered pairs (a,b) such that a/b is a prime in a subset of the positive integers with n elements. - _Yifan Xie_, Feb 21 2025
%D A000788 J.-P. Allouche & J. Shallit, Automatic sequences, Cambridge University Press, 2003, p. 94
%D A000788 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]
%D A000788 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]
%D A000788 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]
%D A000788 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]
%D A000788 E. N. Gilbert, Games of identification or convergence, SIAM Review, 4 (1962), 16-24.
%D A000788 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.
%D A000788 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.
%D A000788 E. Grosswald, Properties of some arithmetic functions, J. Math. Anal. Appl., 28 (1969), pp.405-430.
%D A000788 Donald E. Knuth, The Art of Computer Programming, volume 3 Sorting and Searching, section 5.3.4, subsection Bitonic sorting, with C'(p) = a(p-1).
%D A000788 Hiu-Fai Law, Spanning tree congestion of the hypercube, Discrete Math., 309 (2009), 6644-6648 (see p(m) on page 6647).
%D A000788 Z. Li and E. M. Reingold, Solution of a divide-and-conquer maximin recurrence, SIAM J. Comput., 18 (1989), 1188-1200.
%D A000788 B. Lindström, On a combinatorial problem in number theory, Canad. Math. Bull., 8 (1965), 477-490.
%D A000788 Mauclaire, J.-L.; Murata, Leo; On q-additive functions. I. Proc. Japan Acad. Ser. A Math. Sci. 59 (1983), no. 6, 274-276.
%D A000788 Mauclaire, J.-L.; Murata, Leo; On q-additive functions. II. Proc. Japan Acad. Ser. A Math. Sci. 59 (1983), no. 9, 441-444.
%D A000788 M. D. McIlroy, The number of 1's in binary integers: bounds and extremal properties, SIAM J. Comput., 3 (1974), 255-261.
%D A000788 L. Mirsky, A theorem on representations of integers in the scale of r, Scripta Math., 15 (1949), pp. 11-12.
%D A000788 I. Shiokawa, On a problem in additive number theory, Math. J. Okayama Univ., 16 (1974), pp.167-176. [From the bibliography of Stolarsky, 1977]
%D A000788 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000788 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A000788 K. B. Stolarsky, Power and exponential sums of digital sums related to binomial coefficient parity, SIAM J. Appl. Math., 32 (1977), 717-730.
%D A000788 Trollope, J. R. An explicit expression for binary digital sums. Math. Mag. 41 1968 21-25.
%H A000788 T. D. Noe and Hieronymus Fischer, <a href="/A000788/b000788.txt">Table of n, a(n) for n = 0..10000</a> (terms up to n=1000 by T. D. Noe).
%H A000788 G. Agnarsson, <a href="https://arxiv.org/abs/1106.4997">On the number of hypercubic bipartitions of an integer</a>, arXiv preprint arXiv:1106.4997 [math.CO], 2011.
%H A000788 G. Agnarsson, <a href="https://arxiv.org/abs/1112.3015">Induced subgraphs of hypercubes</a>, arXiv preprint arXiv:1112.3015 [math.CO], 2011.
%H A000788 G. Agnarsson and K. Lauria, <a href="https://arxiv.org/abs/1302.6517">Extremal subgraphs of the d-dimensional grid graph</a>, arXiv preprint arXiv:1302.6517 [math.CO], 2013.
%H A000788 J.-P. Allouche, <a href="http://math.colgate.edu/~integers/graham2/graham2.Abstract.html">On an Inequality in a 1970 Paper of R. L. Graham</a>, INTEGERS 21A (2021), #A2.
%H A000788 Mathias Hauan Arbo, Esten Ingar Grøtli, and Jan Tommy Gravdahl, <a href="https://arxiv.org/abs/1901.06713">CASCLIK: CasADi-Based Closed-Loop Inverse Kinematics</a>, arXiv:1901.06713 [cs.RO], 2019.
%H A000788 Venkata Sai Narayana Bavisetty, Matthew Wheeler, Reinhard Laubenbacher, and Claus Kadelka, <a href="https://arxiv.org/abs/2506.12310">Upper bound for the stability of Boolean networks</a>, arXiv:2506.12310 [q-bio.MN], 2025. See p. 8.
%H A000788 Johann Cigler, <a href="https://arxiv.org/abs/1803.05164">A curious class of Hankel determinants</a>, arXiv:1803.05164 [math.CO], 2018.
%H A000788 G. F. Clements and B. Lindström, <a href="https://doi.org/10.1090/S0002-9939-1965-0178001-X">A sequence of (+-1) determinants with large values</a>, Proc. Amer. Math. Soc., 16 (1965), pp. 548-550.  [From the bibliography of Stolarsky, 1977]
%H A000788 Jean Coquet, <a href="http://dx.doi.org/10.1016/0022-314X(86)90067-3">Power sums of digital sums</a>, J. Number Theory 22 (1986), no. 2, 161-176.
%H A000788 H. Delange, <a href="http://dx.doi.org/10.5169/seals-47328">Sur la fonction sommatoire de la fonction "somme des chiffres"</a>, Enseignement Math., (2), 21 (1975), pp. 31-47.  [From the bibliography of Stolarsky, 1977]
%H A000788 Laurent Feuilloley, <a href="https://arxiv.org/abs/1505.05072">Brief Announcement: Average Complexity for the LOCAL Model</a>, arXiv preprint arXiv:1505.05072 [cs.DC], 2015.
%H A000788 S. R. Finch, P. Sebah and Z.-Q. Bai, <a href="https://arxiv.org/abs/0802.2654">Odd Entries in Pascal's Trinomial Triangle</a>, arXiv:0802.2654 [math.NT], 2008.
%H A000788 Oscar E. González, <a href="https://faculty.math.illinois.edu/~oscareg2/resources/publications/rankinDeterminantsV11.pdf">An observation of Rankin on Hankel determinants</a>, Department of Mathematics, University of Illinois at Urbana-Champaign, 2018.
%H A000788 P. J. Grabner and H.-K. Hwang, <a href="http://algo.stat.sinica.edu.tw/">Digital sums and divide-and-conquer recurrences: Fourier expansions and absolute convergence</a>
%H A000788 Milton W. Green, <a href="/A003075/a003075.pdf">Letter to N. J. A. Sloane, 1973</a> (note "A360" refers to N0360 which is the present sequence).
%H A000788 Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, <a href="http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf">Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications</a>, Preprint 2016.
%H A000788 Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, <a href="https://doi.org/10.1145/3127585">Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications</a>, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
%H A000788 Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, <a href="https://arxiv.org/abs/2210.10968">Identities and periodic oscillations of divide-and-conquer recurrences splitting at half</a>, arXiv:2210.10968 [cs.DS], 2022, p. 36 and 44.
%H A000788 Jeffrey C. Lagarias, <a href="https://arxiv.org/abs/1112.4205">The Takagi function and its properties</a>, arXiv:1112.4205 [math.CA], 2011-2012.
%H A000788 Jeffrey C. Lagarias, <a href="http://hdl.handle.net/2433/198081">The Takagi function and its properties</a>, 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.
%H A000788 Julien Leroy, Michel Rigo, and Manon Stipulanti, <a href="https://doi.org/10.37236/6581">Behavior of Digital Sequences Through Exotic Numeration Systems</a>, Electronic Journal of Combinatorics 24(1) (2017), #P1.44.
%H A000788 Raoul Nakhmanson-Kulish, <a href="/A000788/a000788.jpg">Graphic representation of K(n)=a(n)/(n log2(n)/2) from n=63 to 131071</a>
%H A000788 D. J. Newman, <a href="https://doi.org/10.1090/S0002-9939-1969-0244149-8">On the number of binary digits in a multiple of three</a>, Proc. Amer. Math. Soc., 21 (1969), pp. 719-721.  [From the bibliography of Stolarsky, 1977]
%H A000788 Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>
%H A000788 Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>
%H A000788 S. C. Tang, <a href="https://doi.org/10.1090/S0002-9939-1963-0150082-7">An improvement and generalization of Bellman-Shapiro's theorem on a problem in additive number theory</a>, Proc. Amer. Math. Soc., 14 (1963), pp. 199-204.  [From the bibliography of Stolarsky, 1977]
%H A000788 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Binary.html">Binary</a>
%H A000788 David W. Wilson, <a href="/A000788/a000788.txt">Fast C++ function for computing a(n)</a>
%H A000788 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%F A000788 McIlroy (1974) gives bounds and recurrences. - _N. J. A. Sloane_, Mar 24 2014
%F A000788 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
%F A000788 a(n) = Sum_{k=1..n} A000120(k). - _Benoit Cloitre_, Dec 19 2002
%F A000788 a(0) = 0, a(2n) = a(n)+a(n-1)+n, a(2n+1) = 2a(n)+n+1. - _Ralf Stephan_, Sep 13 2003
%F A000788 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)
%F A000788 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
%F A000788 G.f.: (1/(1-x)^2) * Sum_{k>=0} x^2^k/(1+x^2^k). - _Ralf Stephan_, Apr 19 2003
%F A000788 a(2^n-1) = A001787(n) = n*2^(n-1). - _M. F. Hasler_, Nov 22 2009
%F A000788 a(4^n-2) = n(4^n-2).
%F A000788 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).
%F A000788 a(A000225(n)) = A173921(A000225(n)) = A001787(n); a(A000079(n)) = A005183(n). - _Reinhard Zumkeller_, Mar 04 2010
%F A000788 From _Hieronymus Fischer_, Jun 10 2012: (Start)
%F A000788 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)).
%F A000788 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)).
%F A000788 a(2^m-1) = m*2^(m-1).
%F A000788 (This is the total number of '1' digits occurring in all the numbers with <= m bits.)
%F A000788 Generic formulas for the number of digits >= d in the base p representations of all integers from 0 to n, where 1<= d < p.
%F A000788 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)).
%F A000788 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.
%F A000788 a(p^m-1) = (p-d)*m*p^(m-1).
%F A000788 (This is the total number of digits >= d occurring in all the numbers  with <= m digits in base p representation.)
%F A000788 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)
%F A000788 a(n) = Sum_{k=1..n} A000120(A240857(n,k)). - _Reinhard Zumkeller_, Apr 14 2014
%F A000788 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
%F A000788 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
%F A000788 From _Jeffrey Shallit_, Aug 07 2021: (Start)
%F A000788 A 2-regular sequence, satisfying the identities
%F A000788 a(4n+1) = -a(2n) + a(2n+1) + a(4n)
%F A000788 a(4n+2) = -2a(2n) + 2a(2n+1) + a(4n)
%F A000788 a(4n+3) = -4a(n) + 4a(2n+1)
%F A000788 a(8n) = 4a(n) - 8a(2n) + 5a(4n)
%F A000788 a(8n+4) = -9a(2n) + 5a(2n+1) + 4a(4n)
%F A000788 for n>=0. (End)
%F A000788 a(n) = Sum_{k=0..floor(log_2(n+1))} k * A360189(n,k). - _Alois P. Heinz_, Mar 06 2023
%p A000788 a:= proc(n) option remember; `if`(n=0, 0, a(n-1)+add(i, i=Bits[Split](n))) end:
%p A000788 seq(a(n), n=0..62);  # _Alois P. Heinz_, Nov 11 2024
%t A000788 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 *)
%t A000788 Table[Plus@@Flatten[IntegerDigits[Range[n], 2]], {n, 0, 62}] (* _Alonso del Arte_, Dec 16 2011 *)
%t A000788 Accumulate[DigitCount[Range[0,70],2,1]] (* _Harvey P. Dale_, Jun 08 2013 *)
%o A000788 (PARI) A000788(n)={ n<3 && return(n); if( bittest(n,0) \\
%o A000788 , n+1 == 1<<valuation(n+1,2) && return(valuation(n+1,2)*(n+1)/2) \\
%o A000788 ; A000788(n>>1)*2+n>>1+1 \\
%o A000788 , n == 1<<valuation(n,2) && return(valuation(n,2)*n/2+1) \\
%o A000788 ; A000788(n>>=1)+A000788(n-1)+n )} \\ _M. F. Hasler_, Nov 22 2009
%o A000788 (PARI) a(n)=sum(k=1,n,hammingweight(k)) \\ _Charles R Greathouse IV_, Oct 04 2013
%o A000788 (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
%o A000788 (PARI) a(n)={n++; my(t, i, s); c=n; while(c!=0, i++; c\=2); for(j=1, i, d=(n\2^(i-j))%2; t+=(2^(i-j)*(s*d+d*(i-j)/2)); s+=d); t} \\ _David A. Corneth_, Nov 26 2024
%o A000788 (C++) /* See _David W. Wilson_ link. */
%o A000788 (Haskell) a000788_list = scanl1 (+) A000120_list
%o A000788 -- _Walt Rorie-Baety_, Jun 30 2012
%o A000788 (Haskell) {a000788 0 = 0; a00788 n = a000788 n2 + a000788 (n-n2-1) + (n-n2) where n2 = n `div` 2}
%o A000788 -- _Walt Rorie-Baety_, Jul 15 2012
%o A000788 (Python)
%o A000788 def A000788(n): return sum(i.bit_count() for i in range(1,n+1)) # _Chai Wah Wu_, Mar 01 2023
%o A000788 (Python)
%o A000788 def A000788(n): return (n+1)*n.bit_count()+(sum((m:=1<<j)*((k:=n>>j)-(r if n<<1>=m*(r:=k<<1|1) else 0)) for j in range(1,n.bit_length()+1))>>1) # _Chai Wah Wu_, Nov 11 2024
%Y A000788 For number of 0's in binary expansion of 0, ..., n see A059015.
%Y A000788 The basic sequences concerning the binary expansion of n are A000120, A000788, A000069, A001969, A023416, A059015, A070939, A083652.
%Y A000788 Cf. A005183, A360189.
%Y A000788 Cf. A027868, A037123, A054899, A055640, A055641, A102669-A102685, A117804, A122840, A122841, A160093, A160094, A196563, A196564 (for base 10).
%K A000788 nonn,nice,base,easy
%O A000788 0,3
%A A000788 _N. J. A. Sloane_
%E A000788 More terms from Larry Reeves (larryr(AT)acm.org), Jan 15 2001