A151687 -id:A151687 - cp's OEIS frontend

A118977 a(0)=0, a(1)=1; a(2^i+j) = a(j) + a(j+1) for 0 <= j < 2^i.

0, 1, 1, 2, 1, 2, 3, 3, 1, 2, 3, 3, 3, 5, 6, 4, 1, 2, 3, 3, 3, 5, 6, 4, 3, 5, 6, 6, 8, 11, 10, 5, 1, 2, 3, 3, 3, 5, 6, 4, 3, 5, 6, 6, 8, 11, 10, 5, 3, 5, 6, 6, 8, 11, 10, 7, 8, 11, 12, 14, 19, 21, 15, 6, 1, 2, 3, 3, 3, 5, 6, 4, 3, 5, 6, 6, 8, 11, 10, 5, 3, 5, 6, 6, 8, 11, 10, 7, 8, 11, 12, 14, 19, 21, 15

Offset: 0

Gary W. Adamson, May 07 2006

nonn

The original definition from Gary W. Adamson: Iterative sequence in 2^n subsets generated from binomial transform operations. Let S = a string s(1) through s(2^n); and B = appended string. Say S = (1, 1, 2, 1). Perform the binomial transform operation on S as a vector: [1, 1, 2, 1, 0, 0, 0, ...] = 1, 2, 5, 11, 21, 36, ... Then, performing the analogous operation on B gives a truncated version of the previous sequence: (2, 5, 11, 21, ...). Given a subset s(1) through s(2^n), say s(1), ..., s(4) = (a,b,c,d). Use the operation ((a+b), (b+c), (c+d), d) and append the result to the right of the previous string. Perform the next operation on s(1) through s(2^(n+1)). s(1), ..., s(4) = (1, 1, 2, 1). The operation gives ((1+1), (1+2), (2+1), (1)) = (2, 3, 3, 1) which we append to (1, 1, 2, 1), giving s(1) through s(8): (1, 1, 2, 1, 2, 3, 3, 1).

			From _N. J. A. Sloane_, Jun 01 2009: (Start)
Has a natural structure as a triangle:
  0,
  1,
  1,2,
  1,2,3,3,
  1,2,3,3,3,5,6,4,
  1,2,3,3,3,5,6,4,3,5,6,6,8,11,10,5,
  1,2,3,3,3,5,6,4,3,5,6,6,8,11,10,5,3,5,6,6,8,11,10,7,8,11,12,14,19,21,15,6,
  1,2,3,3,3,5,6,4,3,5,...
In this form the rows converge to (1 followed by A160573) or A151687. (End)

N. J. A. Sloane, Table of n, a(n) for n = 0..9999
David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

For the recurrence a(2^i+j) = C*a(j) + D*a(j+1), a(0) = A, a(1) = B for following values of (A B C D) see: (0 1 1 1) A118977, (1 0 1 1) A151702, (1 1 1 1) A151570, (1 2 1 1) A151571, (0 1 1 2) A151572, (1 0 1 2) A151703, (1 1 1 2) A151573, (1 2 1 2) A151574, (0 1 2 1) A160552, (1 0 2 1) A151704, (1 1 2 1) A151568, (1 2 2 1) A151569, (0 1 2 2) A151705, (1 0 2 2) A151706, (1 1 2 2) A151707, (1 2 2 2) A151708.
Cf. A160552, A151568, A151569, A151570, A160573, A139250. - N. J. A. Sloane, May 25 2009
Cf. A163267 (partial sums). - N. J. A. Sloane, Jan 07 2010

Maple code for the rows of the triangle (PP(n) is a g.f. for the (n+1)-st row):
g:=n->1+x^(2^n-1)+x^(2^n);
c:=n->x^(2^n-1)*(1-x^(2^n));
PP:=proc(n) option remember; global g,c;
if n=1 then 1+2*x else series(g(n-1)*PP(n-1)-c(n-1),x,10000); fi; end; # N. J. A. Sloane, Jun 01 2009

