A remarkable sequence (FWD)

[David W. Wilson]

Antreas P. Hatzipolakis wrote:

> From: xpolakis at hol.gr (Antreas P. Hatzipolakis)
> Newsgroups: sci.math
> Subject: Re: A remarkable sequence
> Date: 26 May 1999 16:32:25 GMT
>
> In article <374AC3C2.73CE0B0A at virginia.edu>, "Charles H. Giffen"
> <chg4k at virginia.edu> wrote:
>
> > Here's a recursive definition of a remarkable sequence
> > a[0],a[1],a[2],...  of positive integers:
> >
> >         a[0] = 1
> >
> >         a[2k+1] = a[k]  for  k = 0,1,2,...
> >
> >         a[2k] = a[k-1] + a[k}  for  k = 1,2,3,...
> >
> > The first few terms of this sequence are:
> >
> >  k      0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17
> > a[k]    1  1  2  1  3  2  3  1  4  3  5  2  5  3  4  1  5  4
> >
> >  18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
> >   7  3  8  5  7  2  7  5  8  3  7  4  5  1  6  5  9  4 11  7

I prefer the prettier recurrence

   a(0) = 0;  a(2k) = a(k);   a(2k+1) = a(k) + a(k+1)

which generates the same sequence prepended by 0.