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

%I M0964 N0360

%S 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 57,60,64,67,71,75,80,81,83,85,88,90,93,96,100,102,105,108,112,115,

%U 119,123,128,130,133,136,140,143,147,151,156,159,163,167,172,176,181,186

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

%C Partial sums of A000120.

%C 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 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

%C a(A000225(n)) = A173921(A000225(n)) = A001787(n); a(A000079(n)) = A005183(n). - _Reinhard Zumkeller_, Mar 04 2010

%C a(n) = Sum_{k=1..n} A000120(A240857(n,k)). - _Reinhard Zumkeller_, Apr 14 2014

%D J.-P. Allouche & J. Shallit, Automatic sequences, Cambridge University Press, 2003, p. 94

%D 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 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 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 Coquet, Jean; Power sums of digital sums. J. Number Theory 22 (1986), no. 2, 161-176.

%D 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 E. N. Gilbert, Games of identification or convergence, SIAM Review, 4 (1962), 16-24.

%D 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 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 E. Grosswald, Properties of some arithmetic functions, J. Math. Anal. Appl., 28 (1969), pp.405-430.

%D Hiu-Fai Law, Spanning tree congestion of the hypercube, Discrete Math., 309 (2009), 6644-6648 (see p(m) on page 6647).

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

%D Z. Li and E. M. Reingold, Solution of a divide-and-conquer maximin recurrence, SIAM J. Comput., 18 (1989), 1188-1200.

%D B. Lindstrom, On a combinatorial problem in number theory, Canad. Math. Bull., 8 (1965), 477-490.

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

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

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

%D L. Mirsky, A theorem on representations of integers in the scale of r, Scripta Math., 15 (1949), pp. 11-12.

%D 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 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

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

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

%H 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 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 G. Agnarsson, <a href="https://arxiv.org/abs/1112.3015">Induced subgraphs of hypercubes</a>, arXiv preprint arXiv:1112.3015 [math.CO], 2011.

%H 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 Mathias Hauan Arbo, Esten Ingar Grøtli, 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 Johann Cigler, <a href="https://arxiv.org/abs/1803.05164">A curious class of Hankel determinants</a>, arXiv:1803.05164 [math.CO], 2018.

%H G. F. Clements and B. Lindstrom, <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 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 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 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 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 P. J. Grabner, 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 Milton W. Green, <a href="/A003075/a003075.pdf">Letter to N. J. A. Sloane, 1973</a>.

%H Hsien-Kuei Hwang, S. Janson, 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 Hsien-Kuei Hwang, S. Janson, 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 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 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 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 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 R. Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>

%H R. Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>

%H 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Binary.html">Binary</a>

%H David W. Wilson, <a href="/A000788/a000788.txt">Fast C++ function for computing a(n)</a>

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%F McIlroy (1974) gives bounds and recurrences. - _N. J. A. Sloane_, Mar 24 2014

%F 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 a(n) = Sum_{k=1..n} A000120(k). - _Benoit Cloitre_, Dec 19 2002

%F a(0) = 0, a(2n) = a(n)+a(n-1)+n, a(2n+1) = 2a(n)+n+1. - _Ralf Stephan_, Sep 13 2003

%F 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 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 G.f.: (1/(1-x)^2) * Sum_{k>=0} x^2^k/(1+x^2^k). - _Ralf Stephan_, Apr 19 2003

%F a(2^n-1) = A001787(n) = n*2^(n-1). - _M. F. Hasler_, Nov 22 2009

%F a(4^n-2) = n(4^n-2).

%F 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 From _Hieronymus Fischer_, Jun 10 2012: (Start)

%F 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 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 a(2^m-1) = m*2^(m-1).

%F (This is the total number of '1' digits occurring in all the numbers with <= m bits.)

%F 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 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 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 a(p^m-1) = (p-d)*m*p^(m-1).

%F (This is the total number of digits >= d occurring in all the numbers with <= m digits in base p representation.)

%F G.f.: g(x) = (1/(1-x)^2)*Sum_{j>=0} (x^(d*p^j) - x^(p*p^j))/(1-x^(p*p^j)).

%F (End)

%F 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

%t 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 Table[Plus@@Flatten[IntegerDigits[Range[n], 2]], {n, 0, 62}] (* _Alonso del Arte_, Dec 16 2011 *)

%t Accumulate[DigitCount[Range[0,70],2,1]] (* _Harvey P. Dale_, Jun 08 2013 *)

%o (PARI) A000788(n)={ n<3 && return(n); if( bittest(n,0) \\

%o , n+1 == 1<<valuation(n+1,2) && return(valuation(n+1,2)*(n+1)/2) \\

%o ; A000788(n>>1)*2+n>>1+1 \\

%o , n == 1<<valuation(n,2) && return(valuation(n,2)*n/2+1) \\

%o ; A000788(n>>=1)+A000788(n-1)+n )} \\ _M. F. Hasler_, Nov 22 2009

%o (PARI) a(n)=sum(k=1,n,hammingweight(k)) \\ _Charles R Greathouse IV_, Oct 04 2013

%o (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 (C++) /* See _David W. Wilson_ link. */

%o (Haskell) a000788_list = scanl1 (+) A000120_list

%o -- _Walt Rorie-Baety_, Jun 30 2012

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

%o -- _Walt Rorie-Baety_, Jul 15 2012

%Y For number of 0's in binary expansion of 0, ..., n see A059015.

%Y The basic sequences concerning the binary expansion of n are A000120, A000788, A000069, A001969, A023416, A059015, A070939, A083652.

%Y Cf. A005183.

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

%K nonn,nice,base,easy

%O 0,3

%A _N. J. A. Sloane_

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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 18 19:48 EST 2019. Contains 329288 sequences. (Running on oeis4.)