A163267 -id:A163267 - 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

A162958 Equals A162956 convolved with (1, 3, 3, 3, ...).

Original entry on oeis.org

1, 4, 10, 19, 25, 40, 67, 94, 100, 115, 142, 175, 208, 280, 388, 469, 475, 490, 517, 550, 583, 655, 763, 850, 883, 955, 1069, 1201, 1372, 1696, 2101, 2344, 2350, 2365, 2392, 2425, 2458, 2530, 2638, 2725, 2758, 2830, 2944, 3076, 3247, 3571, 3976, 4225, 4258

Offset: 1

Gary W. Adamson, Jul 18 2009

nonn

Can be considered a toothpick sequence for N=3, following rules analogous to those in A160552 (= special case of "A"), A151548 = special case "B", and the toothpick sequence A139250 (N=2) = special case "C".
To obtain the infinite set of toothpick sequences, (N = 2, 3, 4, ...), replace the multiplier "2" in A160552 with any N, getting a triangle with 2^n terms. Convolve this A sequence with (1, N, 0, 0, 0, ...) = B such that row terms of A triangles converge to B.
Then generalized toothpick sequences (C) = A convolved with (1, N, N, N, ...).
Examples: A160552 * (1, 2, 0, 0, 0,...) = a B-type sequence A151548.
A160552 * (1, 2, 2, 2, 2,...) = the toothpick sequence A139250 for N=2.
A162956 is analogous to A160552 but replaces "2" with the multiplier "3".
Row terms of A162956 tend to A162957 = (1, 3, 0, 0, 0, ...) * A162956.
Toothpick sequence for N = 3 = A162958 = A162956 * (1, 3, 3, 3, ...).
Row sums of "A"-type triangles = powers of (N+2); since row sums of A160552 = (1, 4, 16, 64, ...), while row sums of A162956 = (1, 5, 25, 125, ...).
Is there an illustration of this sequence using toothpicks? - Omar E. Pol, Dec 13 2016

Alois P. Heinz, Table of n, a(n) for n = 1..16384
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

Cf. A139250, A152548, A160552, A162956, A163267.

Third diagonal of A163311.

b:= proc(n) option remember; `if`(n<2, n,
      (j-> 3*b(j)+b(j+1))(n-2^ilog2(n)))
    end:
a:= proc(n) option remember;
      `if`(n=0, 0, a(n-1)+2*b(n-1)+b(n))
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Jan 28 2017

b[n_] := b[n] = If[n<2, n, Function[j, 3*b[j]+b[j+1]][n-2^Floor[Log[2, n]] ]];
a[n_] := a[n] = If[n == 0, 0, a[n-1] + 2*b[n-1] + b[n]];
Array[a, 100] (* Jean-François Alcover, Jun 11 2018, after Alois P. Heinz *)

Clarified definition by Omar E. Pol, Feb 06 2017

A163311 Triangle read by rows in which the diagonals give the infinite set of Toothpick sequences.

Original entry on oeis.org

1, 1, 2, 1, 3, 4, 1, 4, 7, 5, 1, 5, 10, 11, 7, 1, 6, 13, 19, 15, 10, 1, 7, 16, 29, 25, 23, 13, 1, 8, 19, 41, 37, 40, 35, 14, 1, 9, 22, 55, 51, 61, 67, 43, 16, 1, 10, 25, 71, 67, 86, 109, 94, 47, 19, 1, 11, 28, 89, 85, 115, 161, 173, 100, 55, 22, 1, 12, 31, 109, 105, 148, 223, 286, 181

Offset: 1

Gary W. Adamson, Jul 24 2009

Apart from the second diagonal (which gives the toothpick sequence A139250), the rest of the diagonals cannot be represented with toothpick structures. - Omar E. Pol, Dec 14 2016

			Triangle begins:
1;
1, 2;
1, 3,  4;
1, 4,  7,  5;
1, 5,  10, 11,  7;
1, 6,  13, 19,  15,  10;
1, 7,  16, 29,  25,  23,  13;
1, 8,  19, 41,  37,  40,  35,  14;
1, 9,  22, 55   51,  61,  67,  43,  16;
1, 10, 25, 71,  67,  86,  109, 94,  47,  19;
1, 11, 28, 89,  85,  115, 161, 173, 100, 55,  22;
1, 12, 31, 109, 105, 148, 223, 286, 181, 115, 67,  25;
1, 13, 34, 131, 127, 185, 295, 439, 296, 205, 142, 79,  30;
1, 14, 37, 155, 151, 226, 377, 638, 451, 331, 253, 175, 95, 36;
...

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

Row sums = A163312: (1, 3, 8, 17, 34, 64,...).
Right border = A163267, toothpick sequence for N=1.
Next diagonal going to the left = A139250, toothpick sequence for N=2.
Then 1, 4, 10, 19,... = A162958, toothpick sequence for N=3.
Cf. A160552, A162958, A163311, A163312.

See A162958 for rules governing the generation of N-th Toothpick sequences. By way of example, (N+2), A139250. The generator is A160552, which uses the multiplier "2". Then A160552 convolved with (1, 2, 2, 2,...) = A139250 the Toothpick sequence for N=2. Similarly, we create an array for Toothpick sequences N=1, 2, 3,...etc = A163267, A139250, A162958,...; then take the antidiagonals, creating triangle A163311.

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

A162958 Equals A162956 convolved with (1, 3, 3, 3, ...).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A163311 Triangle read by rows in which the diagonals give the infinite set of Toothpick sequences.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula