login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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^n-1) + 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^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

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] (* Jean-Fran├ž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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 22 21:09 EDT 2018. Contains 316505 sequences. (Running on oeis4.)