login
This site is supported by donations to The OEIS Foundation.

 

Logo


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).
(Formerly M2445)
58

%I M2445

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

%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..inf.} 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 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H T. D. Noe and 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 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 P. Flajolet et al., <a href="http://algo.inria.fr/flajolet/Publications/FlGrKiPrTi94.pdf">Mellin Transforms And Asymptotics: Digital Sums</a>, Theoret. Computer Sci. 23 (1994), 291-314.

%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 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 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 R. Stephan, <a href="http://arXiv.org/abs/math.CO/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

%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 (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 a(n) = A074330(n-1) + 1 for n >= 2. A080978(n) = 2*a(n) + 1. Cf. A080263.

%Y Cf. also A159912, A166556, A038183, A048896.

%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

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 February 19 16:02 EST 2019. Contains 320311 sequences. (Running on oeis4.)