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, 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

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 22 19:53 EDT 2019. Contains 328319 sequences. (Running on oeis4.)