A360189 -id:A360189 - cp's OEIS frontend

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

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

N. J. A. Sloane

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

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

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.
Venkata Sai Narayana Bavisetty, Matthew Wheeler, Reinhard Laubenbacher, and Claus Kadelka, Upper bound for the stability of Boolean networks, arXiv:2506.12310 [q-bio.MN], 2025. See p. 8.
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]
Jean Coquet, 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]
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]
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf 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

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, A037123, A054899, A055640, A055641, A102669-A102685, A117804, A122840, A122841, A160093, A160094, A196563, A196564 (for base 10).

a000788_list = scanl1 (+) A000120_list
-- Walt Rorie-Baety, Jun 30 2012

{a000788 0 = 0; a00788 n = a000788 n2 + a000788 (n-n2-1) + (n-n2) where n2 = n `div` 2}
-- Walt Rorie-Baety, Jul 15 2012

a:= proc(n) option remember; `if`(n=0, 0, a(n-1)+add(i, i=Bits[Split](n))) end:
seq(a(n), n=0..62);  # Alois P. Heinz, Nov 11 2024

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

A000788(n)={ n<3 && return(n); if( bittest(n,0) \\
, n+1 == 1<A000788(n>>1)*2+n>>1+1 \\
, n == 1<A000788(n>>=1)+A000788(n-1)+n )} \\ M. F. Hasler, Nov 22 2009

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

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

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
(C++) /* See David W. Wilson link. */

def A000788(n): return sum(i.bit_count() for i in range(1,n+1)) # Chai Wah Wu, Mar 01 2023