a[0] = 0; a[1] = 1; a[n_] := a[n] = (j = n - 2^Floor[Log[2, n]]; a[j] + a[j + 1]); Array[a, 95, 0] (* Jean-François Alcover, Nov 10 2016 *)

a(0)=0; a(2^i)=1. For n >= 3 let n = 2^i + j, where 1 <= j < 2^i. Then a(n) = Sum_{k >= 0} binomial( wt(j+k),k ), where wt() = A000120(). - N. J. A. Sloane, Jun 01 2009

G.f.: ( x + x^2 * Product_{ n >= 0} (1 + x^(2^n-1) + x^(2^n)) ) / (1+x). - N. J. A. Sloane, Jun 08 2009

New definition and more terms from N. J. A. Sloane, May 25 2009

A160573 G.f.: Product_{k >= 0} (1 + x^(2^k-1) + x^(2^k)).

Original entry on oeis.org

2, 3, 3, 3, 5, 6, 4, 3, 5, 6, 6, 8, 11, 10, 5, 3, 5, 6, 6, 8, 11, 10, 7, 8, 11, 12, 14, 19, 21, 15, 6, 3, 5, 6, 6, 8, 11, 10, 7, 8, 11, 12, 14, 19, 21, 15, 8, 8, 11, 12, 14, 19, 21, 17, 15, 19, 23, 26, 33, 40, 36, 21, 7, 3, 5, 6, 6, 8, 11, 10, 7, 8, 11, 12, 14, 19, 21, 15, 8, 8

Offset: 0

Hagen von Eitzen, May 20 2009

nonn

Sequence mentioned in the Applegate-Pol-Sloane article; see Section 9, "explicit formulas." - Omar E. Pol, Sep 20 2011

			a(5) = binomial(2,0) + binomial(2,1) + binomial(3,2) + binomial(1,3) + binomial(2,4) + binomial(2,5) + ... = 1 + 2 + 3 + 0 + 0 + 0 + ... = 6
From _Omar E. Pol_, Jun 09 2009: (Start)
Triangle begins:
2;
3;3;
3,5,6,4;
3,5,6,6,8,11,10,5;
3,5,6,6,8,11,10,7,8,11,12,14,19,21,15,6;
3,5,6,6,8,11,10,7,8,11,12,14,19,21,15,8,8,11,12,14,19,21,17,15,19,23,26,...
(End)

D. Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191

David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.], which is also available at arXiv:1004.3036v2
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

For generating functions of the form Product_{k>=c} (1+a*x^(2^k-1)+b*x^2^k) for the following values of (a,b,c) see: (1,1,0) A160573, (1,1,1) A151552, (1,1,2) A151692, (2,1,0) A151685, (2,1,1) A151691, (1,2,0) A151688 and A152980, (1,2,1) A151550, (2,2,0) A151693, (2,2,1) A151694.
Row sums of A151683. See A151687 for another version.
Cf. A151552 (g.f. has one factor fewer).
Limiting form of rows of A118977 when that sequence is written as a triangle and the initial 1 is omitted. - N. J. A. Sloane, Jun 01 2009
Cf. A139250, A139251. - Omar E. Pol, Sep 20 2011

Maple
```
See A118977 for Maple code.
```

max = 80; Product[1 + x^(2^k - 1) + x^(2^k), {k, 0, Ceiling[Log[2, max]]}] + O[x]^max // CoefficientList[#, x]& (* Jean-François Alcover, Nov 10 2016 *)

a(n) = Sum_{i >= 0} binomial(A000120(n+i),i).
For k >= 1, a(2^k-2) = k+1 and a(2^k-1) = 3; otherwise if n = 2^i + j, 0 <= j <= 2^i-3, a(n) = a(j) + a(j+1).
a(n) = 2*A151552(n) + A151552(n-1).

cp's OEIS Frontend

A118977 a(0)=0, a(1)=1; a(2^i+j) = a(j) + a(j+1) for 0 <= j < 2^i.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions