A remarkable sequence (FWD)

[David W. Wilson]

Also, this sequence gives the concatenation of denominators of Farey fractions.

0/1 1/1
0/1 1/2 1/1
0/1 1/3 1/2 2/3 1/1
0/1 1/4 1/3 2/5 1/2 3/5 2/3 3/4 1/1
etc.

The sequence is gotten by taking the above list, removing the 0/1 entries,
concatenating the rows, and slicing off the numerators.

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
>
> [...]
>
> From Sloane's _Encyclopedia_:
>
> http://www.research.att.com/~njas/sequences/index.html
>
> ID Number: A002487 (Formerly M0141 and N0056)
> Sequence:
> 1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,1,5,4,7,3,8,5,7,2,7,5,8,3,7,4,5,1,6,5,9,
>
> 4,11,7,10,3,11,8,13,5,12,7,9,2,9,7,12,5,13,8,11,3,10,7,11,4,9,5,6,1,7,
>         6,11,5,14,9,13,4,15,11,18,7,17,10,13,3,14,11,19,8,21,13,18,5,17,12,19. 7
> Name:      Stern's diatomic series: a(2n+1) = a(n), a(2n) = a(n) + a(n-1).
> Comments:  a(n)=number of odd binomial(n-k,k),0<=2k<n [Carlitz].
> Refs.:     TCS 98 187 1992.
> References de Rham, Georges; Un peu de mathematiques a propos d'une courbe
> plane. Elemente der Math.
>            2, (1947). 73-76, 89-97.
>            D. H. Lehmer, On Stern's Diatomic Series, Amer. Math. Monthly 36(1)
> 1929, pp. 59-67.
>            E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways, Academic
> Press, NY, 2 vols.,
>            1982, see p. 114.
>            L. Carlitz, A Problem in Partitions Related to the Stirling Numbers,
> Bull. Amer. Math.
>            Soc., 70(2) pp. 275-278.
>            E. Dijkstra's fusc(n), see his Selected Writings on Computing,
> Springer, 1982, p. 232.
> Formula:   G.f.: prod_0^infty (1+x^2^n+x^2^{n+1}) [Carlitz]
> Author(s): njas
> Extension: Additional references and comments from Leonard Smiley
>            (smiley at math.uaa.alaska.edu).
>
> ----------------
>
> APH
>
> ==========================================================================
>
> From: reznick at mimas.math.uiuc.edu (Bruce Reznick)
> Newsgroups: sci.math
> Subject: Re: A remarkable sequence
> Date: 27 May 1999 17:43:59 GMT
>
>         Let me make two immodest additions to this discussion of the
> Stern sequence. In my paper "Some binary partition functions", which
> appeared in the collection "Analytic number theory" (Allerton Park,
> IL, 1989), 451--477, Progr. Math., 85, Birkh?äuser Boston, Boston, MA,
> 1990. MR 91k:11092, I discussed a variety of questions regarding the
> number of ways to write n = \sum_j a_j2^j, when a_j \in {0,1,...,d-1}.
> The Stern sequence corresponds to d = 3. An old Putnam problem amounts
> to d = 4.
>         It is easy to show that in the sequence 1 1 2 1 3 2 3 1 4 3..,
> every third element of the sequence is even. This begs the question of
> the distribution of the Stern sequence modulo m for m > 2. I've made
> some progress in this direction and gave a talk at the March 1999 AMS
> Meeting in Urbana. (See abstract 941-11-279 in a recent Abstracts of
> the AMS.) In short, consecutive pairs of the Stern sequence are as
> equidistributed mod m as they can be, given that they are
> relatively prime. One consequence is that the probability that a prime
> p divides s(n) is asymptotically 1/(p+1). I hope to finish writing
> this paper this summer, and will be happy to send a preprint to anyone
> interested.
>
> Bruce Reznick
>
> =======================================================================
>
> Antreas