def A000788(n): return (n+1)*n.bit_count()+(sum((m:=1<>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

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

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

A006046 Total number of odd entries in first n rows of Pascal's triangle: a(0) = 0, a(1) = 1, a(2k) = 3a(k), a(2k+1) = 2a(k) + a(k+1). a(n) = Sum_{i=0..n-1} 2^wt(i).

Original entry on oeis.org

0, 1, 3, 5, 9, 11, 15, 19, 27, 29, 33, 37, 45, 49, 57, 65, 81, 83, 87, 91, 99, 103, 111, 119, 135, 139, 147, 155, 171, 179, 195, 211, 243, 245, 249, 253, 261, 265, 273, 281, 297, 301, 309, 317, 333, 341, 357, 373, 405, 409, 417, 425, 441, 449, 465, 481, 513, 521

Offset: 0

Jeffrey Shallit

The graph has a blancmange or Takagi appearance. For the asymptotics, see the references by Flajolet with "Mellin" in the title. - N. J. A. Sloane, Mar 11 2021
The following alternative construction of this sequence is due to Thomas Nordhaus, Oct 31 2000: For each n >= 0 let f_n be the piecewise linear function given by the points (k /(2^n), a(k) / 3^n), k = 0, 1, ..., 2^n. f_n is a monotonic map from the interval [0,1] into itself, f_n(0) = 0, f_n(1) = 1. This sequence of functions converges uniformly. But the limiting function is not differentiable on a dense subset of this interval.
I submitted a problem to the Amer. Math. Monthly about an infinite family of non-convex sequences that solve a recurrence that involves minimization: a(1) = 1; a(n) = max { ua(k) + a(n-k) | 1 <= k <= n/2 }, for n > 1; here u is any real-valued constant >= 1. The case u=2 gives the present sequence. Cf. A130665 - A130667. - Don Knuth, Jun 18 2007
a(n) = sum of (n-1)-th row terms of triangle A166556. - Gary W. Adamson, Oct 17 2009
From Gary W. Adamson, Dec 06 2009: (Start)
Let M = an infinite lower triangular matrix with (1, 3, 2, 0, 0, 0, ...) in every column shifted down twice:
  1;
  3;
  2; 1;
  0, 3;
  0, 2, 1;
  0, 0, 3;
  0, 0, 2, 1;
  0, 0, 0, 3;
  0, 0, 0, 2, 1;
  ...
This sequence starting with "1" = lim_{n->infinity} M^n, the left-shifted vector considered as a sequence. (End)
a(n) is also the sum of all entries in rows 0 to n of Sierpiński's triangle A047999. - Reinhard Zumkeller, Apr 09 2012
The production matrix of Dec 06 2009 is equivalent to the following: Let p(x) = (1 + 3x + 2x^2). The sequence = P(x) * p(x^2) * p(x^4) * p(x^8) * .... The sequence divided by its aerated variant = (1, 3, 2, 0, 0, 0, ...). - Gary W. Adamson, Aug 26 2016
Also the total number of ON cells, rows 1 through n, for cellular automaton Rule 90 (Cf. A001316, A038183, also Mathworld Link). - Bradley Klee, Dec 22 2018

S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 2.16.
Flajolet, Philippe, and Mordecai Golin. "Mellin transforms and asymptotics." Acta Informatica 31.7 (1994): 673-696.
Flajolet, Philippe, Mireille Régnier, and Robert Sedgewick. "Some uses of the Mellin integral transform in the analysis of algorithms." in Combinatorial algorithms on words. Springer, 1985. 241-254.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n = 0..16383 (first 1000 terms from T. D. Noe)
L. Carlitz, The number of binomial coefficients divisible by a fixed power of a prime, Rend. Circ. Mat. Palermo (2) 16 (1967), pp. 299-320.
K.-N. Chang and S.-C. Tsai, Exact solution of a minimal recurrence, Inform. Process. Lett. 75 (2000), 61-64.
Prerona Chatterjee, Kshitij Gajjar, and Anamay Tengse, Transparency Beyond VNP in the Monotone Setting, arXiv:2202.13103 [cs.CC], 2022.
S. R. Finch, P. Sebah, and Z.-Q. Bai, Odd Entries in Pascal's Trinomial Triangle, arXiv:0802.2654 [math.NT], 2008.
N. J. Fine, Binomial coefficients modulo a prime, Amer. Math. Monthly 54:10 (1947), pp. 89-92.
Philippe Flajolet, Peter Grabner, Peter Kirschenhofer, Helmut Prodinger, and Robert F. Tichy, Mellin Transforms And Asymptotics: Digital Sums, Theoret. Computer Sci. 23 (1994), 291-314.
Philippe Flajolet, Xavier Gourdon, and Philippe Dumas, Mellin transforms and asymptotics: harmonic sums Special volume on mathematical analysis of algorithms. Theoret. Comput. Sci. 144 (1995), no. 1-2, 3-58.
Philippe Flajolet and Robert Sedgewick, Mellin transforms and asymptotics: Finite differences and Rice's integrals, Theoretical Computer Science 144.1-2 (1995): 101-124.
P. J. Grabner and H.-K. Hwang, Digital sums and divide-and-conquer recurrences: Fourier expansions and absolute convergence, Constructive Approximation, Jan. 2005, Volume 21, Issue 2, pp 149-179.
H. Harborth, Number of Odd Binomial Coefficients, Proc. Amer. Math. Soc. 62, 19-22, 1977.
H. Harborth, Number of Odd Binomial Coefficients, Proc. Amer. Math. Soc. 62.1 (1977), 19-22. (Annotated scanned copy)
F. T. Howard, The number of binomial coefficients divisible by a fixed power of 2, Proceedings of the American Mathematical Society, Vol. 29:2 (Jul 1971), pp. 236-242.
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, pp. 6, 27, 29-31.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Periodic minimum in the count of binomial coefficients not divisible by a prime, arXiv:2408.06817 [math.NT], 2024. See p. 1.
Akhlesh Lakhtakia and Russell Messier, Self-similar sequences and chaos from Gauss sums, Computers & graphics 13.1 (1989): 59-62.
Akhlesh Lakhtakia and Russell Messier, Self-similar sequences and chaos from Gauss sums, Computers & Graphics 13.1 (1989), 59-60. (Annotated scanned copy)
A. Lakhtakia et al., Fractal sequences derived from the self-similar extensions of the Sierpinski gasket, J. Phys. A 21 (1988), 1925-1928.
Giuseppe Lancia and Paolo Serafini, Computational Complexity and ILP Models for Pattern Problems in the Logical Analysis of Data, Algorithms (2021) Vol. 14, No. 8, 235.
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015.
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
K. B. Stolarsky, Power and exponential sums of digital sums related to binomial coefficient parity, SIAM J. Appl. Math., 32 (1977), 717-730. See B(n). - _N. J. A. Sloane_, Apr 05 2014
Eric Weisstein's World of Mathematics, Pascal's Triangle
Eric Weisstein's World of Mathematics, Rule 90
Eric Weisstein's World of Mathematics, Stolarsky-Harborth Constant
Index entries for triangles and arrays related to Pascal's triangle

Partial sums of A001316.
See A130665 for Sum 3^wt(n).
a(n) = A074330(n-1) + 1 for n >= 2. A080978(n) = 2*a(n) + 1. Cf. A080263.
Cf. also A159912, A166556, A038183, A048896, A360189.
Sequences of form a(n) = r*a(ceiling(n/2)) + s*a(floor(n/2)), a(1)=1, for (r,s) = (1,1), (1,2), (2,1), (1,3), (2,2), (3,1), (1,4), (2,3), (3,2), (4,1): A000027, A006046, A064194, A130665, A073121, A268524, A116520, A268525, A268526, A268527.

a006046 = sum . concat . (`take` a047999_tabl)
-- Reinhard Zumkeller, Apr 09 2012

[0] cat [n le 1 select 1 else 2*Self(Floor(n/2)) + Self(Floor(Ceiling(n/2))): n in [1..60]]; // Vincenzo Librandi, Aug 30 2016

f:=proc(n) option remember;
if n <= 1 then n elif n mod 2 = 0 then 3*f(n/2)
else 2*f((n-1)/2)+f((n+1)/2); fi; end;
[seq(f(n),n=0..130)]; # N. J. A. Sloane, Jul 29 2014

f[n_] := Sum[ Mod[ Binomial[n, k], 2], {k, 0, n} ]; Table[ Sum[ f[k], {k, 0, n} ], {n, 0, 100} ]
Join[{0},Accumulate[Count[#,?OddQ]&/@Table[Binomial[n,k],{n,0,60},{k,0,n}]]] (* _Harvey P. Dale, Dec 10 2014 *)
FoldList[Plus, 0, Total /@ CellularAutomaton[90, Join[Table[0, {#}], {1}, Table[0, {#}]], #]][[2 ;; -1]] &@50 (* Bradley Klee, Dec 23 2018 *)
Join[{0}, Accumulate[2^DigitCount[Range[0, 127], 2, 1]]] (* Paolo Xausa, Oct 24 2024 *)
Join[{0}, Accumulate[2^Nest[Join[#, #+1]&, {0}, 7]]] (* Paolo Xausa, Oct 24 2024, after IWABUCHI Yu(u)ki in A000120 *)

A006046(n)={ n<2 & return(n); A006046(n\2)*3+if(n%2,1<M. F. Hasler, May 03 2009

a(n) = if(!n, 0, my(r=0, t=1); forstep(i=logint(n, 2), 0, -1, r*=3; if(bittest(n, i), r+=t; t*=2)); r); \\ Ruud H.G. van Tol, Jul 06 2024

from functools import lru_cache
@lru_cache(maxsize=None)
def A006046(n):return n if n<=1 else 2*A006046((n-1)//2)+A006046((n+1)//2)if n%2 else 3*A006046(n//2) # Guillermo Hernández, Dec 31 2023

from math import prod
def A006046(n):
    d = list(map(lambda x:int(x)+1,bin(n)[:1:-1]))
    return sum((b-1)*prod(d[a:])*3**a for a, b in enumerate(d))>>1 # Chai Wah Wu, Aug 13 2025

a(n) = Sum_{k=0..n-1} 2^A000120(k). - Paul Barry, Jan 05 2005; simplified by N. J. A. Sloane, Apr 05 2014
For asymptotics see Stolarsky (1977). - N. J. A. Sloane, Apr 05 2014
a(n) = a(n-1) + A001316(n-1). a(2^n) = 3^n. - Henry Bottomley, Apr 05 2001
a(n) = n^(log_2(3))*G(log_2(n)) where G(x) is a function of period 1 defined by its Fourier series. - Benoit Cloitre, Aug 16 2002; formula modified by S. R. Finch, Dec 31 2007
G.f.: (x/(1-x))*Product_{k>=0} (1 + 2*x^2^k). - Ralf Stephan, Jun 01 2003; corrected by Herbert S. Wilf, Jun 16 2005
a(1) = 1, a(n) = 2*a(floor(n/2)) + a(ceiling(n/2)).
a(n) = 3*a(floor(n/2)) + (n mod 2)*2^A000120(n-1). - M. F. Hasler, May 03 2009
a(n) = Sum_{k=0..floor(log_2(n))} 2^k * A360189(n-1,k). - Alois P. Heinz, Mar 06 2023

More terms from James Sellers, Aug 21 2000

Definition expanded by N. J. A. Sloane, Feb 16 2016

A130665 a(n) = Sum_{k=0..n} 3^wt(k), where wt() = A000120().

Original entry on oeis.org

1, 4, 7, 16, 19, 28, 37, 64, 67, 76, 85, 112, 121, 148, 175, 256, 259, 268, 277, 304, 313, 340, 367, 448, 457, 484, 511, 592, 619, 700, 781, 1024, 1027, 1036, 1045, 1072, 1081, 1108, 1135, 1216, 1225, 1252, 1279, 1360, 1387, 1468, 1549, 1792, 1801, 1828, 1855

Offset: 0

N. J. A. Sloane, based on a message from Don Knuth, Jun 23 2007

Partial sums of A048883. - David Applegate, Jun 11 2009
From Gary W. Adamson, Aug 26 2016: (Start)
The formula of Mar 26 2010 is equivalent to the left-shifted vector of matrix powers (lim_{k->infinity} M^k), of the production matrix M:
  1, 0, 0, 0, 0, 0, ...
  4, 0, 0, 0, 0, 0, ...
  3, 1, 0, 0, 0, 0, ...
  0, 4, 0, 0, 0, 0, ...
  0, 3, 1, 0, 0, 0, ...
  0, 0, 4, 0, 0, 0, ...
  0, 0, 3, 1, 0, 0, ...
  ...
The sequence divided by its aerated variant is (1, 4, 3, 0, 0, 0, ...). (End)

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
David Applegate, The movie version
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, pp. 27, 31-32.
Tanya Khovanova and Joshua Xiong, Nim Fractals, arXiv:1405.594291 [math.CO], 2014 and J. Int. Seq. 17 (2014) # 14.7.8.
D. E. Knuth, Problem 11320 Amer. Math. Monthly, Vol. 114 No. 9 (Nov 2007) p. 835.
Omar E. Pol, Illustration of initial terms: Fig. 1. Neighbors of the vertices, Fig. 2. Overlapping squares, Fig. 3. One-step bishop, (Nov 08 2009)
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Mike Warburton, Ulam-Warburton Automaton - Counting Cells with Quadratics, arXiv:1901.10565 [math.CO], 2019.

Cf. A000120, A006046 (Sum 2^wt(n)), A116520, A130667, A147562, A151920, A151922, A160410, A160412, A360189.

a130665 = sum . map (3 ^) . (`take` a000120_list) . (+ 1)
-- Reinhard Zumkeller, Apr 18 2012

u:=3; a[1]:=1; M:=30; for n from 1 to M do a[2*n] := (u+1)*a[n]; a[2*n+1] := u*a[n] + a[n+1]; od; t1:=[seq( a[n], n=1..2*M )]; # Gives sequence with a different offset

f[n_] := Sum[3^Count[ IntegerDigits[k, 2], 1], {k, 0, n}]; Array[f, 51, 0] (* Robert G. Wilson v, Jun 28 2010 *)

def a(n):  # formula version, n=10^10000 takes ~1 second
    if n == 0:
        return 1
    msb = 1 << (n.bit_length() - 1)
    return msb**2 + 3 * a(n-msb) # Stefan Pochmann, Mar 15 2023

def a(n):  # optimized, n=10^50000 takes ~1 second
    n += 1
    total = 0
    power3 = 1
    while n:
        log = n.bit_length() - 1
        total += power3 << (2*log)
        n -= 1 << log
        power3 *= 3
    return total # Stefan Pochmann, Mar 15 2023

With a different offset: a(1) = 1; a(n) = max { 3*a(k)+a(n-k) | 1 <= k <= n/2 }, for n>1.
a(2n+1) = 4*a(n) and a(2n) = 3*a(n-1) + a(n).
a(n) = (A147562(n+1) - 1)*3/4 + 1. - Omar E. Pol, Nov 08 2009
a(n) = A160410(n+1)/4. - Omar E. Pol, Nov 12 2009
Let r(x) = (1 + 4x + 3x^2), then (1 + 4x + 7x^2 + 16x^3 + ...) =
r(x)* r(x^2) * r(x^4) * r(x^8) * ... - Gary W. Adamson, Mar 26 2010
For asymptotics see the discussion in the comments in A006046. - N. J. A. Sloane, Mar 11 2021
a(n) = Sum_{k=0..floor(log_2(n+1))} 3^k * A360189(n,k). - Alois P. Heinz, Mar 06 2023
a(n) = msb^2 + 3*a(n-msb), where msb = A053644(n). - Stefan Pochmann, Mar 15 2023

Simpler definition (and new offset) from David Applegate, Jun 11 2009

Lower limit of sum in definition changed from 1 to 0 by Robert G. Wilson v, Jun 28 2010

A116520 a(0) = 0, a(1) = 1; a(n) = max { 4*a(k) + a(n-k) | 1 <= k <= n/2 }, for n > 1.

Original entry on oeis.org

0, 1, 5, 9, 25, 29, 45, 61, 125, 129, 145, 161, 225, 241, 305, 369, 625, 629, 645, 661, 725, 741, 805, 869, 1125, 1141, 1205, 1269, 1525, 1589, 1845, 2101, 3125, 3129, 3145, 3161, 3225, 3241, 3305, 3369, 3625, 3641, 3705, 3769, 4025, 4089, 4345, 4601, 5625

Offset: 0

Roger L. Bagula, Mar 15 2006

Equivalently, a(n) = r*a(ceiling(n/2)) + s*a(floor(n/2)), a(0)=0, a(1)=1, for (r,s) = (1,4). - N. J. A. Sloane, Feb 16 2016
A 5-divide version of A084230.
Zero together with the partial sums of A102376. - Omar E. Pol, May 05 2010
Also, total number of cubic ON cells after n generations in a three-dimensional cellular automaton in which A102376(n-1) gives the number of cubic ON cells in the n-th level of the structure starting from the top. An ON cell remains ON forever. The structure looks like an irregular stepped pyramid, with n >= 1. - Omar E. Pol, Feb 13 2015
From Gary W. Adamson, Aug 27 2016: (Start)
The formula of Mar 26 2010 is equivalent to lim_{k->infinity} M^k of the following production matrix M:
  1, 0, 0, 0, 0, 0, ...
  5, 0, 0, 0, 0, 0, ...
  4, 1, 0, 0, 0, 0, ...
  0, 5, 0, 0, 0, 0, ...
  0, 4, 1, 0, 0, 0, ...
  0, 0, 5, 0, 0, 0, ...
  0, 0, 4, 1, 0, 0, ...
  0, 0, 0, 5, 0, 0, ...
  ...
The sequence with offset 1 divided by its aerated variant is (1, 5, 4, 0, 0, 0, ...). (End)

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
K.-N. Chang and S.-C. Tsai, Exact solution of a minimal recurrence, Inform. Process. Lett. 75 (2000), 61-64.
H. Harborth, Number of Odd Binomial Coefficients, Proc. Amer. Math. Soc. 62, 19-22, 1977.
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, pp. 27, 32.
D. E. Knuth, Problem 11320, The American Mathematical Monthly, Vol. 114, No. 9 (Nov., 2007), p. 835.
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Eric Weisstein's World of Mathematics, Stolarsky-Harborth Constant
Index entries for sequences related to cellular automata

Cf. A000120, A006046, A077465, A130665, A130667, A102376, A360189.

Sequences of the form a(n) = r*a(ceiling(n/2)) + s*a(floor(n/2)), a(1)=1, for (r,s) = (1,1), (1,2), (2,1), (1,3), (2,2), (3,1), (1,4), (2,3), (3,2), (4,1): A000027, A006046, A064194, A130665, A073121, A268524, A116520, A268525, A268526, A268527.

import Data.List (transpose)
a116520 n = a116520_list !! n
a116520_list = 0 : zs where
   zs = 1 : (concat $ transpose
                      [zipWith (+) vs zs, zipWith (+) vs $ tail zs])
      where vs = map (* 4) zs
-- Reinhard Zumkeller, Apr 18 2012

a:=proc(n) if n=0 then 0 elif n=1 then 1 elif n mod 2 = 0 then 5*a(n/2) else 4*a((n-1)/2)+a((n+1)/2) fi end: seq(a(n),n=0..52);

b[0] := 0 b[1] := 1 b[n_?EvenQ] := b[n] = 5*b[n/2] b[n_?OddQ] := b[n] = 4*b[(n - 1)/2] + b[(n + 1)/2] a = Table[b[n], {n, 1, 25}]

a(0) = 1, a(1) = 1; thereafter a(2n) = 5a(n) and a(2n+1) = 4a(n) + a(n+1).
Let r(x) = (1 + 5x + 4x^2). Then (1 + 5x + 9x^2 + 25x^3 + ...) = r(x) * r(x^2) * r(x^4) * r(x^8) * ... . - Gary W. Adamson, Mar 26 2010
a(n) = Sum_{k=0..n-1} 4^wt(k), where wt = A000120. - Mike Warburton, Mar 14 2019
a(n) = Sum_{k=0..floor(log_2(n))} 4^k*A360189(n-1,k). - Alois P. Heinz, Mar 06 2023

Edited by N. J. A. Sloane, Apr 16 2006, Jul 02 2008

A090996 Number of leading 1's in binary expansion of n.

Original entry on oeis.org

0, 1, 1, 2, 1, 1, 2, 3, 1, 1, 1, 1, 2, 2, 3, 4, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 5, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2

Offset: 0

Benoit Cloitre, Feb 29 2004

Mirror of triangle A065120. See example. - Omar E. Pol, Oct 17 2013

a(n) is also the least part in the integer partition having viabin number n. The viabin number of an integer partition is defined in the following way. Consider the southeast border of the Ferrers board of the integer partition and consider the binary number obtained by replacing each east step with 1 and each north step, except the last one, with 0. The corresponding decimal form is, by definition, the viabin number of the given integer partition. "Viabin" is coined from "via binary". For example, consider the integer partition [2,2,2,1]. The southeast border of its Ferrers board yields 10100, leading to the viabin number 20. - Emeric Deutsch, Jul 24 2017

			In binary : 14=1110 and there are 3 leading 1's, so a(14)=3.
From _Omar E. Pol_, Oct 17 2013: (Start)
Written as an irregular triangle with row lengths A011782 the sequence begins:
0;
1;
1,2;
1,1,2,3;
1,1,1,1,2,2,3,4;
1,1,1,1,1,1,1,1,2,2,2,2,3,3,4,5;
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,3,3,3,3,4,4,5,6;
Right border gives A001477. Row sums give A000225.
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..65535 (first 10001 terms from Vincenzo Librandi)
Index entries for sequences related to binary expansion of n

a(n) = A007814(1+A030101(n)).

Cf. A279209, A279210, A360189.

a := proc(n) if type(log[2](n+1), integer) then log[2](n+1) else a(floor((1/2)*n)) end if end proc: seq(a(n), n = 0 .. 200); # Emeric Deutsch, Jul 24 2017
# second Maple program:
b:= proc(n, t) `if`(n=0, t,
      b(iquo(n, 2, 'm'), m*(t+1)))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..127);  # Alois P. Heinz, Mar 06 2023

Join[{0},Table[Length@First@Split@IntegerDigits[n,2],{n,30}]] (* Birkas Gyorgy, Mar 09 2011 *) (* adapted by Vincenzo Librandi, Dec 23 2016 *)

a(n) = if(n==0, 0); b=binary(n+1); if(hammingweight(b) == 1, #b-1, a(n\2)) \\ David A. Corneth, Jul 24 2017

a(n) = if(n==0, 0); my(b = binary(n), r = #b); for(i=2, #b, if(!b[i], return(i-1))); r \\ David A. Corneth, Jul 24 2017

a(2^k-1)=k; a(A004754(k))=1; a(A004758(k))=2.
a(2^k-1)=k; for any other n, a(n) = a(floor(n/2)).
a(n) = f(n, 0) with f(n, x) = if n < 2 then n + x else f([n/2], (x+1)*(n mod 2)). - Reinhard Zumkeller, Feb 02 2007
Conjecture: a(n) = w(n+1)*(w(n+1)-w(n)+1) - w(2^(w(n+1)+1)-n-1) for n>0, where w(n) = floor(log_2(n)), that is, A000523(n). - Velin Yanev, Dec 21 2016
a(n) = A360189(n-1,floor(log_2(n))). - Alois P. Heinz, Mar 06 2023

Edited and corrected by Franklin T. Adams-Watters, Apr 08 2006

Sequence had accidentally been shifted left by one step, which was corrected and term a(0)=0 added by Antti Karttunen, Jan 01 2007

A130667 a(1) = 1; a(n) = max{ 5*a(k) + a(n-k) | 1 <= k <= n/2 } for n > 1.

Original entry on oeis.org

1, 6, 11, 36, 41, 66, 91, 216, 221, 246, 271, 396, 421, 546, 671, 1296, 1301, 1326, 1351, 1476, 1501, 1626, 1751, 2376, 2401, 2526, 2651, 3276, 3401, 4026, 4651, 7776, 7781, 7806, 7831, 7956, 7981, 8106, 8231, 8856, 8881, 9006, 9131, 9756, 9881, 10506, 11131

Offset: 1

N. J. A. Sloane, based on a message from Don Knuth, Jun 23 2007

nonn

From Gary W. Adamson, Aug 27 2016: (Start)
The formula of Mar 26 2010 is equivalent to the following: Given the production matrix M below, lim_{k->infinity} M^k as a left-shifted vector generates the sequence.
  1, 0, 0, 0, 0, ...
  6, 0, 0, 0, 0, ...
  5, 1, 0, 0, 0, ...
  0, 6, 0, 0, 0, ...
  0, 5, 1, 0, 0, ...
  0, 0, 6, 0, 0, ...
  0, 0, 5, 1, 0, ...
  ...
The sequence divided by its aerated variant is (1, 6, 5, 0, 0, 0, ...). (End)

Alois P. Heinz, Table of n, a(n) for n = 1..16383
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, pp. 27, 32-33.
D. E. Knuth, Problem 11320, The American Mathematical Monthly, Vol. 114, No. 9 (Nov., 2007), p. 835.

Cf. A000120, A006046, A116520, A130665, A360189.

import Data.List (transpose)
a130667 n = a130667_list !! (n-1)
a130667_list = 1 : (concat $ transpose
   [zipWith (+) vs a130667_list, zipWith (+) vs $ tail a130667_list])
   where vs = map (* 5) a130667_list
-- Reinhard Zumkeller, Apr 18 2012

[&+[5^(2*k - Valuation(Factorial(2*k), 2)): k in [0..n]]: n in [0..50]]; // Vincenzo Librandi, Mar 15 2019

a:= proc(n) option remember;
      `if`(n=1, 1, `if`(irem(n, 2, 'm')=0, 6*a(m), 5*a(m)+a(n-m)))
    end:
seq(a(n), n=1..70); # Alois P. Heinz, Apr 09 2012

a[1]=1; a[n_] := a[n] = If[EvenQ[n], 6a[n/2], 5a[(n-1)/2]+a[(n+1)/2]]; Array[a, 50] (* Jean-François Alcover, Feb 13 2015 *)

first(n)=my(v=vector(n),r,t); v[1]=1; for(i=2,n, r=0; for(k=1,i\2, t=5*v[k]+v[i-k]; if(t>r, r=t)); v[i]=r); v \\ Charles R Greathouse IV, Aug 29 2016

a(2*n) = 6*a(n) and a(2*n+1) = 5*a(n) + a(n+1).
Let r(x) = (1 + 6*x + 5*x^2). Then (1 + 6*x + 11*x^2 + 36*x^3 + ...) = r(x) * r(x^2) * r(x^4) * r(x^8) * ... - Gary W. Adamson, Mar 26 2010
a(n) = Sum_{k=0..n} 5^wt(k), where wt = A000120. - Mike Warburton, Mar 14 2019
a(n) = Sum_{k=0..floor(log_2(n))} 5^k*A360189(n-1,k). - Alois P. Heinz, Mar 06 2023

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Haskell

Maple

Mathematica

PARI

PARI

PARI

PARI

Python

Python

Formula

Extensions

A006046 Total number of odd entries in first n rows of Pascal's triangle: a(0) = 0, a(1) = 1, a(2k) = 3*a(k), a(2k+1) = 2*a(k) + a(k+1). a(n) = Sum_{i=0..n-1} 2^wt(i).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Python

Formula

Extensions

A130665 a(n) = Sum_{k=0..n} 3^wt(k), where wt() = A000120().

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Python

Python

Formula

Extensions

A116520 a(0) = 0, a(1) = 1; a(n) = max { 4*a(k) + a(n-k) | 1 <= k <= n/2 }, for n > 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

Extensions

A090996 Number of leading 1's in binary expansion of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A006046 Total number of odd entries in first n rows of Pascal's triangle: a(0) = 0, a(1) = 1, a(2k) = 3a(k), a(2k+1) = 2a(k) + a(k+1). a(n) = Sum_{i=0..n-1} 2^wt(i).

A116522 a(0)=1, a(1)=1, a(n)=7a(n/2) for n=2,4,6,..., a(n)=6a((n-1)/2)+a((n+1)/2) for n=3,5,7,....

A116525 a(0)=1, a(1)=1, a(n) = 11a(n/2) for even n, and a(n) = 10a((n-1)/2) + a((n+1)/2) for odd n >= 3.

A116526 a(0)=1, a(1)=1, a(n) = 9a(n/2) for even n >= 2, and a(n) = 8a((n-1)/2) + a((n+1)/2) for odd n >= 3.