The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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). For n>0, a(n) = Sum_{i=0..n-1} 2^wt(i). (Formerly M2445) 62
 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 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 COMMENTS 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 REFERENCES 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, Xavier Gourdon, and Philippe Dumas. "Mellin transforms and asymptotics: Harmonic sums." Theoretical computer science 144.1-2 (1995): 3-58. 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. Flajolet, Philippe, and Robert Sedgewick. "Mellin transforms and asymptotics: Finite differences and Rice's integrals." Theoretical Computer Science 144.1-2 (1995): 101-124. N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence). LINKS T. D. Noe and 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. 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. 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 FORMULA 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 MAPLE 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 MATHEMATICA 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 *) PROG (PARI) A006046(n)={ n<2 & return(n); A006046(n\2)*3+if(n%2, 1<= 2. A080978(n) = 2*a(n) + 1. Cf. A080263. Cf. also A159912, A166556, A038183, A048896. 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. Sequence in context: A292918 A216091 A002731 * A161830 A151922 A233762 Adjacent sequences:  A006043 A006044 A006045 * A006047 A006048 A006049 KEYWORD nonn,nice,easy,look AUTHOR EXTENSIONS More terms from James A. Sellers, Aug 21 2000 Definition expanded by N. J. A. Sloane, Feb 16 2016 STATUS approved

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

Last modified October 2 05:52 EDT 2022. Contains 357191 sequences. (Running on oeis4.)