A268526 -id:A268526 - cp's OEIS frontend

A006046 Total number of odd entries in first n rows of Pascal's triangle: a(0) = 0, a(1) = 1, a(2k) = 3a(k), a(2k+1) = 2a(k) + a(k+1). a(n) = Sum_{i=0..n-1} 2^wt(i).

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

Jeffrey Shallit

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

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

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.
Philippe Flajolet, Xavier Gourdon, and Philippe Dumas, Mellin transforms and asymptotics: harmonic sums Special volume on mathematical analysis of algorithms. Theoret. Comput. Sci. 144 (1995), no. 1-2, 3-58.
Philippe Flajolet and Robert Sedgewick, Mellin transforms and asymptotics: Finite differences and Rice's integrals, Theoretical Computer Science 144.1-2 (1995): 101-124.
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.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, pp. 6, 27, 29-31.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Periodic minimum in the count of binomial coefficients not divisible by a prime, arXiv:2408.06817 [math.NT], 2024. See p. 1.
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
Index entries for triangles and arrays related to Pascal's triangle

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.

a006046 = sum . concat . (`take` a047999_tabl)
-- Reinhard Zumkeller, Apr 09 2012

[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

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

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

A006046(n)={ n<2 & return(n); A006046(n\2)*3+if(n%2,1<M. F. Hasler, May 03 2009

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

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

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

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

More terms from James Sellers, Aug 21 2000

Definition expanded by N. J. A. Sloane, Feb 16 2016

A116520 a(0) = 0, a(1) = 1; a(n) = max { 4*a(k) + a(n-k) | 1 <= k <= n/2 }, for n > 1.

Original entry on oeis.org

0, 1, 5, 9, 25, 29, 45, 61, 125, 129, 145, 161, 225, 241, 305, 369, 625, 629, 645, 661, 725, 741, 805, 869, 1125, 1141, 1205, 1269, 1525, 1589, 1845, 2101, 3125, 3129, 3145, 3161, 3225, 3241, 3305, 3369, 3625, 3641, 3705, 3769, 4025, 4089, 4345, 4601, 5625

Offset: 0

Roger L. Bagula, Mar 15 2006

Equivalently, a(n) = r*a(ceiling(n/2)) + s*a(floor(n/2)), a(0)=0, a(1)=1, for (r,s) = (1,4). - N. J. A. Sloane, Feb 16 2016
A 5-divide version of A084230.
Zero together with the partial sums of A102376. - Omar E. Pol, May 05 2010
Also, total number of cubic ON cells after n generations in a three-dimensional cellular automaton in which A102376(n-1) gives the number of cubic ON cells in the n-th level of the structure starting from the top. An ON cell remains ON forever. The structure looks like an irregular stepped pyramid, with n >= 1. - Omar E. Pol, Feb 13 2015
From Gary W. Adamson, Aug 27 2016: (Start)
The formula of Mar 26 2010 is equivalent to lim_{k->infinity} M^k of the following production matrix M:
  1, 0, 0, 0, 0, 0, ...
  5, 0, 0, 0, 0, 0, ...
  4, 1, 0, 0, 0, 0, ...
  0, 5, 0, 0, 0, 0, ...
  0, 4, 1, 0, 0, 0, ...
  0, 0, 5, 0, 0, 0, ...
  0, 0, 4, 1, 0, 0, ...
  0, 0, 0, 5, 0, 0, ...
  ...
The sequence with offset 1 divided by its aerated variant is (1, 5, 4, 0, 0, 0, ...). (End)

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
K.-N. Chang and S.-C. Tsai, Exact solution of a minimal recurrence, Inform. Process. Lett. 75 (2000), 61-64.
H. Harborth, Number of Odd Binomial Coefficients, Proc. Amer. Math. Soc. 62, 19-22, 1977.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, pp. 27, 32.
D. E. Knuth, Problem 11320, The American Mathematical Monthly, Vol. 114, No. 9 (Nov., 2007), p. 835.
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Eric Weisstein's World of Mathematics, Stolarsky-Harborth Constant
Index entries for sequences related to cellular automata

Cf. A000120, A006046, A077465, A130665, A130667, A102376, A360189.

Sequences of the 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.

import Data.List (transpose)
a116520 n = a116520_list !! n
a116520_list = 0 : zs where
   zs = 1 : (concat $ transpose
                      [zipWith (+) vs zs, zipWith (+) vs $ tail zs])
      where vs = map (* 4) zs
-- Reinhard Zumkeller, Apr 18 2012

a:=proc(n) if n=0 then 0 elif n=1 then 1 elif n mod 2 = 0 then 5*a(n/2) else 4*a((n-1)/2)+a((n+1)/2) fi end: seq(a(n),n=0..52);

b[0] := 0 b[1] := 1 b[n_?EvenQ] := b[n] = 5*b[n/2] b[n_?OddQ] := b[n] = 4*b[(n - 1)/2] + b[(n + 1)/2] a = Table[b[n], {n, 1, 25}]

a(0) = 1, a(1) = 1; thereafter a(2n) = 5a(n) and a(2n+1) = 4a(n) + a(n+1).
Let r(x) = (1 + 5x + 4x^2). Then (1 + 5x + 9x^2 + 25x^3 + ...) = r(x) * r(x^2) * r(x^4) * r(x^8) * ... . - Gary W. Adamson, Mar 26 2010
a(n) = Sum_{k=0..n-1} 4^wt(k), where wt = A000120. - Mike Warburton, Mar 14 2019
a(n) = Sum_{k=0..floor(log_2(n))} 4^k*A360189(n-1,k). - Alois P. Heinz, Mar 06 2023

Edited by N. J. A. Sloane, Apr 16 2006, Jul 02 2008

A064194 a(2n) = 3a(n), a(2n+1) = 2a(n+1)+a(n), with a(1) = 1.

Original entry on oeis.org

1, 3, 7, 9, 17, 21, 25, 27, 43, 51, 59, 63, 71, 75, 79, 81, 113, 129, 145, 153, 169, 177, 185, 189, 205, 213, 221, 225, 233, 237, 241, 243, 307, 339, 371, 387, 419, 435, 451, 459, 491, 507, 523, 531, 547, 555, 563, 567, 599, 615, 631, 639, 655, 663, 671, 675

Offset: 1

Guillaume Hanrot and Paul Zimmermann, Sep 21 2001

Number of ring multiplications needed to multiply two degree-n polynomials using Karatsuba's algorithm.
Number of gates in the AND/OR problem (see Chang/Tsai reference).
a(n) is also the number of odd elements in the n X n symmetric Pascal matrix. - Stefano Spezia, Nov 14 2022

A. A. Karatsuba and Y. P. Ofman, Multiplication of multiplace numbers by automata. Dokl. Akad. Nauk SSSR 145, 2, 293-294 (1962).

N. J. A. Sloane, Table of n, a(n) for n = 1..10000
K.-N. Chang and S.-C. Tsai, Exact solution of a minimal recurrence, Inform. Process. Lett. 75 (2000), 61-64.
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.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, pp. 27-28.

Cf. A023416, A267584, A047999 (Sierpinski triangle).
Cf. also A268514.
Sequences of form a(n)=r*a(ceil(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.

[n le 1 select 1 else Self(Floor(n/2)) + 2*Self(Ceiling(n/2)): n in [1..60]]; // Vincenzo Librandi, Aug 30 2016

f:=proc(n) option remember; if n=1 then 1 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=1..60)]; # N. J. A. Sloane, Jan 17 2016

a[n_] := a[n] = If[EvenQ[n], 3 a[n/2], 2 a[# + 1] + a[#] &[(n - 1)/2]]; a[1] = 1; Array[a, 56] (* Michael De Vlieger, Oct 29 2022 *)

a(n) = sum(i=0, n-1, sum(j=0, n-1, binomial(i+j, i) % 2)); \\ Michel Marcus, Aug 25 2013

Partial sums of the sequence { b(1)=1, b(n)=2^(e0(n-1)+1) } (essentially A267584), where e0(n)=A023416(n) is the number of zeros in the binary expansion of n. [Chang/Tsai] - Ralf Stephan, Jul 29 2003
a(1) = 1, a(n) = a(floor(n/2)) + 2*a(ceiling(n/2)), n > 1.
a(n+1) = Sum_{0<=i, j<=n} (binomial(i+j, i) mod 2). - Benoit Cloitre, Mar 07 2005
In particular, a(2^k)=3^k, a(3*2^k)=7*3^k. - N. J. A. Sloane, Jan 18 2016
a(n) = 2*A268514(n-1) + 1. - N. J. A. Sloane, Feb 07 2016

Edited with clearer definition by N. J. A. Sloane, Jan 18 2016

A073121 a(n) = ra(ceiling(n/2)) + sa(floor(n/2)) with a(1)=1 and (r,s)=(2,2).

Original entry on oeis.org

1, 4, 10, 16, 28, 40, 52, 64, 88, 112, 136, 160, 184, 208, 232, 256, 304, 352, 400, 448, 496, 544, 592, 640, 688, 736, 784, 832, 880, 928, 976, 1024, 1120, 1216, 1312, 1408, 1504, 1600, 1696, 1792, 1888, 1984, 2080, 2176, 2272, 2368, 2464, 2560, 2656, 2752

Offset: 1

Jeffrey Shallit, Aug 25 2002

nonn

A recurrence occurring in the analysis of a regular expression algorithm.

			a(1)=1, a(2) = 2*(a(1)+a(1)) = 4, a(3) = 2*(a(2)+a(1)) = 10.

K. Ellul, J. Shallit and M.-w. Wang, Regular expressions: new results and open problems, in Descriptional Complexity of Formal Systems (DCFS), Proceedings of workshop, London, Ontario, Canada, 21-24 August 2002, pp. 17-34.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
Jean-Paul Allouche and Jeffrey Shallit, The Ring of k-regular Sequences, II
F. Barbero, G. Gutin, M. Jones, and B. Sheng, Parameterized and approximation algorithms for the load coloring problem, Algorithmica 79, No. 1, 211-229 (2017). Prop 3.
Keh-Ning Chang and Shi-Chun Tsai, Exact solution of a minimal recurrence, Inform. Process. Lett. 75 (2000), 61-64.
Erik D. Demaine, Martin L. Demaine, Yair N. Minsky, Joseph S. B. Mitchell, Ronald L. Rivest, and Mihai Patrascu, Picture-Hanging Puzzles, arXiv:1203.3602 [cs.DS], 2012-2014.
Keith Ellul, Bryan Krawetz, Jeffrey Shallit, and Ming-wei Wang, Regular expressions: new results and open problems, Journal of Automata, Languages and Combinatorics, preprint.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, pp. 27, 37.
Jean-Marc Luck, Revisiting log-periodic oscillations, arXiv:2403.00432 [cond-mat.stat-mech], 2024. See p. 14.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions

Cf. A053644, A053645, A254575.

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.

a073121 n = a053644 n * (fromIntegral n + 2 * a053645 n)
-- Reinhard Zumkeller, Mar 23 2012

a:= proc(n) option remember; `if`(n=1, 1,
      2*((m-> a(m)+a(n-m))(iquo(n, 2))))
    end:
seq(a(n), n=1..70);  # Alois P. Heinz, Feb 01 2015

a[n_] := a[n] = If[n == 1, 1, 2*(a[Quotient[n, 2]] + a[n - Quotient[n, 2]])]; Table[a[n], {n, 1, 70}] (* Jean-François Alcover, Feb 24 2016, after Alois P. Heinz *)
a[ n_] := If[ n < 1, 0, Module[{m = 1, A = 1}, While[m < n, m *= 2; A = (Normal[A] /. x -> x^2) 2 (1 + x)^2 - 1 + O[x]^m]; Coefficient[A, x, n - 1]]]; (* Michael Somos, Jul 04 2017 *)

{a(n) = n--; if( n<0, 0, my(m=1, A = 1 + O(x)); while(m<=n, m*=2; A = subst(A, x, x^2) * 2 * (1 + x)^2 - 1); polcoeff(A, n))}; /* Michael Somos, Jul 04 2017 */

a(n) = 2*(a(floor(n/2)) + a(ceiling(n/2))) for n >= 2; alternatively, a(n) = 2^c(n+2b) where n = 2^c + b, 0 <= b < 2^c.
a(n) == 1 (mod 3), a(n+1)-a(n) = 3*A053644(n). If k >= 1: a(2^k)=4^k, a(3*2^k)=(10/9)*4^k. More generally a(m*2^k) = a(m)*4^k. Hence for any n, n^2 <= a(n) <= C*n^2 where C is a constant 1.125 < C < 1.14 and it seems that C = lim_{k->infinity} a(A001045(k))/A001045(k)^2 where A001045(k) =(2^n - (-1)^n)/3 is the Jacobsthal sequence. In other words, in the range 2^k <= n <= 2^(k+1) the maximum of a(n)/n^2 is reached for the only possible n in the Jacobsthal sequence. - Benoit Cloitre, Aug 26 2002
For any n, n^2 <= a(n) <= 9/8 * n^2. - Arnoud van der Leer, Sep 01 2019
a(n) = 2*(a(floor(n/2)) + a(ceiling(n/2))) for n >= 2; alternatively, a(n) = 2^c(n+2b) where n = 2^c + b, 0 <= b < 2^c
G.f.: 3*x/(1-x)^2 * ((2*x+1)/3 + Sum_{k>=1} 2^(k-1)*x^2^k). - Ralf Stephan, Apr 18 2003
G.f.: A(x) = 2 * (1/x + 2 + x) * A(x^2) - x. - Michael Somos, Jul 04 2017

Edited by N. J. A. Sloane, Feb 16 2016

Number of triples 0 <= i, j, k < n such that bitwise AND of all pairs (i, j), (j, k), (k, i) is 0. - Peter Karpov, Mar 01 2016

Start with A = [[[1]]], iteratively replace every element Aijk with Aijk * [[[1, 1], [1, 0]], [[1, 0], [0, 0]]]. a(n) is the sum of the resulting array inside the cubic region i, j, k < n. - Peter Karpov, Mar 01 2016

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Python

Formula

Extensions

A116520 a(0) = 0, a(1) = 1; a(n) = max { 4*a(k) + a(n-k) | 1 <= k <= n/2 }, for n > 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

Extensions

A064194 a(2n) = 3*a(n), a(2n+1) = 2*a(n+1)+a(n), with a(1) = 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A073121 a(n) = r*a(ceiling(n/2)) + s*a(floor(n/2)) with a(1)=1 and (r,s)=(2,2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A268524 a(n) = r*a(ceiling(n/2))+s*a(floor(n/2)) with a(1)=1 and (r,s)=(3,1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A268525 a(n) = r*a(ceiling(n/2))+s*a(floor(n/2)) with a(1)=1 and (r,s)=(2,3).

Views

Author

Keywords

Links

Crossrefs

Programs

A006046 Total number of odd entries in first n rows of Pascal's triangle: a(0) = 0, a(1) = 1, a(2k) = 3a(k), a(2k+1) = 2a(k) + a(k+1). a(n) = Sum_{i=0..n-1} 2^wt(i).

A064194 a(2n) = 3a(n), a(2n+1) = 2a(n+1)+a(n), with a(1) = 1.

A073121 a(n) = ra(ceiling(n/2)) + sa(floor(n/2)) with a(1)=1 and (r,s)=(2,2).

A268524 a(n) = ra(ceiling(n/2))+sa(floor(n/2)) with a(1)=1 and (r,s)=(3,1).

A268525 a(n) = ra(ceiling(n/2))+sa(floor(n/2)) with a(1)=1 and (r,s)=(2,3).

A268527 a(n) = ra(ceiling(n/2))+sa(floor(n/2)) with a(1)=1 and (r,s)=(4,1).