

A118977


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


19



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

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


LINKS

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
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS


FORMULA

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 * Prod_{ n >= 0} (1 + x^(2^n1) + x^(2^n)) ) / (1+x).  N. J. A. Sloane, Jun 08 2009


EXAMPLE

Comment from N. J. A. Sloane, Jun 01 2009: 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.


MAPLE

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^n1)+x^(2^n);
c:=n>x^(2^n1)*(1x^(2^n));
PP:=proc(n) option remember; global g, c;
if n=1 then 1+2*x else series(g(n1)*PP(n1)c(n1), x, 10000); fi; end; # N. J. A. Sloane, Jun 01 2009


MATHEMATICA

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] (* JeanFrançois Alcover, Nov 10 2016 *)


CROSSREFS

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
Sequence in context: A033763 A033803 A035531 * A071766 A007305 A112531
Adjacent sequences: A118974 A118975 A118976 * A118978 A118979 A118980


KEYWORD

nonn


AUTHOR

Gary W. Adamson, May 07 2006


EXTENSIONS

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


STATUS

approved



