|
%I M2445 #189 Jan 08 2024 09:03:25
%S 0,1,3,5,9,11,15,19,27,29,33,37,45,49,57,65,81,83,87,91,99,103,111,
%T 119,135,139,147,155,171,179,195,211,243,245,249,253,261,265,273,281,
%U 297,301,309,317,333,341,357,373,405,409,417,425,441,449,465,481,513,521
%N 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).
%C 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
%C 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.
%C 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
%C a(n) = sum of (n-1)-th row terms of triangle A166556. - _Gary W. Adamson_, Oct 17 2009
%C From _Gary W. Adamson_, Dec 06 2009: (Start)
%C Let M = an infinite lower triangular matrix with (1, 3, 2, 0, 0, 0, ...) in every column shifted down twice:
%C 1;
%C 3;
%C 2; 1;
%C 0, 3;
%C 0, 2, 1;
%C 0, 0, 3;
%C 0, 0, 2, 1;
%C 0, 0, 0, 3;
%C 0, 0, 0, 2, 1;
%C ...
%C This sequence starting with "1" = lim_{n->infinity} M^n, the left-shifted vector considered as a sequence. (End)
%C 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
%C 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
%C 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
%D S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 2.16.
%D Flajolet, Philippe, and Mordecai Golin. "Mellin transforms and asymptotics." Acta Informatica 31.7 (1994): 673-696.
%D 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.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H N. J. A. Sloane, <a href="/A006046/b006046.txt">Table of n, a(n) for n = 0..16383</a> (first 1000 terms from T. D. Noe)
%H L. Carlitz, <a href="http://dx.doi.org/10.1007/BF02843799">The number of binomial coefficients divisible by a fixed power of a prime</a>, Rend. Circ. Mat. Palermo (2) 16 (1967), pp. 299-320.
%H K.-N. Chang and S.-C. Tsai, <a href="http://dx.doi.org/10.1016/S0020-0190(00)00076-4">Exact solution of a minimal recurrence</a>, Inform. Process. Lett. 75 (2000), 61-64.
%H Prerona Chatterjee, Kshitij Gajjar, and Anamay Tengse, <a href="https://arxiv.org/abs/2202.13103">Transparency Beyond VNP in the Monotone Setting</a>, arXiv:2202.13103 [cs.CC], 2022.
%H S. R. Finch, P. Sebah and Z.-Q. Bai, <a href="http://arXiv.org/abs/0802.2654">Odd Entries in Pascal's Trinomial Triangle</a>, arXiv:0802.2654 [math.NT], 2008.
%H N. J. Fine, <a href="http://www.jstor.org/stable/2304500">Binomial coefficients modulo a prime</a>, Amer. Math. Monthly 54:10 (1947), pp. 89-92.
%H Philippe Flajolet, Peter Grabner, Peter Kirschenhofer, Helmut Prodinger and Robert F. Tichy, <a href="https://doi.org/10.1016/0304-3975(92)00065-Y">Mellin Transforms And Asymptotics: Digital Sums</a>, Theoret. Computer Sci. 23 (1994), 291-314.
%H Philippe Flajolet, Xavier Gourdon, and Philippe Dumas, <a href="https://doi.org/10.1016/0304-3975(95)00002-E">Mellin transforms and asymptotics: harmonic sums</a> Special volume on mathematical analysis of algorithms. Theoret. Comput. Sci. 144 (1995), no. 1-2, 3-58.
%H Philippe Flajolet and Robert Sedgewick, <a href="https://doi.org/10.1016/0304-3975(94)00281-M">Mellin transforms and asymptotics: Finite differences and Rice's integrals</a>, Theoretical Computer Science 144.1-2 (1995): 101-124.
%H P. J. Grabner and H.-K. Hwang, <a href="http://algo.stat.sinica.edu.tw/hk/files/2005_07/pdf/Digital_sums_and_divide-and-conquer_recurrences.pdf">Digital sums and divide-and-conquer recurrences: Fourier expansions and absolute convergence</a>, Constructive Approximation, Jan. 2005, Volume 21, Issue 2, pp 149-179.
%H H. Harborth, <a href="http://dx.doi.org/10.1090/S0002-9939-1977-0429714-1">Number of Odd Binomial Coefficients</a>, Proc. Amer. Math. Soc. 62, 19-22, 1977.
%H H. Harborth, <a href="/A006046/a006046_1.pdf">Number of Odd Binomial Coefficients</a>, Proc. Amer. Math. Soc. 62.1 (1977), 19-22. (Annotated scanned copy)
%H F. T. Howard, <a href="http://dx.doi.org/10.1090/S0002-9939-1971-0302459-9">The number of binomial coefficients divisible by a fixed power of 2</a>, Proceedings of the American Mathematical Society, Vol. 29:2 (Jul 1971), pp. 236-242.
%H 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, pp. 6, 27, 29-31.
%H Akhlesh Lakhtakia and Russell Messier, <a href="http://dx.doi.org/10.1016/0097-8493(89)90038-1">Self-similar sequences and chaos from Gauss sums</a>, Computers & graphics 13.1 (1989): 59-62.
%H Akhlesh Lakhtakia and Russell Messier, <a href="/A006046/a006046.pdf">Self-similar sequences and chaos from Gauss sums</a>, Computers & Graphics 13.1 (1989), 59-60. (Annotated scanned copy)
%H A. Lakhtakia et al., <a href="http://dx.doi.org/10.1088/0305-4470/21/8/030">Fractal sequences derived from the self-similar extensions of the Sierpinski gasket</a>, J. Phys. A 21 (1988), 1925-1928.
%H Giuseppe Lancia and Paolo Serafini, <a href="https://doi.org/10.3390/a14080235">Computational Complexity and ILP Models for Pattern Problems in the Logical Analysis of Data</a>, Algorithms (2021) Vol. 14, No. 8, 235.
%H N. J. A. Sloane, <a href="http://arxiv.org/abs/1503.01168">On the Number of ON Cells in Cellular Automata</a>, arXiv:1503.01168 [math.CO], 2015.
%H Ralf Stephan, <a href="https://arxiv.org/abs/math/0307027">Divide-and-conquer generating functions. I. Elementary sequences</a>, arXiv:math/0307027 [math.CO], 2003.
%H K. B. Stolarsky, <a href="http://dx.doi.org/10.1137/0132060">Power and exponential sums of digital sums related to binomial coefficient parity</a>, SIAM J. Appl. Math., 32 (1977), 717-730. See B(n). - _N. J. A. Sloane_, Apr 05 2014
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PascalsTriangle.html">Pascal's Triangle</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Rule90.html">Rule 90</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Stolarsky-HarborthConstant.html">Stolarsky-Harborth Constant</a>
%H <a href="/index/Pas#Pascal">Index entries for triangles and arrays related to Pascal's triangle</a>
%F a(n) = Sum_{k=0..n-1} 2^A000120(k). - _Paul Barry_, Jan 05 2005; simplified by _N. J. A. Sloane_, Apr 05 2014
%F For asymptotics see Stolarsky (1977). - _N. J. A. Sloane_, Apr 05 2014
%F a(n) = a(n-1) + A001316(n-1). a(2^n) = 3^n. - _Henry Bottomley_, Apr 05 2001
%F 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
%F 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
%F a(1) = 1, a(n) = 2*a(floor(n/2)) + a(ceiling(n/2)).
%F a(n) = 3*a(floor(n/2)) + (n mod 2)*2^A000120(n-1). - _M. F. Hasler_, May 03 2009
%F a(n) = Sum_{k=0..floor(log_2(n))} 2^k * A360189(n-1,k). - _Alois P. Heinz_, Mar 06 2023
%p f:=proc(n) option remember;
%p if n <= 1 then n elif n mod 2 = 0 then 3*f(n/2)
%p else 2*f((n-1)/2)+f((n+1)/2); fi; end;
%p [seq(f(n),n=0..130)]; # _N. J. A. Sloane_, Jul 29 2014
%t f[n_] := Sum[ Mod[ Binomial[n, k], 2], {k, 0, n} ]; Table[ Sum[ f[k], {k, 0, n} ], {n, 0, 100} ]
%t Join[{0},Accumulate[Count[#,_?OddQ]&/@Table[Binomial[n,k],{n,0,60},{k,0,n}]]] (* _Harvey P. Dale_, Dec 10 2014 *)
%t FoldList[Plus, 0, Total /@ CellularAutomaton[90, Join[Table[0, {#}], {1}, Table[0, {#}]], #]][[2 ;; -1]] &@50 (* _Bradley Klee_, Dec 23 2018 *)
%o (PARI) A006046(n)={ n<2 & return(n); A006046(n\2)*3+if(n%2,1<<norml2(binary(n\2))) } \\ _M. F. Hasler_, May 03 2009
%o (Haskell)
%o a006046 = sum . concat . (`take` a047999_tabl)
%o -- _Reinhard Zumkeller_, Apr 09 2012
%o (Python) from functools import lru_cache
%o @lru_cache(maxsize=None)
%o 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
%o (Magma) [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
%Y Partial sums of A001316.
%Y See A130665 for Sum 3^wt(n).
%Y a(n) = A074330(n-1) + 1 for n >= 2. A080978(n) = 2*a(n) + 1. Cf. A080263.
%Y Cf. also A159912, A166556, A038183, A048896, A360189.
%Y 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.
%K nonn,nice,easy,look
%O 0,3
%A _Jeffrey Shallit_
%E More terms from _James A. Sellers_, Aug 21 2000
%E Definition expanded by _N. J. A. Sloane_, Feb 16 2016
|
