\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf Regularity Properties of the Stern \\ \vskip .12in Enumeration of the Rationals } \vskip 1cm \large Bruce Reznick \\ Department of Mathematics \\ University of Illinois\\ Urbana, IL 61801 \\ USA\\ \href{mailto:reznick@math.uiuc.edu}{\tt reznick@math.uiuc.edu} \\ \end{center} \vskip .2 in \begin{abstract} The Stern sequence $s(n)$ is defined by $s(0) = 0, s(1) = 1$, $s(2n) = s(n)$, $s(2n+1) = s(n) + s(n+1)$. Stern showed in 1858 that $\gcd(s(n),s(n+1)) = 1$, and that every positive rational number $\frac ab$ occurs exactly once in the form $\frac{s(n)}{s(n+1)}$ for some $n \ge 1$. We show that in a strong sense, the average value of these fractions is $\frac 32$. We also show that for $d \ge 2$, the pair $(s(n), s(n+1))$ is uniformly distributed among all feasible pairs of congruence classes modulo $d$. More precise results are presented for $d=2$ and 3. \end{abstract} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{plain} %\newtheorem{theorem}{Theorem}[section] %\newtheorem{lemma}[theorem]{Lemma} %\newtheorem{proposition}[theorem]{Proposition} %\newtheorem{corollary}[theorem]{Corollary} %\newtheorem{conjecture}[theorem]{Conjecture} %\newtheorem*{main}{Main Theorem} \def\mod#1{{\ifmmode\text{\rm\ (mod~$#1$)} \else\discretionary{}{}{\hbox{ }}\rm(mod~$#1$)\fi}} \theoremstyle{definition} \newtheorem*{definition}{Definition} \theoremstyle{remark} \newtheorem*{example}{Example} \newtheorem*{remark}{Remark} \newtheorem*{remarks}{Remarks} \newcommand{\qq}{{\mathbb Q}} \newcommand{\rr}{{\mathbb R}} \newcommand{\nn}{{\mathbb N}} \newcommand{\zz}{{\mathbb Z}} \newcommand{\ch}{\raisebox{2pt}{$\chi$}} \newcommand{\al}{\alpha} \newcommand{\be}{\beta} \newcommand{\ga}{\gamma} \newcommand{\ep}{\epsilon} \newcommand{\la}{\lambda} \newcommand{\de}{\delta} \newcommand{\Del}{\Delta} %%% Revised version, Sept. 11, 2008 \section{Introduction and History} In 1858, M. A. Stern \cite{ste} defined the {\it diatomic array}, an unjustly neglected mathematical construction. It is a Pascal triangle with memory: each row is created by inserting the sums of pairs of consecutive elements into the previous row. \begin{equation} \begin{aligned} &a\quad b \\ &a\quad a+b\quad b \\ &a\quad 2a+b\quad a+b\quad a+2b\quad b \\ &a\quad 3a+b\quad 2a+b\quad 3a+2b\quad a+b\quad 2a+3b\quad a+2b\quad a+3b\quad b \\ &\qquad \vdots \\ \end{aligned} \end{equation} When $(a,b) = (0,1)$, it is easy to see that each row of the diatomic array repeats as the first half of the next row down. The resulting infinite {\it Stern sequence} can also be defined recursively by: \begin{equation} s(0) = 0,\ s(1) = 1,\qquad s(2n) = s(n),\ s(2n+1) = s(n) + s(n+1). \end{equation} Taking $(a,b) = (1,1)$ in (1), we obtain blocks of $(s(n))$ for $2^r \le n \le 2^{r+1}$. Although $s(2^r)=1$ is repeated at the ends, each pair $(s(n),s(n+1))$ appears below exactly once as a consecutive pair in a row: \begin{equation} \begin{aligned} & (r=0) &\qquad &1\quad 1 \\ & (r=1) &\qquad &1\quad 2\quad 1 \\ & (r=2) &\qquad &1\quad 3\quad 2\quad 3\quad 1 \\ & (r=3) &\qquad &1\quad 4\quad 3\quad 5\quad 2\quad 5\quad 3\quad 4\quad 1 \\ &\qquad \vdots \\ \end{aligned} \end{equation} Mirror symmetry (or an easy induction) implies that for $0 \le k \le 2^r$, we have \begin{equation} s(2^r + k) = s(2^{r+1} - k). \end{equation} In his original paper, Stern proved that for all $n$, \begin{equation} \gcd(s(n),s(n+1)) = 1; \end{equation} moreover, for every pair of positive relatively prime integers $(a,b)$, there is a unique $n$ so that $s(n) = a$ and $s(n+1) = b$. Stern's discovery predates Cantor's proof of the countability of $\qq$ by fifteen years. This property of the Stern sequence has been recently made explicit and discussed \cite{cw} by Calkin and Wilf. Another enumeration of the positive rationals involves the {\it Stern-Brocot array}, which also predates Cantor; see Graham, Knuth and Patashnik \cite[pp. 116--123, 305--306]{gkp}. This was used by Minkowski \cite{mink} in defining his $?$-function. The Stern sequence and Stern-Brocot array make brief appearances \cite[pp. 156,426]{dic} in Dickson's {\it History}. Apparently, de Rham \cite{dr} was the first to consider the sequence $(s(n))$ {\it per se}, attributing the term ``Stern sequence'' to Bachmann \cite[p. 143]{bach}, who had only considered the array. The Stern sequence has recently arisen as well in the discussion of 2-regular sequences by Allouche and Shallit \cite{as} and the Tower of Hanoi graph \cite{hkmpp} by Hinz, Klav\v zar, Milutinovi\'c, Parisse, and Petr. Some other Stern identities and a large bibliography relating to the Stern sequence are given \cite{urb} by Urbiha. A further discussion of the Stern sequence will be found in \cite{rez2}. Let \begin{equation} t(n) = \frac {s(n)}{s(n+1)}. \end{equation} Here are blocks of $(t(n))$, for $2^r \le n <2^{r+1}$ for small $r$: \begin{equation} \begin{aligned} & (r=0) &\qquad & \tfrac 11 \\ & (r=1) &\qquad & \tfrac 12 \quad \tfrac 21 \\ & (r=2) &\qquad & \tfrac 13 \quad \tfrac 32 \quad \tfrac 23 \quad \tfrac 31 \\ & (r=3) &\qquad & \tfrac 14 \quad \tfrac 43 \quad \tfrac 35 \quad \tfrac 52 \quad \tfrac 25 \quad \tfrac 53 \quad \tfrac 34 \quad \tfrac 41 \\ &\qquad \vdots \\ \end{aligned} \end{equation} In Section 3, we shall show that \begin{equation} \sum_{n=0}^{N-1} t(n) = \frac {3N}2 + {\mathcal O}(\log^2 N), \end{equation} so the ``average'' element in the Stern enumeration of $\mathbb Q_+$ is $\frac 32$. For a fixed integer $d \ge 2$, let \begin{equation} S_d(n) := (s(n) \text{ mod }d, s(n+1)\text{ mod } d) \end{equation} and let \begin{equation} {\mathcal S}_d = \{(i \text{ mod }d, j\text{ mod }d): \gcd(i,j,d) = 1\}. \end{equation} It follows from (5) that $S_d(n) \in {\mathcal S}_d$ for all $n$. In Section 4, we shall show that for each $d$, the sequence $(S_d(n))$ is uniformly distributed on ${\mathcal S}_d $, so the ``probability'' that $s(n) \equiv i \mod d$ can be explicitly computed. More precisely, let \begin{equation} T(N;d,i) = \left\vert\{n: 0 \le n < N\ \& \ s(n) \equiv i \text{ mod }d \}\right\vert. \end{equation} Then there exists $\tau_d < 1$ so that \begin{equation} T(N;d,i) = r_{d,i} N + {\mathcal O}(N^{\tau_d}), \end{equation} where \begin{equation} r_{d,i} = \frac 1d \cdot \prod_{p\ | i,p\ |\ d} \frac {p}{p+1} \cdot \prod_{p\ \nmid\ i , p\ |\ d} \frac {p^2}{p^2-1}. \end{equation} In particular, the probability that $s(n)$ is a multiple of $d$ is $I(d)^{-1}$, where \begin{equation} I(d) = d \prod_{p\ | \ d} \frac{p+1}p \in \mathbb N. \end{equation} In Section 5, we present more specific information for the cases $d = 2$ and 3. It is an easy induction that $s(n)$ is even if and only if $n$ is a multiple of 3, so that $\tau_2 = 0$. We show that $\tau_3 = \frac 12$ and give an explicit formula for $T(2^r;3,0)$, as well as a recursive description of those $n$ for which $3 \ | \ s(n)$. We also prove that, for all $N\ge 1$, $T(N;3,1) - T(N;3,2) \in \{0,1,2,3\}$. It will be proved in \cite{rez2} that \begin{equation} T(2^r;4,0) = T(2^r;5,0), \qquad T(2^r;6,0) = T(2^r;9,0) = T(2^r;11,0); \end{equation} we conjecture that $T(2^r;22,0) = T(2^r;27,0)$. (The latter is true for $r \le 19$.) These exhaust the possibilities for $T(2^r;N_1,0) = T(2^r;N_2,0)$ with $N_i \le 128$. Note that $I(4) = I(5) = 6$, $I(6)=I(8) =I(9) = I(11) = 12$ and $I(22)=I(27) = 36$. However, $T(2^r;8,0)\neq T(2^r;6,0)$, so there is more than just asymptotics at work. \section{Basic facts about the Stern sequence} We formalize the definition of the diatomic array. Define $Z(r,k) = Z(r,k;a,b)$ recursively for $r \ge 0$ and $0 \le k \le 2^r$ by: \begin{equation} \begin{gathered} Z(0,0) = a, \quad Z(0,1) = b; \\ Z(r+1,2k) = Z(r,k), \quad Z(r+1,2k+1) = Z(r,k) + Z(r,k+1). \end{gathered} \end{equation} The following lemma follows from (2), (16) and a simple induction. \begin{lemma} For $0 \le k \le 2^r$, we have \begin{equation} Z(r,k;0,1) = s(k). \end{equation} \end{lemma} Lemma 1 leads directly to a general formula for the diatomic array. \begin{theorem} For $0 \le k \le 2^r$, we have \begin{equation} Z(r,k;a,b) = s(2^r-k)a + s(k)b. \end{equation} \end{theorem} \begin{proof} Clearly, $Z(r,k;a,b)$ is linear in $(a,b)$ and it also satisfies a mirror symmetry \begin{equation} Z(r,k;a,b) = Z(r,2^r-k;b,a) \end{equation} for $0 \le k \le 2^r$, c.f. (4). Thus, \begin{equation} Z(r,k;a,b) = a Z(r,k;1,0) + bZ(r,k;0,1) = aZ(r,2^r-k;0,1) + bZ(r,k;0,1). \end{equation} The result then follows from Lemma 1. \end{proof} The diatomic array contains a self-similarity: any two consecutive entries in any row determine the corresponding portion of the succeeding rows. More precisely, we have a relation whose simple inductive proof is omitted, and which immediately leads to the iterated generalization of (2). \begin{lemma} If $0 \le k \le 2^r$ and $0 \le k_0 \le 2^{r_0}-1$, then \begin{equation} Z(r+r_0,2^{r}k_0 + k;a,b) = Z(r,k;Z(r_0,k_0;a,b),Z(r_0,k_0+1;a,b)). \end{equation} \end{lemma} \begin{corollary} If $n \ge 0$ and $0 \le k \le 2^r$, then \begin{equation} s(2^rn + k) = s(2^r-k)s(n) + s(k)s(n+1). \end{equation} \end{corollary} \begin{proof} Take $(a,b,k_0,r_0) = (0,1,n, \lceil \log_2 (n+1) \rceil)$ in Lemma 3, so that $k_0 < 2^{r_0}$, and then apply Theorem 2. \end{proof} We turn now to $t(n)$. Clearly, $t(2n) < 1 \le t(2n+1)$ for all $n$; after a little algebra, (2) implies \begin{equation} t(2n) = \cfrac 1{1 + \cfrac 1{t(n)}}\ , \qquad t(2n+1) = 1 + t(n). \end{equation} The mirror symmetry (4) yields two other formulas which are evident in (7): \begin{equation} t(2^r + k)t(2^{r+1}-k-1) = 1, \end{equation} for $0 \le k \le 2^r-1$, which follows from \begin{equation} t(2^{r+1}-k-1) = \frac {s(2^{r+1}-k-1)}{s(2^{r+1}-k)} = \frac {s(2^r + k+1)}{s(2^r+k)} = \frac 1{t(2^r+k)}; \end{equation} and \begin{equation} t(2^r + 2\ell)+ t(2^{r+1}-2\ell-2) = 1, \end{equation} for $r \ge 1$ and $0 \le 2\ell \le 2^r-2$, which follows from \begin{equation} \frac{s(2^r+2\ell)}{s(2^r+2\ell+1)} + \frac{s(2^{r+1}-2\ell-2)}{s(2^{r+1}-2\ell-1)} = \frac{s(2^r+2\ell)}{s(2^r+2\ell+1)} + \frac{s(2^r+2\ell+2)}{s(2^r+2\ell+1)}, \end{equation} since $s(2m) + s(2m+2) = s(2m+1)$. Although we will not use it directly here, we mention a simple closed formula for $t(n)$, and hence for $s(n)$. Stern had already proved that if $2^r \le n < 2^{r+1}$, then the sum of the denominators in the continued fraction representation of $t(n)$ is $r+1$; this is clear from (23). Lehmer \cite{leh} gave an exact formulation, of which the following is a variation. Suppose $n$ is odd and $[n]_2$, the binary representation of $n$, consists of a block of $a_1$ 1's, followed by $a_2$ 0's, $a_3$ 1's, etc, ending with $a_{2v}$ 0's and $a_{2v+1}$ 1's, with $a_j \ge 1$. (That is, $n = 2^{a_1 + \cdots + a_{2v+1}} - 2^{a_2 + \cdots + a_{2v+1}} \pm \cdots \pm 2^{a_{2v+1}} - 1$.) Then \begin{equation} t(n) = \frac{s(n)}{s(n+1)} = \frac pq = a_{2v+1} + \cfrac 1{a_{2v} + \cfrac 1{\dots + \cfrac 1{a_1}}}\ . \end{equation} Conversely, if $\frac pq > 1$ and (28) gives its presentation as a simple continued fraction with an odd number of denominators, then the unique $n$ with $t(n) = \frac pq$ has the binary representation described above. (If $n$ is even or $\frac pq < 1$, apply (24) first.) The {\it Stern-Brocot array} is named after the clockmaker Achille Brocot, who used it \cite{broc} in 1861 as the basis of a gear table; see also Hayes \cite{hayes}. This array caught the attention of several French number theorists, and is discussed \cite{luc} by Lucas. It is formed by applying the diatomic rule to numerators and denominators simultaneously: \begin{equation} \begin{aligned} & (r=0) &\qquad & \tfrac 01 \quad \tfrac 10\\ & (r=1) &\qquad & \tfrac 01 \quad \tfrac 11 \quad \tfrac 10 \\ & (r=2) &\qquad & \tfrac 01 \quad \tfrac 12 \quad \tfrac 11 \quad \tfrac 21\quad \tfrac 10 \\ & (r=3) &\qquad & \tfrac 01 \quad \tfrac 13 \quad \tfrac 12 \quad \tfrac 23 \quad \tfrac 11 \quad \tfrac 32 \quad \tfrac 21 \quad \tfrac 31\quad \tfrac 10\\ &\qquad \vdots \\ \end{aligned} \end{equation} This array is not quite the same as (7). If $\frac ab$ and $\frac cd$ are consecutive in the $r$-th row, then they repeat in the $(r+1)$-st row, separated by $\frac {a+c}{b+d}$. It is easy to see that the elements of the $r$-th row are $\frac{s(k)}{s(2^r-k)}$, $0 \le k \le 2^r$. It is also easy to show that the elements of each row are increasing, and moreover, that they share a property with the Farey sequence. \begin{lemma} For $0 \le k \le 2^r - 2$, \begin{equation} \frac{s(k+1)}{s(2^r-k-1)} - \frac{s(k)}{s(2^r-k)} =\frac 1{s(2^r-k)s(2^r-k-1)}. \end{equation} That is, \begin{equation} s(k+1)s(2^r-k)-s(k)s(2^r - k-1) = 1. \end{equation} \end{lemma} This lemma has a simple proof by induction, which can be found in Lucas \cite[p.467]{luc}, and Graham, Knuth and Patashnik \cite[p.117]{gkp}. The ``new'' entries in the $(r+1)$-st row of (29) are a permutation of the $r$-th row of (7). The easiest way to express the connection (see \cite{rez2}) for rationals $\frac pq > 1$ is that if $0 < k < 2^r$ is odd, then \begin{equation} \frac pq = \frac{s(2^r+k)}{s(2^r-k)} = \frac {s(\overleftarrow{2^r+k})} {s(\overleftarrow{2^r+k}+1)}, \end{equation} where $\overleftarrow n$ denotes the integer so that $[n]_2$ and $[\overleftarrow n]_2$ are the reverse of each other. If $\frac pq < 1$, then apply mirror symmetry to the instance of (32) which holds for $\frac qp$. The Minkowski $?$-function can be defined using the first half of the rows of (29). For odd $\ell$, $0 \le \ell \le 2^r$, \begin{equation} ?\left( \frac{s(\ell)}{s(2^{r+1}-\ell)} \right) = \frac \ell{2^r}. \end{equation} This gives a strictly increasing map from $\mathbb Q \cap [0,1]$ to the dyadic rationals in $[0,1]$, which extends to a continuous strictly increasing map from $[0,1]$ to itself, taking quadratic irrationals to non-dyadic rationals. Finally, suppose $N$ is a positive integer, written as \begin{equation} N = 2^{r_1} + 2^{r_2} + \cdots + 2^{r_v}, \qquad r_1 > r_2 > \dots > r_v. \end{equation} We shall define \begin{equation} N_0 = 0;\quad N_j = 2^{r_1} +\cdots + 2^{r_j}\text{ for } j = 1, \dots, v. \end{equation} Further, for $1 \le j \le v$, let $M_j = 2^{-r_j}N_{j+1}$, so that \begin{equation} N_j = N_{j-1} + 2^{r_j} = 2^{r_j}(M_j+1) = 2^{r_{j-1}}M_{j-1}. \end{equation} and, for $a < b \in \mathbb Z$, let \begin{equation} [a,b):= \{k \in \mathbb Z : a \le k < b \}. \end{equation} Our proofs will rely on the observation that \begin{equation} [0,N) = \bigcup_{j=0}^{v-1} [N_j,N_{j+1}) = \bigcup_{j=1}^{v} [2^{r_j}M_j,2^{r_j}(M_j+1)), \end{equation} where the above unions are disjoint, so that, formally, \begin{equation} \sum_{n=0}^{N-1} = \sum_{j=0}^{v-1} \sum_{n=N_j}^{N_{j+1}-1} = \sum_{j=1}^{v} \sum_{n=2^{r_j}M_j}^{2^{r_j}(M_j+1)-1}. \end{equation} \section{The Stern-Average Rational} We begin by looking at the sum of $t(n)$ along the rows of (7). Let \begin{equation} A(r) = \sum_{n=2^r}^{2^{r+1}-1} t(n)\qquad{\text{and}}\qquad \tilde A(r) = \sum_{n=0}^{2^{r}-1} t(n) = \sum_{i=0}^{r-1} A(i). \end{equation} \begin{lemma} For $r \ge 0$, \begin{equation} A(r) = \frac 32 \cdot 2^r - \frac 12\qquad{\text{and}}\qquad \tilde A(r) = \frac 32 \cdot 2^r -\frac {r+3}2. \end{equation} \end{lemma} \begin{proof} First note that $A(0) = t(1) = \frac 11 = \frac 32 - \frac 12$. Now observe that for $r \ge 0$, \begin{equation} \begin{gathered} A(r+1) = \sum_{j=0}^{2^{r+1}-1} t(2^{r+1} + j) = \sum_{k=0}^{2^r-1} t(2^{r+1} + 2k) + \sum_{k=0}^{2^r-1} t(2^{r+1} + 2k+1). \end{gathered} \end{equation} Using (26) and (23), we can simplify this summation: \begin{equation} \sum_{k=0}^{2^r-1} t(2^{r+1} + 2k) = \frac 12 \left( \sum_{k=0}^{2^r-1} t(2^{r+1} + 2k) + t(2^{r+2}-2k-2) \right) = 2^{r-1}, \end{equation} and \begin{equation} \sum_{k=0}^{2^r-1} t(2^{r+1} + 2k+1) = \sum_{k=0}^{2^r-1}\bigl(1 + t(2^r+k)\bigr) = 2^r + A(r). \end{equation} Thus, $A(r+1) = 2^{r-1}+2^r+A(r)$, and the formula for $A(r)$ is established by induction. This also immediately implies the formula for $\tilde A(r)$. \end{proof} \begin{lemma} If $m$ is even, then \begin{equation} \tilde A(r) \le \sum_{k=0}^{2^r-1} t(2^rm + k) < A(r). \end{equation} \end{lemma} \begin{proof} For fixed $(k,r)$, let \begin{equation} \Phi_{k,r}(x) = \frac {s(2^r-k) x + s(k)}{s(2^r-(k+1))x + s(k+1)}. \end{equation} Then it follows from (31) that \begin{equation} \Phi_{k,r}'(x) = \frac {s(k+1)s(2^r-k)-s(k)s(2^r - k-1)}{(s(2^r-(k+1))x + s(k+1))^2} > 0. \end{equation} Using (22), we see that \begin{equation} \begin{gathered} t(2^rm + k) = \frac{s(2^rm + k)}{s(2^rm + k+1)} = \frac{s(2^r-k)s(m) + s(k)s(m+1)}{s(2^r-k-1)s(m) + s(k+1)s(m+1)} \\=\Phi_{k,r}\left(\frac {s(m)}{s(m+1)} \right) = \Phi_{k,r}(t(m)). \end{gathered} \end{equation} Since $m$ is even, $0 \le t(m) < 1$; monotonicity then implies that \begin{equation} t(k) = \Phi_{k,r}(0) \le t(2^rm + k) < \Phi_{r,k}(1) = t(2^r+k). \end{equation} Summing (49) on $k$ from 0 to $2^r-1$ gives (45). \end{proof} We use these estimates to establish (8). \begin{theorem} If $2^r \le N < 2^{r+1}$, then \begin{equation} \frac{3N}2 - \frac{r^2+7r+6}4 \le \sum_{n=0}^{N-1} t(n) < \frac{3N}2 - \frac 12. \end{equation} \end{theorem} \begin{proof} Recalling (39), we apply Lemma 7 for each $j$, with $r = r_j$ and $m = M_j$, so that \begin{equation} \frac 32 \cdot 2^{r_j} - \frac {r_j+3}2 \le \sum_{n=N_{j-1}}^{N_j-1} t(n) < \frac 32\cdot 2^{r_j} - \frac 12. \end{equation} After summing on $j$, we find that \begin{equation} \frac {3N}2 - \frac {r_1 + \dots + r_v + 3v}2 \le \sum_{n=0}^{N-1} t(n) < \frac {3N}2 - \frac {v}2. \end{equation} To obtain (50), note that $\sum r_j + 3v \le \frac{r(r+1)}2 + 3r+3 = \frac {r^2+7r+6}2$. \end{proof} \begin{corollary} \begin{equation} \sum_{n=0}^{N-1} t(n) = \frac {3N}2 + \mathcal O\left( \log^2N \right). \end{equation} \end{corollary} Since $t(2^r-1) = \frac r1$, the true error term is at least $\mathcal O(\log N)$. Numerical computations using Mathematica suggest that $\log^2N$ can be replaced by $\log N \log\log N$. It also seems that, at least for small fixed positive integers $t$, \begin{equation} \al_t:= \lim_{N \to \infty} \frac 1N \sum_{n=0}^{N-1} \frac {s(n)}{s(n+t)} \end{equation} exists. We have seen that $\al_1 = \frac 32$, and if they exist, the evidence suggests that $\al_2\approx 1.262$, $\al_3 \approx 1.643$ and $\al_4 \approx 1.161$. We are unable to present an explanation for these specific numerical values. \section{Stern Pairs, mod $d$} We fix $d \ge 2$ with prime factorization $d = \prod p_\ell^{e_\ell}$, $e_\ell \ge 1$, and recall the definitions of $\mathcal S_d$ and $S_d(n)$ from (9) and (10). Let \begin{equation} N_d = \left\vert \mathcal S_d \right\vert, \end{equation} and for $0 \le i < d$, let \begin{equation} N_d(i)= \left\vert \{j\text{ mod } d: (i \text{ mod } d, j \text{ mod } d) \in \mathcal S_d\} \right\vert. \end{equation} We now give two lemmas whose proofs rely on the Chinese Remainder Theorem. \begin{lemma} The map $S_d: \nn \to \mathcal S_d$ is surjective. \end{lemma} \begin{proof} Suppose $\al =(i,j) \in \mathcal S_d$ with $0 \le i, j \le d-1$. We shall show that there exists $w \in \mathbb N$ so that $\gcd(i, j+wd) = 1$. Consequently, there exists $n$ with $s(n) = i$ and $s(n+1) = j + wd$, so that $S_d(n) = \al$. Write $i= \prod_\ell {q_\ell^{f_\ell}}$, $f_\ell \ge 1$, with $q_\ell$ prime. If $q_\ell\ |\ j$, then $q_\ell\ \nmid \ d$. There exists $w\ge 0$ so that $w \equiv d^{-1} \mod {q_\ell^{f_\ell}}$ if $q_\ell\ |\ j$ and $w \equiv 0 \mod {q_\ell^{f_\ell}}$ if $q_\ell\ \nmid\ j$. Then $j + wd \not\equiv 0 \mod {q_\ell^{f_\ell}}$ for all $\ell$, so no prime dividing $i$ divides $j + wd$, as desired. \end{proof} \begin{lemma} For $0 \le i \le d-1$, \begin{equation} N_d = d^2 \prod_{\ell} \frac {p_\ell^2-1}{p_\ell^2} \qquad \text{and} \qquad N_d(i) = d \prod_{p_\ell\ |\ i} \frac {p_\ell-1}{p_\ell}. \end{equation} \end{lemma} \begin{proof} To compute $N_d$, we use the Chinese Remainder Theorem by counting the choices for $(i \text{ mod } p_\ell^{e_\ell}, j \text{ mod } p_\ell^{e_\ell})$ for each $\ell$. Missing are those $(i,j)$ in which $p_\ell$ divides both $i$ and $j$, and so the total number of classes is $(p_\ell^{e_\ell} - p_\ell^{e_\ell-1})^2$ for each $\ell$. Now fix $i$. If $p_\ell \ |\ i$, then $(i,j) \in \mathcal S_d$ if and only if $p_\ell \nmid j$; if $p_\ell \nmid i$, then there is no restriction on $j$. Thus, there are either $p_\ell^{e_\ell} - p_\ell^{e_\ell-1}$ or $p_\ell^{e_\ell}$ choices for $j$, respectively. \end{proof} Suppose $\al = (i,j) \in \mathcal S_d$; let $L(\al):= (i, i+j)$ and $R(\al) = (i+j,j)$, where $i+j$ is reduced mod $d$ if necessary. Then $L(\al), R(\al) \in \mathcal S_d$ and the following lemma is immediate. \begin{lemma} For all $n$, we have $S_d(2n) = L(S_d(n))$ and $S_d(2n+1) = R(S_d(n))$. \end{lemma} We now define the directed graph $\mathcal G_d$ as follows. The vertices of $\mathcal G_d$ are the elements of $\mathcal S_d$. The edges of $\mathcal G_d$ consist of $(\al, L(\al))$ and $(\al, R(\al))$ where $\al \in \mathcal S_d$. Iterating, we see that $L^k(\al) = (i, i+kj)$ and $R^k(\al) = (i + kj, j)$, so that $L^d = R^d = id$, and $L^{-1} = L^{d-1}$ and $R^{-1} = R^{d-1}$. Thus, if $(\al, \be)$ is an edge of $\mathcal G_d$, then there is a walk of length $d-1$ from $\be$ to $\al$. Each vertex of $\mathcal G_d$ has out-degree two; since $(L^{-1}(\al), \al)$ and $(R^{-1}(\al), \al)$ are edges, each vertex has in-degree two as well. Let $M_d = [m_{\al(d)\be(d)}] = [m_{\al\be}]$ denote the adjacency matrix for $\mathcal G_d$: $M_d$ is the $N_d \times N_d$ 0-1 matrix so that $m_{\al L(\al)} = m_{\al R(\al)} = 1$, with other entries equal to 0. For a positive integer $r$, write \begin{equation} M_d^r = [m_{\al\be}^{(r)}]; \end{equation} then $m_{\al\be}^{(r)}$ is the number of walks of length $r$ from $\al$ to $\be$. Finally, for $\ga \in \mathcal S_d$, and integers $U_1 < U_2$, let \begin{equation} B(\ga;U_1,U_2) = \left\vert \{m: U_1 \le m < U_2\ \&\ S_d(m) = \ga \} \right\vert \end{equation} The following is essentially equivalent to Lemma 3. \begin{lemma} Suppose $\al = S_d(m)$, $\be \in \mathcal S_d$ and $r \ge 1$. Then $B(\be;2^rm,2^r(m+1)) =m_{\al\be}^{(r)} $ is equal to the number of walks of length $r$ in $\mathcal G_d$ from $\al$ to $\be$. \end{lemma} \begin{proof} The walks of length 1 starting from $\al$ are $(\al, L(\al))$ and $(\al, R(\al))$; these may be interpreted as $(S_d(n),S_d(2n))$ and $(S_d(n),S_d(2n+1))$. The rest is an easy induction. \end{proof} \begin{lemma} For sufficiently large $N$, $m_{\al\be}^{(N)} > 0$ for all $\al, \be$. \end{lemma} \begin{proof} Let $\al_0 = (0,1) = S_d(0)$. Note that $L(\al_0) = \al_0$, hence if there is a walk of length $w$ from $\al_0$ to $\ga$, then there are such walks of every length $\ge w$. By Lemma 10, for each $\al \in \mathcal S_d$, there exists $n_\al$ so that $S_d(n_\al) = \al$. Choose $r$ sufficiently large that $n_\al < 2^r$ for all $\al$. Then by Lemma 13, for every $\ga$, there is a walk of length $r$ from $\al_0$ to $\ga$, and so there is a walk of length $(d-1)r$ from $\ga$ to $\al_0$. Thus, for any $\al, \be \in \mathcal S_d$, there is at least one walk of length $dr$ from $\al$ to $\be$ via $\al_0$. \end{proof} We need a version of Perron-Frobenius. Observe that $A_d = \frac 12 M_d$ is doubly stochastic and the entries of $A_d^N = 2^{-N}M_d^N$ are positive for sufficiently large $N$. Thus $A_d$ is {\it irreducible} (see Minc \cite[Ch. 1]{minc}), so it has a simple eigenvalue of 1, and all its other eigenvalues are inside the unit disk. It follows that $M_d$ has a simple eigenvalue of 2. Let \begin{equation} f_d(T) = T^k + c_{k-1}T^{k-1} + \cdots + c_0 \end{equation} be the minimal polynomial of $M_d$. Let $\rho_d < 2$ be the maximum modulus of any non-2 root of $f_d$, and let $1+\sigma_d$ be the maximum multiplicity of any such maximal root. Then for $r \ge 0$ and all $(\al,\be)$, \begin{equation} m_{\al\be}^{r+k} + c_{k-1}m_{\al\be}^{r+k-1} + \cdots + c_0m_{\al\be}^{r} = 0. \end{equation} It follows from the standard theory of linear recurrences that for some constants $c_{\al\be}$, \begin{equation} m_{\al\be}^{r} = c_{\al\be} 2^r + \mathcal(r^{\sigma_d}\rho_d^r)\qquad \text{as } r\to \infty. \end{equation} In particular, $\lim_{r\to\infty} A_d^r = A_{d0}:= [c_{\al\be}]$, and since $A_d^{r+1} = A_d A_d^r$, it follows that each column of $A_{d0}$ is an eigenvector of $A_d$, corresponding to $\la = 1$. Such eigenvectors are constant vectors and since $A_{d0}$ is doubly stochastic, we may conclude that for all $(\al,\be)$, $c_{\al\be} = \frac 1{N_d}$. Then there exists $c_d > 0$ so that for $r \ge 0$ and all $(\al,\be)$, \begin{equation} \left\vert m_{\al\be}^{r} - \frac{2^r}{N_d}\right\vert < c_dr_d^{\sigma_d}\rho_d^r. \end{equation} Computations show that for for small values of $d$ at least, $\rho_d = \frac 12$ and $\sigma_d = 0$. In any event, by choosing $2> \bar\rho_d > \rho_d$ if $\sigma_d > 0$, we can replace $r_d^{\sigma_d}\rho_d^r$ by $\bar\rho_d^r$ in the upper bound. Putting this together, we have proved the following theorem. \begin{theorem} There exist constants $c_d$ and $\bar\rho_d < 2$ so that if $m \in \mathbb N$ and $\al \in \mathcal S_d$, then for all $r \ge 0$, \begin{equation} \left\vert B(\al;2^rm,2^r(m+1)) - \frac {2^r}{N_d} \right\vert < c_d \bar\rho_d^r. \end{equation} \end{theorem} We now use this result on blocks of length $2^r$ to get our main theorem. \begin{theorem} For fixed $d \ge 2$, there exists $\tau_d< 1$ so that, for all $\al \in \mathcal S_d$, \begin{equation} B(\al;0,N) = \frac N {N_d} + \mathcal O(N^{\tau_d}). \end{equation} \end{theorem} \begin{proof} By (39), we have \begin{equation} B(\al;0,N) = \sum_{j=0}^{v-1} B(\al;N_j,N_{j+1}) = \sum_{j=1}^{v} B(\al;2^{r_j}M_j,2^{r_j}(M_j+1)). \end{equation} It follows that \begin{equation} \left\vert B(\al;0,N) - \frac N {N_d} \right \vert \le c_d(\bar\rho_d^{r_1} + \cdots + \bar\rho_d^{r_v}). \end{equation} If $\bar\rho_d \le 1$, the upper bound is $\mathcal O(r_1) = \mathcal O(\log N) = \mathcal O(N^{\epsilon})$ for any $\ep > 0$. If $1 \le \bar\rho_d < 2$, the upper bound is $\mathcal O(\bar\rho_d^{r_1}) = \mathcal O(N^{\tau_d})$ for $\tau_d = \frac{\log \bar\rho_d}{\log 2}$, since $N \le 2^{r_1+1}$. \end{proof} Using the notation (11), we have \begin{equation} T(N;d,i) = \sum_{\al = (i,j) \in \mathcal S_d} B(\al;0,N), \end{equation} and the following is an immediate consequence of Lemma 11 and Theorem 16. \begin{corollary} Suppose $d \ge 2$. Then \begin{equation} T(N;d,i) = r_{d,i}N + \mathcal O(N^{\tau_d}), \end{equation} where, recalling that $d = \prod p_\ell^{e_\ell}$, \begin{equation} r_{d,i} = \frac 1d \cdot \prod_{p_\ell | i} \frac {p_\ell}{p_\ell+1} \cdot \prod_{p_\ell \nmid i} \frac {p_\ell^2}{p_\ell^2-1}. \end{equation} \end{corollary} For example, if $p$ is prime, then $f(p,0) = \frac 1{p+1}$ and $f(p,i) = \frac p{p^2-1}$ when $p \nmid i$. In some sense, the model here is a Markov Chain, if we imagine going from $m$ to $2m$ or $2m+1$ with equal probability, so that the $B(\be;2^rm,2^r(m+1))$'s represent the distribution of destinations after $r$ steps. Ken Stolarsky has pointed out that Schmidt \cite{sch} provides a somewhat different application of the limiting theory of Markov Chains in a number theoretic setting. \section{Small values of $d$} It is immediate to see (and to prove) that $2 \ | \ s(n)$ if and only if $3 \ | \ n$, thus $S_2(n)$ cycles among $\{(0,1), (1,1), (1,0)\}$ and $\tau_2 = 0$. This generalizes to a family of partition sequences. Suppose $d \ge 2$ is fixed, and let $b(d;n)$ denote the number of ways that $n$ can be written in the form \begin{equation} n = \sum_{i\ge 0} \epsilon_i 2^i,\qquad \epsilon_i \in \{0,\dots,d-1\}, \end{equation} so that $b(2;n) = 1$. It is shown in \cite{rez1} that \begin{equation} \sum_{n=0}^\infty s(n)X^n = X\prod_{j=0}^\infty\left(1 + X^{2^j} + X^{2^{j+1}}\right). \end{equation} A standard partition argument shows that \begin{equation} \sum_{n=0}^\infty b(d;n)X^n = \prod_{j=0}^\infty \frac {1 - X^{d\cdot 2^j}}{1 - X^{2^j}}. \end{equation} Thus, $s(n) = b(3;n-1)$. An examination of the product in (73) modulo 2 shows that $b(d;n)$ is odd if and only if $n \equiv 0,1 \text{ mod } d$ (see \cite{rez1}, Theorems 5.2 and 2.14.) Suppose now that $d=3$. Write the 8 elements of $\mathcal S_3$ in lexicographic order: \begin{equation} (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2). \end{equation} Then in the notation of the last section, \begin{equation} M_3 = \begin{pmatrix} 1&0&0&1&0&0&0&0 \\ 0&1&0&0&0&0&0&1 \\0&0&1&1&0&0&0&0 \\ 0&0&0&0&1&0&1&0 \\ 0&1&1&0&0&0&0&0 \\ 0&0&0&0&0&1&0&1 \\ 1&0&0&0&0&1&0&0 \\ 0&0&0&0&1&0&1&0 \end{pmatrix}\ . \end{equation} The minimal polynomial of $M_3$ is \begin{equation} f_3(T) =T^5 -2T^4+T^3-4T^2+4T = T(T-1)(T-2)(T - \mu)(T- \bar\mu), \end{equation} where \begin{equation} \mu = \frac {-1 + \sqrt 7 i}2, \qquad \bar \mu = \frac {-1 -\sqrt 7 i}2. \end{equation} Since the roots of $f_3$ are distinct, we see that for each $(\al,\be) \in \mathcal S_3$, for $r \ge 1$, there exist constants $v_{\al\be i}$ so that \begin{equation} m_{\al\be}^{(r)} = v_{\al\be 1} + v_{\al\be 2}\mu^r + v_{\al\be 3}\bar\mu^r + \frac 18\cdot 2^r = \frac 18\cdot 2^r + \mathcal O(2^{r/2}). \end{equation} (As it happens, there are only eight distinct sequences $m_{\al\be}^{(r)}$.) Corollary 17 then implies that \begin{equation} \begin{gathered} T(N;3,0) = \frac N4 + \mathcal O(\sqrt N), \\ T(N;3,1) = \frac {3N}8 + \mathcal O(\sqrt N), \ T(N;3,2) = \frac {3N}8 + \mathcal O(\sqrt N). \end{gathered} \end{equation} Since $T(N;3,0) + T(N;3,1) + T(N;3,2) = N$, we gain complete information from studying $T(N;3,0)$ and \begin{equation} \Delta(N) = \Delta_3(N) := T(N;3,1) - T(N;3,2). \end{equation} (That is, $\Delta_3(N+1) - \Delta_3(N)$ equals $0, 1, -1$ when $s(N) \equiv 0, 1, 2$ mod 3, respectively.) To study $T(N;3,0)$, we first define the set $A_3 \subset \mathbb N$ recursively by: \begin{equation} 0,5,7 \in A_3, \qquad 0 < n \in A_3 \implies 2n, 8n\pm 5, 8n \pm 7 \in A_3. \end{equation} Thus, \begin{equation} A_3 = \{ 0, 5, 7, 10, 14, 20, 28, 33, 35, 40, 45, 47, 49, 51, 56, 61, 63,\dots \}. \end{equation} \begin{theorem} If $n \ge 0$, then $3 \ |\ s(n)$ if and only if $n \in A_3$. \end{theorem} \begin{proof} It follows recursively from (2) or directly from (22) that \begin{equation} s(2n) = s(n),\quad s(8n\pm 5) = 2s(n) + 3s(n\pm 1), \qquad s(8n\pm 7) = s(n) + 3s(n\pm 1). \end{equation} Thus, 3 divides $s(n)$ if and only if 3 divides $s(2n), s(8n\pm 5)$ or $ s(8n\pm 7)$. Since every $n > 1$ can be written uniquely as $2n', 8n'\pm 5$ or $8n'\pm 7$ with $0 \le n' < n$, the description of $A_3$ is complete. \end{proof} In the late 1970's, E. W. Dijkstra \cite[pp. 215--6, 230--232]{dijk} studied the Stern sequence under the name ``fusc'', and gave a different description of $A_3$ (p. 232): \smallskip \begin{quote} Inspired by a recent exercise of Don Knuth I tried to characterize the arguments $n$ such that $3\ | \ \it{fusc}(n)$. With braces used to denote zero or more instances of the enclosed, the vertical bar as the BNF `or', and the question mark `?' to denote either a 0 or a 1, the syntactical representation for such an argument (in binary) is \{0\}1\{?0\{1\}0$\vert$?1\{0\}1\}?1\{0\}. I derived this by considering -- as a direct derivation of my program -- the finite state automaton that computes \it{fusc} $(N)$ mod 3. \end{quote} \smallskip Let \begin{equation} a_r = | \{ n \in A_3: 2^r \le n < 2^{r+1} \} | = T(2^{r+1};3,0) - T(2^r;3,0). \end{equation} It follows from (82) that \begin{equation} a_0 = a_1=0, \quad a_2=a_3=a_4 = 2, \quad a_5 = 10. \end{equation} \begin{lemma} For $r \ge 3$, $(a_r)$ satisfies the recurrence \begin{equation} a_r = a_{r-1} + 4a_{r-3}. \end{equation} \end{lemma} \begin{proof} This is evidently true for $r = 3, 4,5$. If $2^r \le n < 2^{r+1}$ and $n=2n'$, then $2^{r-1} \le n' < 2^r$, so the even elements of $A_3$ counted in $a_r$ come from elements of $A_3$ counted in $a_{r-1}$. If $2^r \le n < 2^{r+1}$ and $n=8n'\pm5$ or $n=8n'\pm7$, then $2^{r-3} < n' < 2^{r-2}$ and $n' \in A_3$. Thus the odd elements of $A_3$ counted in $a_r$ come (in fours) from elements of $A_3$ counted in $a_{r-3}$. \end{proof} The characteristic polynomial of the recurrence (86) is $T^3-T^2-4$ (necessarily a factor of $f_3(T)$), and has roots $T=2,\ \mu$ and $\bar\mu$. The details of the following routine computation are omitted. \begin{theorem} For $r \ge 0$, we have the exact formula \begin{equation} a_r = \frac 14 \cdot 2^r + \left(\frac{-7+5\sqrt 7 i}{56}\right)\mu^r + \left(\frac{-7-5\sqrt 7 i}{56}\right)\bar\mu^r . \end{equation} \end{theorem} Keeping in mind that $s(0) = 0$ is not counted in any $a_r$, we find after a further computation that the error estimate $\mathcal O(\sqrt N)$ is best possible for $T(N;3,0)$: \begin{corollary} \begin{equation} T(2^r;3,0) = \frac 14 \cdot 2^r + \left(\frac{7-\sqrt 7 i}{56}\right)\mu^r + \left(\frac{7+\sqrt 7 i}{56}\right)\bar\mu^r + \frac 12\ . \end{equation} \end{corollary} To study $\Delta(N)$, we first need a somewhat surprising lemma. \begin{lemma} For all $N$, $\Delta(2N)= \Delta(4N)$. \end{lemma} \begin{proof} The simplest proof is by induction, and the assertion is trivial for $N=0$. There are eight possible ``short'' diatomic arrays modulo 3: \begin{equation} \begin{gathered} \begin{matrix} {s(N)}&&&&{s(N+1)} \\ s(2N)&&s(2N+1)&&s(2N+2) \\ s(4N)&s(4N+1)&s(4N+2)&s(4N+3)&s(4N+4) \end{matrix} = \\ \begin{matrix} 0&&&&1\\0&&1&&1\\0&1&1&2&1 \end{matrix}\quad\Bigg\vert\Bigg\vert\quad \begin{matrix} 0&&&&2\\0&&2&&2\\0&2&2&1&2 \end{matrix}\quad \Bigg\vert\Bigg\vert\quad \begin{matrix} 1&&&&0\\1&&1&&0\\1&2&1&1&0 \end{matrix}\quad\Bigg\vert\Bigg\vert\quad \begin{matrix} 1&&&&1\\1&&2&&1\\1&0&2&0&1 \end{matrix} \\ \begin{matrix} 1&&&&2\\1&&0&&2\\1&1&0&2&2 \end{matrix} \quad\Bigg\vert\Bigg\vert\quad \begin{matrix} 2&&&&0\\2&&2&&0\\2&1&2&2&0 \end{matrix} \quad\Bigg\vert\Bigg\vert\quad \begin{matrix} 2&&&&1\\2&&0&&1\\2&2&0&1&1 \end{matrix} \quad\Bigg\vert\Bigg\vert\quad \begin{matrix} 2&&&&2\\2&&1&&2\\2&0&1&0&2 \end{matrix} \end{gathered} \end{equation} By counting the elements in the rows mod 3 in each case, we see that $\Delta(2N+2) - \Delta(2N) = \Delta(4N+4) - \Delta(4N)$ is equal to: $1, -1, 2, 0, 1, -2, -1, 0$, respectively. \end{proof} \begin{theorem} For all $n$, $\Delta(n) \in \{0,1,2,3\}$. More specifically, \begin{equation} \begin{gathered} S_3(m) = (0,1) \implies \Delta(2m) = 0,\ \Delta(2m+1) =0; \\ S_3(m) = (0,2) \implies \Delta(2m) = 3,\ \Delta(2m+1) =3; \\ S_3(m) = (1,*) \implies \Delta(2m) = 1,\ \Delta(2m+1) =2; \\ S_3(m) = (2,*) \implies \Delta(2m) = 2,\ \Delta(2m+1) =1. \end{gathered} \end{equation} \end{theorem} \begin{proof} To prove the theorem, we first observe that it is correct for $m \le 4$. We now assume it is true for $m \le 2^r$ and prove it for $2^r \le m < 2^{r+1}$. There are sixteen cases: $m$ can be even or odd and there are 8 choices for $S_3(m)$. As a representative example, suppose $S_3(m) = (2,1)$. We shall consider the cases $m=2t$ and $m=2t+1$ separately. The proofs for the other seven choices of $S_3(m)$ are very similar and are omitted. Suppose first that $m=2t < 2^{r+1}$. Then $S_3(m) = S_3(2t) = (2,1)$, hence $S_3(t) = (2,2)$. We have $\Delta(2m) = 2$ by hypothesis, and hence $\Delta(4m) = 2$ by Lemma 22. The eighth array in (89) shows that $s(4t) \equiv 2$ mod 3, so that $\Delta(4m+1) = \Delta(4m) - 1 = 1$, as asserted in (90). If, on the other hand, $m=2t+1 < 2^{r+1}$ and $S_3(m) = S_3(2t+1) = (2,1)$, then $S_3(t) = (1,1)$. We now have $\Delta(2t) = 1$ and $\Delta(2t+1) =2$ by hypothesis and $\Delta(4t) = 1$ by Lemma 22. The fourth array in (89) shows that $(s(4t),s(4t+1),s(4t+2)) \equiv (1,0,2)\text{ mod }3$. Thus, it follows that $\Delta(2m) = \Delta(4t+2) = \Delta(4t) + 1 + 0 =2$ and $\Delta(2m+1) = \Delta(4t+3) = \Delta(4t+2)-1 = 1$, again as desired. \end{proof} Since $S_3(m)$ is uniformly distributed on $\mathcal S_3$, (90) shows that $\Delta(n)$ takes the values $(0,1,2,3)$ with limiting probability $(\frac 18, \frac 38, \frac 38, \frac 18)$. We conclude with a few words about the results announced at the end of the first section, but not proved here. For each $(d,i)$, $T(2^r;d,i)$ will satisfy a recurrence whose characteristic equation is a factor of the minimal polynomial of $\mathcal S_d$. It happens that $T(2^r;4,0) = T(2^r;5,0)$ for small values of $r$ and both satisfy the recurrence with characteristic polynomial $T^4-2T^3+T^2-4$ (roots: $2,-1,-\tau, -\bar\tau$) so that equality holds for all $r$. The same applies to $T(2^r;6,0) = T(2^r;9,0) = T(2^r;11,0)$, with a more complicated recurrence. Results similar to Lemma 22 and Theorem 23 hold for $d=4$, with a similar proof; Antonios Hondroulis has shown that this is also true for $d=6$. No result has been found yet for $d=5$, although a Mathematica check for $N \le 2^{19}$ shows that $-5 \le T(N;5,1) - T(N;5,4) \le 11$. These topics will be discussed in greater detail in \cite{rez2}. \bibliographystyle{amsalpha} \begin{thebibliography}{99} \bibitem{as} J.-P. Allouche, J. Shallit, The ring of $k$-regular sequences, {\it Theoret. Comput. Sci.} {\bf 98} (1992), 163--197, MR1166363 (94c:11021). \bibitem{bach} P. Bachmann, {\it Niedere Zahlentheorie, v. 1}, Leipzig 1902, Reprinted by Chelsea, New York, 1968. \bibitem{broc} A. Brocot, Calcul des rouages par approximation, nouvelle m\'ethode, {\it Revue Chronom\'etrique. Journal des Horlogers, Scientifique et Pratique} {\bf 3} (1861), 186--194. \bibitem{cw} N. Calkin and H. Wilf, Recounting the rationals, {\it Amer. Math. Monthly} {\bf 107} (2000), 360--363, MR1763062 (2001d:11024). \bibitem{dr} G. de Rham, Un peu de math\'ematiques \`a propos d'une courbe plane. {\it Elem. Math.} {\bf 2} (1947), 73--76, 89--97 MR0022685 (9,246g), reprinted in {\it Oeuvres Math\'ematiques}, Geneva, 1981, 678--690, MR0638722 (84d:01081). \bibitem{dic} L. E. Dickson, {\it History of the Theory of Numbers, v. 1}, Carnegie Inst. of Washington, Washington, D.C., 1919, reprinted by Chelsea, New York, 1966, MR0245499 (39 \#6807a). \bibitem{dijk} E. W. Dijkstra, {\it Selected writings on computing: a personal perspective}, Springer-Verlag, New York, 1982, MR0677672 (85d:68001). \bibitem{gkp} R. L. Graham, D. E. Knuth, O. Patashnik, {\it Concrete Mathematics, Second Edition}, Addison-Wesley, Boston, 1994, MR1397498 (97d:68003). \bibitem{hayes} B. Hayes, On the teeth of wheels, {\it Amer. Sci.} {\bf 88}, July-August 2000, 296--300. \bibitem{hkmpp} A. Hinz, S. Klav\v zar, U. Milutinovi\'c, D. Parisse, C. Petr, Metric properties of the Tower of Hanoi graphs and Stern's diatomic sequence, {\it European J. Combin.} {\bf 26} (2005), 693--708, MR2127690 (2005m:05081). \bibitem{leh} D. H. Lehmer, On Stern's diatomic series, {\it Amer. Math. Monthly} {\bf 36} (1929), 59--67, MR1521653. \bibitem{luc} E. Lucas, {\it Th\'eorie des nombres, vol. 1}, Gauthier-Villars, Paris, 1891. \bibitem{minc} H. Minc, {\it Nonnegative matrices}, Wiley, New York, 1988, MR0932967 (89i:15061). \bibitem{mink} H. Minkowski, Zur Geometrie der Zahlen, Ver. III Int. Math.-Kong. Heidelberg 1904, pp. 164-173; in {\it Gesammelte Abhandlungen, Vol. 2}, Chelsea, New York 1967, pp. 45--52. \bibitem{rez1} B. Reznick, Some digital partition functions, in: B.C. Berndt et al. (Eds.),{\it Analytic Number Theory, Proceedings of a Conference in Honor of Paul T. Bateman}, Birkh\"auser, Boston, 1990, pp. 451--477, MR1084197 (91k:11092). \bibitem{rez2} B. Reznick, A Stern introduction to combinatorial number theory, in preparation. \bibitem{sch} W. Schmidt, The joint distribution of the digits of certain integer $s$-tuples, in: Paul Erd\"os, Editor-in-Chief, {\it Studies in Pure Mathematics to the memory of Paul Tur\'an}, Birkh\"auser, Basel, 1983, pp. 605--622, MR0820255 (87h:11072). \bibitem{ste} M. A. Stern, Ueber eine zahlentheoretische Funktion, {\it J. Reine Angew. Math.} {\bf 55} (1858) 193--220. \bibitem{urb} I. Urbiha, Some properties of a function studied by de Rham, Carlitz and Dijkstra and its relation to the (Eisenstein-)Stern's diatomic sequence, {\it Math. Commun.} {\bf 6} (2001) 181--198 (MR1908338 (2003f:11018) \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 05A15; Secondary 11B37, 11B57, 11B75. \noindent \emph{Keywords: } Stern sequence, enumerations of the rationals, Stern-Brocot array, Dijkstra's ``fusc" sequence, integer sequences mod $m$. \bigskip \hrule \bigskip \noindent (Concerned with sequence \seqnum{A002487}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received August 31 2008; revised version received September 16 2008. Published in {\it Journal of Integer Sequences}, September 16 2008. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}