cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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

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

Views

Author

Jeffrey Shallit

Keywords

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

Links

Crossrefs

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.

Programs

  • Haskell
    a006046 = sum . concat . (`take` a047999_tabl)
-- Reinhard Zumkeller, Apr 09 2012
  • 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
  • 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 *)
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 *)
  • PARI
    A006046(n)={ n<2 & return(n); A006046(n\2)*3+if(n%2,1<M. F. Hasler, May 03 2009
  • PARI
    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
  • Python
    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
  • Python
    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

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
a(n) = Sum_{k=0..floor(log_2(n))} 2^k * A360189(n-1,k). - Alois P. Heinz, Mar 06 2023

Extensions

More terms from James Sellers, Aug 21 2000
Definition expanded by N. J. A. Sloane, Feb 16 2016

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.