A remarkable sequence (FWD)

[Antreas P. Hatzipolakis]

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