In this talk, we will survey some old and new results about the
Stern sequence, a highly underappreciated mathematical object.
It is defined by the recurrence
s(0) = 0, s(1) = 1, s(2n) = s(n), s(2n+1) = s(n) + s(n+1).
It is most easily written by imagining a Pascal triangle with memory, and
starting with (1,1). The rows of the resulting "diatomic" array give s(n)
for 2^r \le n \le 2^{r+1}:
(r=0): 1 1
(r=1): 1 2 1
(r=2): 1 3 2 3 1
(r=3): 1 4 3 5 2 5 3 4 1
Stern himself proved in 1858 that every pair of relatively prime positive
integers (a,b) occurs exactly once as the pair (s(n),s(n+1)), and the
binary representation of n is encoded by the continued fraction
representation of a/b. The maximum values in the r-th row is the (r+2)-nd
Fibonacci number. The sum of the entries in the r-th row is 3^r + 1; the
sum of the cubes of the entries is 9*7^{r-1} for r > 0. The Stern sequence
also has many interesting divisibility properties: s(n) is even iff n is a
multiple of 3; the set of n for which s(n) is a multiple of 3 has a simple
recursive description. The set of n for which s(n) is a multiple of the
prime p has density 1/(p+1). Further, s(n) counts the number of binary
representations of n-1, if one allows digits from {0,1,2}. If n is odd and
m is the integer whose base 2 representation is the reversal of n's, then
s(n) = s(m) and s(n+1)s(m+1) = 1 mod (s(n)). The Stern sequence affords a
clear understanding of the alluringly-named Minkowski ?-function, which
gives a strictly increasing map from [0,1] to itself, taking the rationals
to the dyadic rationals, and the quadratic irrationals to the non-dyadic
rationals. There are few other mathematical objects which are as generous
in their grooviness; as one final example, s(729) = 64.
This talk will be rather elementary and accessible to alert undergraduates.