

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..n1} 2^wt(i).
(Formerly M2445)


63



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 nonconvex sequences that solve a recurrence that involves minimization: a(1) = 1; a(n) = max { ua(k) + a(nk)  1 <= k <= n/2 }, for n > 1; here u is any realvalued constant >= 1. The case u=2 gives the present sequence. Cf. A130665  A130667.  Don Knuth, Jun 18 2007
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 leftshifted vector considered as a sequence. (End)
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): 673696.
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. 241254.
Flajolet, Philippe, and Robert Sedgewick. "Mellin transforms and asymptotics: Finite differences and Rice's integrals." Theoretical Computer Science 144.12 (1995): 101124.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS

Eric Weisstein's World of Mathematics, Rule 90


FORMULA

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/(1x))*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)).


MAPLE

f:=proc(n) option remember;
if n <= 1 then n elif n mod 2 = 0 then 3*f(n/2)
else 2*f((n1)/2)+f((n+1)/2); fi; end;


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

(Haskell)
a006046 = sum . concat . (`take` a047999_tabl)
(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


CROSSREFS

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.


KEYWORD



AUTHOR



EXTENSIONS



STATUS

approved



