Regularity Properties of the Stern Enumeration of the Rationals

Bruce Reznick Department of Mathematics University of Illinois Urbana, IL 61801 USA

                 reznick@math.uiuc.edu

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{a}{b} occurs exactly once in the form \frac{s(n)}{s(n+1)} for some n ≥ 1. We show that in a strong sense, the average value of these fractions is \frac{3}{2}. We also show that for d ≥ 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.

1 Introduction and History

In 1858, M. A. Stern [18] defined the 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.

a b ; a a + b b ; a 2a + b a + b a + 2b b ; a 3a + b 2a + b 3a + 2b a + b 2a + 3b a + 2b a + 3b b ; ⋮  (1)

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 Stern sequence can also be defined recursively by:

s(0) = 0, s(1) = 1,  s(2n) = s(n), s(2n + 1) = s(n) + s(n + 1).  (2)

Taking (a, b) = (1, 1) in (1), we obtain blocks of (s(n)) for 2^{r} ≤ n ≤ 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:

(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 ; ⋮  (3)

Mirror symmetry (or an easy induction) implies that for 0 ≤ k ≤ 2^{r}, we have

s(2^{r} + k) = s(2^{r+1} − k).  (4)

In his original paper, Stern proved that for all n,

gcd(s(n), s(n + 1)) = 1;  (5)

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 ℚ by fifteen years. This property of the Stern sequence has been recently made explicit and discussed [4] by Calkin and Wilf. Another enumeration of the positive rationals involves the Stern-Brocot array, which also predates Cantor; see Graham, Knuth and Patashnik [8, pp. 116–123, 305–306]. This was used by Minkowski [14] in defining his ?-function. The Stern sequence and Stern-Brocot array make brief appearances [6, pp. 156,426] in Dickson’s History. Apparently, de Rham [5] was the first to consider the sequence (s(n)) per se, attributing the term “Stern sequence” to Bachmann [2, p. 143], 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 [1] and the Tower of Hanoi graph [10] by Hinz, Klavžar, Milutinović, Parisse, and Petr. Some other Stern identities and a large bibliography relating to the Stern sequence are given [19] by Urbiha. A further discussion of the Stern sequence will be found in [16].

Let

t(n) = \frac{s(n)}{s(n + 1)}.  (6)

Here are blocks of (t(n)), for 2^{r} ≤ n < 2^{r+1} for small r:

(r = 0)  \frac{1}{1} ; (r = 1)  \frac{1}{2} \frac{2}{1} ; (r = 2)  \frac{1}{3} \frac{3}{2} \frac{2}{3} \frac{3}{1} ; (r = 3)  \frac{1}{4} \frac{4}{3} \frac{3}{5} \frac{5}{2} \frac{2}{5} \frac{5}{3} \frac{3}{4} \frac{4}{1} ; ⋮  (7)

In Section 3, we shall show that

∑_{n=0}^{N−1} t(n) = \frac{3N}{2} + O(log^{2} N),  (8)

so the “average” element in the Stern enumeration of ℚ_{+} is \frac{3}{2}.

For a fixed integer d ≥ 2, let

S_{d}(n) := (s(n) mod d, s(n + 1) mod d)  (9)

and let

S_{d} = {(i mod d, j mod d) : gcd(i, j, d) = 1}.  (10)

It follows from (5) that S_{d}(n) ∈ S_{d} for all n. In Section 4, we shall show that for each d, the sequence (S_{d}(n)) is uniformly distributed on S_{d}, so the “probability” that s(n) ≡ i (mod d) can be explicitly computed. More precisely, let

T (N; d, i) = |{n : 0 ≤ n < N & s(n) ≡ i mod d}| .  (11)

Then there exists τ_{d} < 1 so that

T (N; d, i) = r_{d,i}N + O(N^{τ_{d}}),  (12)

where

r_{d,i} = \frac{1}{d} · ∏_{p |i,p | d} \frac{p}{p + 1} · ∏_{p ∤ i,p | d} \frac{p^{2}}{p^{2} − 1}.  (13)

In particular, the probability that s(n) is a multiple of d is I(d)^{−1}, where

I(d) = d ∏_{p | d} \frac{p + 1}{p} ∈ ℕ.  (14)

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 τ_{2} = 0. We show that τ_{3} = \frac{1}{2} 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 ≥ 1, T (N; 3, 1) − T (N; 3, 2) ∈ {0, 1, 2, 3}.

It will be proved in [16] that

T (2^{r}; 4, 0) = T (2^{r}; 5, 0),  T (2^{r}; 6, 0) = T (2^{r}; 9, 0) = T (2^{r}; 11, 0);  (15)

we conjecture that T (2^{r}; 22, 0) = T (2^{r}; 27, 0). (The latter is true for r ≤ 19.) These exhaust the possibilities for T (2^{r}; N_{1}, 0) = T (2^{r}; N_{2}, 0) with N_{i} ≤ 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) ≠ T (2^{r}; 6, 0), so there is more than just asymptotics at work.

2 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 ≥ 0 and 0 ≤ k ≤ 2^{r} by:

\begin{matrix}Z(0, 0) = a, Z(0, 1) = b; \\ Z(r + 1, 2k) = Z(r, k), Z(r + 1, 2k + 1) = Z(r, k) + Z(r, k + 1). \end{matrix}  (16)

The following lemma follows from (2), (16) and a simple induction.

Lemma 1. For 0 ≤ k ≤ 2^{r}, we have

Z(r, k; 0, 1) = s(k).  (17)

Lemma 1 leads directly to a general formula for the diatomic array.

Theorem 2. For 0 ≤ k ≤ 2^{r}, we have

Z(r, k; a, b) = s(2^{r} − k)a + s(k)b.  (18)

Proof. Clearly, Z(r, k; a, b) is linear in (a, b) and it also satisfies a mirror symmetry

Z(r, k; a, b) = Z(r, 2^{r} − k; b, a)  (19)

for 0 ≤ k ≤ 2^{r}, c.f. (4). Thus,

Z(r, k; a, b) = aZ(r, k; 1, 0) + bZ(r, k; 0, 1) = aZ(r, 2^{r} − k; 0, 1) + bZ(r, k; 0, 1).  (20)

The result then follows from Lemma 1.

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).

Lemma 3. If 0 ≤ k ≤ 2^{r} and 0 ≤ k_{0} ≤ 2^{r_{0}} − 1, then

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)).  (21)

Corollary 4. If n ≥ 0 and 0 ≤ k ≤ 2^{r}, then

s(2^{r}n + k) = s(2^{r} − k)s(n) + s(k)s(n + 1).  (22)

Proof. Take (a, b, k_{0}, r_{0}) = (0, 1, n, ⌈log_{2}(n + 1)⌉) in Lemma 3, so that k_{0} < 2^{r_{0}}, and then apply Theorem 2.

We turn now to t(n). Clearly, t(2n) < 1 ≤ t(2n + 1) for all n; after a little algebra, (2) implies

t(2n) = \frac{1}{1 + \frac{1}{t(n)}} ,  t(2n + 1) = 1 + t(n).  (23)

The mirror symmetry (4) yields two other formulas which are evident in (7):

t(2^{r} + k)t(2^{r+1} − k − 1) = 1,  (24)

for 0 ≤ k ≤ 2^{r} − 1, which follows from

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)};  (25)

and

t(2^{r} + 2ℓ) + t(2^{r+1} − 2ℓ − 2) = 1,  (26)

for r ≥ 1 and 0 ≤ 2ℓ ≤ 2^{r} − 2, which follows from

\frac{s(2^{r} + 2ℓ)}{s(2^{r} + 2ℓ + 1)} + \frac{s(2^{r+1} − 2ℓ − 2)}{s(2^{r+1} − 2ℓ − 1)} = \frac{s(2^{r} + 2ℓ)}{s(2^{r} + 2ℓ + 1)} + \frac{s(2^{r} + 2ℓ + 2)}{s(2^{r} + 2ℓ + 1)},  (27)

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} ≤ 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 [11] 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} ≥ 1. (That is, n = 2^{a_{1}+···+a_{2v+1}} − 2^{a_{2}+···+a_{2v+1}} ± ⋯ ± 2^{a_{2v+1}} − 1.) Then

t(n) = \frac{s(n)}{s(n + 1)} = \frac{p}{q} = a_{2v+1} + \frac{1}{a_{2v} + \frac{1}{⋯ + \frac{1}{a_{1}}}} .  (28)

Conversely, if \frac{p}{q} > 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{p}{q} has the binary representation described above. (If n is even or \frac{p}{q} < 1, apply (24) first.)

The Stern-Brocot array is named after the clockmaker Achille Brocot, who used it [3] in 1861 as the basis of a gear table; see also Hayes [9]. This array caught the attention of several French number theorists, and is discussed [12] by Lucas. It is formed by applying the diatomic rule to numerators and denominators simultaneously:

(r = 0)  \frac{0}{1} \frac{1}{0} ; (r = 1)  \frac{0}{1} \frac{1}{1} \frac{1}{0} ; (r = 2)  \frac{0}{1} \frac{1}{2} \frac{1}{1} \frac{2}{1} \frac{1}{0} ; (r = 3)  \frac{0}{1} \frac{1}{3} \frac{1}{2} \frac{2}{3} \frac{1}{1} \frac{3}{2} \frac{2}{1} \frac{3}{1} \frac{1}{0} ; ⋮  (29)

This array is not quite the same as (7). If \frac{a}{b} and \frac{c}{d} 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 ≤ k ≤ 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.

Lemma 5. For 0 ≤ k ≤ 2^{r} − 2,

\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)}.  (30)

That is,

s(k + 1)s(2^{r} − k) − s(k)s(2^{r} − k − 1) = 1.  (31)

This lemma has a simple proof by induction, which can be found in Lucas [12, p.467], and Graham, Knuth and Patashnik [8, p.117].

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 [16]) for rationals \frac{p}{q} > 1 is that if 0 < k < 2^{r} is odd, then

\frac{p}{q} = \frac{s(2^{r} + k)}{s(2^{r} − k)} = \frac{s(\overleftarrow{2^{r} + k})}{s(\overleftarrow{2^{r} + k} + 1)},  (32)

where \overleftarrow{n} denotes the integer so that [n]_{2} and [\overleftarrow{n}]_{2} are the reverse of each other. If \frac{p}{q} < 1, then apply mirror symmetry to the instance of (32) which holds for \frac{q}{p}.

The Minkowski ?-function can be defined using the first half of the rows of (29). For odd ℓ, 0 ≤ ℓ ≤ 2^{r},

? (\frac{s(ℓ)}{s(2^{r+1} − ℓ)}) = \frac{ℓ}{2^{r}} .  (33)

This gives a strictly increasing map from ℚ ∩ [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

N = 2^{r_{1}} + 2^{r_{2}} + ⋯ + 2^{r_{v}},  r_{1} > r_{2} > ⋯ > r_{v}.  (34)

We shall define

N_{0} = 0; N_{j} = 2^{r_{1}} + ⋯ + 2^{r_{j}} for j = 1, …, v.  (35)

Further, for 1 ≤ j ≤ v, let M_{j} = 2^{−r_{j}}N_{j+1}, so that

N_{j} = N_{j−1} + 2^{r_{j}} = 2^{r_{j}}(M_{j} + 1) = 2^{r_{j−1}}M_{j−1}.  (36)

and, for a < b ∈ ℤ, let

[a, b) := {k ∈ ℤ : a ≤ k < b}.  (37)

Our proofs will rely on the observation that

[0, N) = ⋃_{j=0}^{v−1}[N_{j}, N_{j+1}) = ⋃_{j=1}^{v}[2^{r_{j}}M_{j}, 2^{r_{j}}(M_{j} + 1)),  (38)

where the above unions are disjoint, so that, formally,

∑_{n=0}^{N−1} = ∑_{j=0}^{v−1} ∑_{n=N_{j}}^{N_{j+1}−1} = ∑_{j=1}^{v} ∑_{n=2^{r_{j}} M_{j}}^{2^{r_{j}} (M_{j}+1)−1} .  (39)

3 The Stern-Average Rational

We begin by looking at the sum of t(n) along the rows of (7). Let

A(r) = ∑_{n=2^{r}}^{2^{r+1}−1} t(n) and Ã(r) = ∑_{n=0}^{2^{r}−1} t(n) = ∑_{i=0}^{r−1} A(i).  (40)

Lemma 6. For r ≥ 0,

A(r) = \frac{3}{2} · 2^{r} − \frac{1}{2} and Ã(r) = \frac{3}{2} · 2^{r} − \frac{r + 3}{2}. (41)

Proof. First note that A(0) = t(1) = \frac{1}{1} = \frac{3}{2} − \frac{1}{2}. Now observe that for r ≥ 0,

A(r + 1) = ∑_{j=0}^{2^{r+1}−1} t(2^{r+1} + j) = ∑_{k=0}^{2^{r}−1} t(2^{r+1} + 2k) + ∑_{k=0}^{2^{r}−1} t(2^{r+1} + 2k + 1).  (42)

Using (26) and (23), we can simplify this summation:

∑_{k=0}^{2^{r}−1} t(2^{r+1} + 2k) = \frac{1}{2} (∑_{k=0}^{2^{r}−1} t(2^{r+1} + 2k) + t(2^{r+2} − 2k − 2)) = 2^{r−1},  (43)

and

∑_{k=0}^{2^{r}−1} t(2^{r+1} + 2k + 1) = ∑_{k=0}^{2^{r}−1}(1 + t(2^{r} + k)) = 2^{r} + A(r).  (44)

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 Ã(r). Lemma 7. If m is even, then

Ã(r) ≤ ∑_{k=0}^{2^{r}−1} t(2^{r}m + k) < A(r).  (45)

Proof. For fixed (k, r), let

Φ_{k,r}(x) = \frac{s(2^{r} − k)x + s(k)}{s(2^{r} − (k + 1))x + s(k + 1)}.  (46)

Then it follows from (31) that

Φ′_{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.  (47)

Using (22), we see that

\begin{matrix}t(2^{r}m + k) = \frac{s(2^{r}m + k)}{s(2^{r}m + 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)} \\ = Φ_{k,r} (\frac{s(m)}{s(m + 1)}) = Φ_{k,r}(t(m)). \end{matrix}  (48)

Since m is even, 0 ≤ t(m) < 1; monotonicity then implies that

t(k) = Φ_{k,r}(0) ≤ t(2^{r}m + k) < Φ_{r,k}(1) = t(2^{r} + k).  (49)

Summing (49) on k from 0 to 2^{r} − 1 gives (45).

We use these estimates to establish (8).

Theorem 8. If 2^{r} ≤ N < 2^{r+1}, then

\frac{3N}{2} − \frac{r^{2} + 7r + 6}{4} ≤ ∑_{n=0}^{N−1} t(n) < \frac{3N}{2} − \frac{1}{2}.  (50)

Proof. Recalling (39), we apply Lemma 7 for each j, with r = r_{j} and m = M_{j}, so that

\frac{3}{2} · 2^{r_{j}} − \frac{r_{j} + 3}{2} ≤ ∑_{n=N_{j−1}}^{N_{j}−1} t(n) < \frac{3}{2} · 2^{r_{j}} − \frac{1}{2}.  (51)

After summing on j, we find that

\frac{3N}{2} − \frac{r_{1} + ⋯ + r_{v} + 3v}{2} ≤ ∑_{n=0}^{N−1} t(n) < \frac{3N}{2} − \frac{v}{2}.  (52)

To obtain (50), note that ∑ r_{j} + 3v ≤ \frac{r(r+1)}{2} + 3r + 3 = \frac{r^{2}+7r+6}{2}.

Corollary 9.

∑_{n=0}^{N−1} t(n) = \frac{3N}{2} + O (log^{2} N) .  (53)

Since t(2^{r} − 1) = \frac{r}{1}, the true error term is at least O(log N). Numerical computations using Mathematica suggest that log^{2} N can be replaced by log N log log N. It also seems that, at least for small fixed positive integers t,

α_{t} := lim_{N→∞} \frac{1}{N} ∑_{n=0}^{N−1} \frac{s(n)}{s(n + t)}  (54)

exists. We have seen that α_{1} = \frac{3}{2}, and if they exist, the evidence suggests that α_{2} ≈ 1.262, α_{3} ≈ 1.643 and α_{4} ≈ 1.161. We are unable to present an explanation for these specific numerical values.

4 Stern Pairs, mod d

We fix d ≥ 2 with prime factorization d = ∏ p_{ℓ}^{e_{ℓ}}, e_{ℓ} ≥ 1, and recall the definitions of S_{d} and S_{d}(n) from (9) and (10). Let

N_{d} = |S_{d}| ,  (55)

and for 0 ≤ i < d, let

N_{d}(i) = |{j mod d : (i mod d, j mod d) ∈ S_{d}}| .  (56)

We now give two lemmas whose proofs rely on the Chinese Remainder Theorem.

Lemma 10. The map S_{d} : ℕ → S_{d} is surjective.

Proof. Suppose α = (i, j) ∈ S_{d} with 0 ≤ i, j ≤ d − 1. We shall show that there exists w ∈ ℕ 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) = α.

Write i = ∏_{ℓ} q_{ℓ}^{f_{ℓ}}, f_{ℓ} ≥ 1, with q_{ℓ} prime. If q_{ℓ} | j, then q_{ℓ} ∤ d. There exists w ≥ 0 so that w ≡ d^{−1} (mod q_{ℓ}^{f_{ℓ}}) if q_{ℓ} | j and w ≡ 0 (mod q_{ℓ}^{f_{ℓ}}) if q_{ℓ} ∤ j. Then j + wd ≢ 0 (mod q_{ℓ}^{f_{ℓ}}) for all ℓ, so no prime dividing i divides j + wd, as desired.

Lemma 11. For 0 ≤ i ≤ d − 1,

N_{d} = d^{2} ∏_{ℓ} \frac{p_{ℓ}^{2} − 1}{p_{ℓ}^{2}}  and  N_{d}(i) = d ∏_{p_{ℓ} | i} \frac{p_{ℓ} − 1}{p_{ℓ}}.  (57)

Proof. To compute N_{d}, we use the Chinese Remainder Theorem by counting the choices for (i mod p_{ℓ}^{e_{ℓ}}, j mod p_{ℓ}^{e_{ℓ}}) for each ℓ. Missing are those (i, j) in which p_{ℓ} divides both i and j, and so the total number of classes is (p_{ℓ}^{e_{ℓ}} − p_{ℓ}^{e_{ℓ}−1})^{2} for each ℓ.

Now fix i. If p_{ℓ} | i, then (i, j) ∈ S_{d} if and only if p_{ℓ} ∤ j; if p_{ℓ} ∤ i, then there is no restriction on j. Thus, there are either p_{ℓ}^{e_{ℓ}} − p_{ℓ}^{e_{ℓ}−1} or p_{ℓ}^{e_{ℓ}} choices for j, respectively.

Suppose α = (i, j) ∈ S_{d}; let L(α) := (i, i + j) and R(α) = (i + j, j), where i + j is reduced mod d if necessary. Then L(α), R(α) ∈ S_{d} and the following lemma is immediate.

Lemma 12. For all n, we have S_{d}(2n) = L(S_{d}(n)) and S_{d}(2n + 1) = R(S_{d}(n)).

We now define the directed graph G_{d} as follows. The vertices of G_{d} are the elements of S_{d}. The edges of G_{d} consist of (α, L(α)) and (α, R(α)) where α ∈ S_{d}. Iterating, we see that L^{k}(α) = (i, i + kj) and R^{k}(α) = (i + kj, j), so that L^{d} = R^{d} = id, and L^{−1} = L^{d−1} and R^{−1} = R^{d−1}. Thus, if (α, β) is an edge of G_{d}, then there is a walk of length d − 1 from β to α.

Each vertex of G_{d} has out-degree two; since (L^{−1}(α), α) and (R^{−1}(α), α) are edges, each vertex has in-degree two as well. Let M_{d} = [m_{α(d)β(d)}] = [m_{αβ}] denote the adjacency matrix for G_{d}: M_{d} is the N_{d} × N_{d} 0-1 matrix so that m_{αL(α)} = m_{αR(α)} = 1, with other entries equal to 0. For a positive integer r, write

M_{d}^{r} = [m_{αβ}^{(r)}];  (58)

then m_{αβ}^{(r)} is the number of walks of length r from α to β. Finally, for γ ∈ S_{d}, and integers U_{1} < U_{2}, let

B(γ; U_{1}, U_{2}) = |{m : U_{1} ≤ m < U_{2} & S_{d}(m) = γ}|  (59)

The following is essentially equivalent to Lemma 3.

Lemma 13. Suppose α = S_{d}(m), β ∈ S_{d} and r ≥ 1. Then B(β; 2^{r}m, 2^{r}(m + 1)) = m_{αβ}^{(r)} is equal to the number of walks of length r in G_{d} from α to β.

Proof. The walks of length 1 starting from α are (α, L(α)) and (α, R(α)); 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.

Lemma 14. For sufficiently large N, m_{αβ}^{(N)} > 0 for all α, β.

Proof. Let α_{0} = (0, 1) = S_{d}(0). Note that L(α_{0}) = α_{0}, hence if there is a walk of length w from α_{0} to γ, then there are such walks of every length ≥ w. By Lemma 10, for each α ∈ S_{d}, there exists n_{α} so that S_{d}(n_{α}) = α. Choose r sufficiently large that n_{α} < 2^{r} for all α. Then by Lemma 13, for every γ, there is a walk of length r from α_{0} to γ, and so there is a walk of length (d − 1)r from γ to α_{0}. Thus, for any α, β ∈ S_{d}, there is at least one walk of length dr from α to β via α_{0}.

We need a version of Perron-Frobenius. Observe that A_{d} = \frac{1}{2}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 irreducible (see Minc [13, Ch. 1]), 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

f_{d}(T) = T^{k} + c_{k−1}T^{k−1} + ⋯ + c_{0}  (60)

be the minimal polynomial of M_{d}. Let ρ_{d} < 2 be the maximum modulus of any non-2 root of f_{d}, and let 1 + σ_{d} be the maximum multiplicity of any such maximal root. Then for r ≥ 0 and all (α, β),

m_{αβ}^{r+k} + c_{k−1}m_{αβ}^{r+k−1} + ⋯ + c_{0}m_{αβ}^{r} = 0.  (61)

It follows from the standard theory of linear recurrences that for some constants c_{αβ},

m_{αβ}^{r} = c_{αβ}2^{r} + (r^{σ_{d}}ρ_{d}^{r}) as r → ∞.  (62)

In particular, lim_{r→∞} A_{d}^{r} = A_{d0} := [c_{αβ}], 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 λ = 1. Such eigenvectors are constant vectors and since A_{d0} is doubly stochastic, we may conclude that for all (α, β), c_{αβ} = \frac{1}{N_{d}}. Then there exists c_{d} > 0 so that for r ≥ 0 and all (α, β),

|m_{αβ}^{r} − \frac{2^{r}}{N_{d}} | < c_{d}r_{d}^{σ_{d}}ρ_{d}^{r}.  (63)

Computations show that for for small values of d at least, ρ_{d} = \frac{1}{2} and σ_{d} = 0. In any event, by choosing 2 > ρ̄_{d} > ρ_{d} if σ_{d} > 0, we can replace r_{d}^{σ_{d}}ρ_{d}^{r} by ρ̄_{d}^{r} in the upper bound. Putting this together, we have proved the following theorem.

Theorem 15. There exist constants c_{d} and ρ̄_{d} < 2 so that if m ∈ ℕ and α ∈ S_{d}, then for all r ≥ 0,

|B(α; 2^{r}m, 2^{r}(m + 1)) − \frac{2^{r}}{N_{d}} | < c_{d}ρ̄_{d}^{r}.  (64)

We now use this result on blocks of length 2^{r} to get our main theorem.

Theorem 16. For fixed d ≥ 2, there exists τ_{d} < 1 so that, for all α ∈ S_{d},

B(α; 0, N) = \frac{N}{N_{d}} + O(N^{τ_{d}}).  (65)

Proof. By (39), we have

B(α; 0, N) = ∑_{j=0}^{v−1} B(α; N_{j}, N_{j+1}) = ∑_{j=1}^{v} B(α; 2^{r_{j}}M_{j}, 2^{r_{j}}(M_{j} + 1)).  (66)

It follows that

|B(α; 0, N) − \frac{N}{N_{d}} | ≤ c_{d}(ρ̄_{d}^{r_{1}} + ⋯ + ρ̄_{d}^{r_{v}}).  (67)

If ρ̄_{d} ≤ 1, the upper bound is O(r_{1}) = O(log N) = O(N^{ϵ}) for any ϵ > 0. If 1 ≤ ρ̄_{d} < 2, the upper bound is O(ρ̄_{d}^{r_{1}}) = O(N^{τ_{d}}) for τ_{d} = \frac{log ρ̄_{d}}{log 2} , since N ≤ 2^{r_{1}+1}.

Using the notation (11), we have

T (N; d, i) = ∑_{α=(i,j)∈S_{d}} B(α; 0, N),  (68)

and the following is an immediate consequence of Lemma 11 and Theorem 16.

Corollary 17. Suppose d ≥ 2. Then

T (N; d, i) = r_{d,i}N + O(N^{τ_{d}}),  (69)

where, recalling that d = ∏ p_{ℓ}^{e_{ℓ}},

r_{d,i} = \frac{1}{d} · ∏_{p_{ℓ}|i} \frac{p_{ℓ}}{p_{ℓ} + 1} · ∏_{p_{ℓ}∤i} \frac{p_{ℓ}^{2}}{p_{ℓ}^{2} − 1}.  (70)

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 ∤ 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(β; 2^{r}m, 2^{r}(m + 1))’s represent the distribution of destinations after r steps. Ken Stolarsky has pointed out that Schmidt [17] provides a somewhat different application of the limiting theory of Markov Chains in a number theoretic setting.

5 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 τ_{2} = 0. This generalizes to a family of partition sequences. Suppose d ≥ 2 is fixed, and let b(d; n) denote the number of ways that n can be written in the form

n = ∑_{i≥0} ϵ_{i}2^{i},  ϵ_{i} ∈ {0, …, d − 1},  (71)

so that b(2; n) = 1. It is shown in [15] that

∑_{n=0}^{∞} s(n)X^{n} = X ∏_{j=0}^{∞} (1 + X^{2^{j}} + X^{2^{j+1}}) .  (72)

A standard partition argument shows that

∑_{n=0}^{∞} b(d; n)X^{n} = ∏_{j=0}^{∞} \frac{1 − X^{d·2^{j}}}{1 − X^{2^{j}}} .  (73)

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 ≡ 0, 1 mod d (see [15], Theorems 5.2 and 2.14.)

Suppose now that d = 3. Write the 8 elements of S_{3} in lexicographic order:

(0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2).  (74)

Then in the notation of the last section,

M_{3} = (\begin{matrix}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{matrix}) .  (75)

The minimal polynomial of M_{3} is

f_{3}(T) = T^{5} − 2T^{4} + T^{3} − 4T^{2} + 4T = T (T − 1)(T − 2)(T − μ)(T − μ̄),  (76)

where

μ = \frac{−1 + \sqrt{7}i}{2},  μ̄ = \frac{−1 − \sqrt{7}i}{2}.  (77)

Since the roots of f_{3} are distinct, we see that for each (α, β) ∈ S_{3}, for r ≥ 1, there exist constants v_{αβi} so that

m_{αβ}^{(r)} = v_{αβ1} + v_{αβ2}μ^{r} + v_{αβ3}μ̄^{r} + \frac{1}{8} · 2^{r} = \frac{1}{8} · 2^{r} + O(2^{r/2}).  (78)

(As it happens, there are only eight distinct sequences m_{αβ}^{(r)}.) Corollary 17 then implies that

\begin{matrix}T (N; 3, 0) = \frac{N}{4} + O(\sqrt{N}), \\ T (N; 3, 1) = \frac{3N}{8} + O(\sqrt{N}), T (N; 3, 2) = \frac{3N}{8} + O(\sqrt{N}). \end{matrix}  (79)

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

Δ(N) = Δ_{3}(N) := T (N; 3, 1) − T (N; 3, 2).  (80)

(That is, Δ_{3}(N + 1) − Δ_{3}(N) equals 0, 1, −1 when s(N) ≡ 0, 1, 2 mod 3, respectively.) To study T (N; 3, 0), we first define the set A_{3} ⊂ ℕ recursively by:

0, 5, 7 ∈ A_{3},  0 < n ∈ A_{3} ⟹ 2n, 8n ± 5, 8n ± 7 ∈ A_{3}.  (81)

Thus,

A_{3} = {0, 5, 7, 10, 14, 20, 28, 33, 35, 40, 45, 47, 49, 51, 56, 61, 63, … }.  (82)

Theorem 18. If n ≥ 0, then 3 | s(n) if and only if n ∈ A_{3}.

Proof. It follows recursively from (2) or directly from (22) that

s(2n) = s(n), s(8n ± 5) = 2s(n) + 3s(n ± 1),  s(8n ± 7) = s(n) + 3s(n ± 1). (83)

Thus, 3 divides s(n) if and only if 3 divides s(2n), s(8n ± 5) or s(8n ± 7). Since every n > 1 can be written uniquely as 2n′, 8n′ ± 5 or 8n′ ± 7 with 0 ≤ n′ < n, the description of A_{3} is complete.

In the late 1970’s, E. W. Dijkstra [7, pp. 215–6, 230–232] studied the Stern sequence under the name “fusc”, and gave a different description of A_{3} (p. 232):

Inspired by a recent exercise of Don Knuth I tried to characterize the arguments n such that 3 | 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|?1{0}1}?1{0}. I derived this by considering – as a direct derivation of my program – the finite state automaton that computes fusc (N) mod 3.

Let

a_{r} = |{n ∈ A_{3} : 2^{r} ≤ n < 2^{r+1}}| = T (2^{r+1}; 3, 0) − T (2^{r}; 3, 0).  (84)

It follows from (82) that

a_{0} = a_{1} = 0, a_{2} = a_{3} = a_{4} = 2, a_{5} = 10.  (85)

Lemma 19. For r ≥ 3, (a_{r}) satisfies the recurrence

a_{r} = a_{r−1} + 4a_{r−3}.  (86)

Proof. This is evidently true for r = 3, 4, 5. If 2^{r} ≤ n < 2^{r+1} and n = 2n′, then 2^{r−1} ≤ 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} ≤ n < 2^{r+1} and n = 8n′ ± 5 or n = 8n′ ± 7, then 2^{r−3} < n′ < 2^{r−2} and n′ ∈ 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}.

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, μ and μ̄. The details of the following routine computation are omitted.

Theorem 20. For r ≥ 0, we have the exact formula

a_{r} = \frac{1}{4} · 2^{r} + (\frac{−7 + 5\sqrt{7}i}{56}) μ^{r} + (\frac{−7 − 5\sqrt{7}i}{56}) μ̄^{r}.  (87)

Keeping in mind that s(0) = 0 is not counted in any a_{r}, we find after a further computation that the error estimate O(\sqrt{N}) is best possible for T (N; 3, 0):

Corollary 21.

T (2^{r}; 3, 0) = \frac{1}{4} · 2^{r} + (\frac{7 − \sqrt{7}i}{56}) μ^{r} + (\frac{7 + \sqrt{7}i}{56}) μ̄^{r} + \frac{1}{2} .  (88)

To study Δ(N), we first need a somewhat surprising lemma.

Lemma 22. For all N, Δ(2N) = Δ(4N).

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{matrix}\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} = \\ 0  1 0  1  1 0 1 1 2 1 & | & | & 0  2 0  2  2 0 2 2 1 2 & | & | & 1  0 1  1  0 1 2 1 1 0 & | & | & 1  1 1  2  1 1 0 2 0 1 \\ 1  2 1  0  2 1 1 0 2 2 & | & | & 2  0 2  2  0 2 1 2 2 0 & | & | & 2  1 2  0  1 2 2 0 1 1 & | & | & 2  2 2  1  2 2 0 1 0 2 \end{matrix}  (89)

By counting the elements in the rows mod 3 in each case, we see that Δ(2N + 2) − Δ(2N) = Δ(4N + 4) − Δ(4N) is equal to: 1, −1, 2, 0, 1, −2, −1, 0, respectively.

Theorem 23. For all n, Δ(n) ∈ {0, 1, 2, 3}. More specifically,

S_{3}(m) = (0, 1) ⟹ Δ(2m) = 0, Δ(2m + 1) = 0;
S_{3}(m) = (0, 2) ⟹ Δ(2m) = 3, Δ(2m + 1) = 3;
S_{3}(m) = (1, ∗) ⟹ Δ(2m) = 1, Δ(2m + 1) = 2;
S_{3}(m) = (2, ∗) ⟹ Δ(2m) = 2, Δ(2m + 1) = 1.

(90)

Proof. To prove the theorem, we first observe that it is correct for m ≤ 4. We now assume it is true for m ≤ 2^{r} and prove it for 2^{r} ≤ 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 Δ(2m) = 2 by hypothesis, and hence Δ(4m) = 2 by Lemma 22. The eighth array in (89) shows that s(4t) ≡ 2 mod 3, so that Δ(4m + 1) = Δ(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 Δ(2t) = 1 and Δ(2t + 1) = 2 by hypothesis and Δ(4t) = 1 by Lemma 22. The fourth array in (89) shows that (s(4t), s(4t + 1), s(4t + 2)) ≡ (1, 0, 2) mod 3. Thus, it follows that Δ(2m) = Δ(4t + 2) = Δ(4t) + 1 + 0 = 2 and Δ(2m + 1) = Δ(4t + 3) = Δ(4t + 2) − 1 = 1, again as desired.

Since S_{3}(m) is uniformly distributed on S_{3}, (90) shows that Δ(n) takes the values (0, 1, 2, 3) with limiting probability (\frac{1}{8}, \frac{3}{8}, \frac{3}{8}, \frac{1}{8}).

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 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, −τ, −τ̄) 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 ≤ 2^{19} shows that −5 ≤ T (N; 5, 1) − T (N; 5, 4) ≤ 11. These topics will be discussed in greater detail in [16].

References

[1] J.-P. Allouche, J. Shallit, The ring of k-regular sequences, Theoret. Comput. Sci. 98 (1992), 163–197, MR1166363 (94c:11021).

[2] P. Bachmann, Niedere Zahlentheorie, v. 1, Leipzig 1902, Reprinted by Chelsea, New York, 1968.

[3] A. Brocot, Calcul des rouages par approximation, nouvelle méthode, Revue Chronométrique. Journal des Horlogers, Scientifique et Pratique 3 (1861), 186–194.

[4] N. Calkin and H. Wilf, Recounting the rationals, Amer. Math. Monthly 107 (2000), 360–363, MR1763062 (2001d:11024).

[5] G. de Rham, Un peu de mathématiques à propos d’une courbe plane. Elem. Math. 2 (1947), 73–76, 89–97 MR0022685 (9,246g), reprinted in Oeuvres Mathématiques, Geneva, 1981, 678–690, MR0638722 (84d:01081).

[6] L. E. Dickson, 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).

[7] E. W. Dijkstra, Selected writings on computing: a personal perspective, Springer-Verlag, New York, 1982, MR0677672 (85d:68001).

[8] R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics, Second Edition, Addison-Wesley, Boston, 1994, MR1397498 (97d:68003).

[9] B. Hayes, On the teeth of wheels, Amer. Sci. 88, July-August 2000, 296–300.

[10] A. Hinz, S. Klavžar, U. Milutinović, D. Parisse, C. Petr, Metric properties of the Tower of Hanoi graphs and Stern’s diatomic sequence, European J. Combin. 26 (2005), 693– 708, MR2127690 (2005m:05081).

[11] D. H. Lehmer, On Stern’s diatomic series, Amer. Math. Monthly 36 (1929), 59–67, MR1521653.

[12] E. Lucas, Théorie des nombres, vol. 1, Gauthier-Villars, Paris, 1891.

[13] H. Minc, Nonnegative matrices, Wiley, New York, 1988, MR0932967 (89i:15061).

[14] H. Minkowski, Zur Geometrie der Zahlen, Ver. III Int. Math.-Kong. Heidelberg 1904, pp. 164-173; in Gesammelte Abhandlungen, Vol. 2, Chelsea, New York 1967, pp. 45–52.

[15] B. Reznick, Some digital partition functions, in: B.C. Berndt et al. (Eds.),Analytic Number Theory, Proceedings of a Conference in Honor of Paul T. Bateman, Birkhäuser, Boston, 1990, pp. 451–477, MR1084197 (91k:11092).

[16] B. Reznick, A Stern introduction to combinatorial number theory, in preparation.

[17] W. Schmidt, The joint distribution of the digits of certain integer s-tuples, in: Paul Erdös, Editor-in-Chief, Studies in Pure Mathematics to the memory of Paul Turán, Birkhäuser, Basel, 1983, pp. 605–622, MR0820255 (87h:11072).

[18] M. A. Stern, Ueber eine zahlentheoretische Funktion, J. Reine Angew. Math. 55 (1858) 193–220.

[19] I. Urbiha, Some properties of a function studied by de Rham, Carlitz and Dijkstra and its relation to the (Eisenstein-)Stern’s diatomic sequence, Math. Commun. 6 (2001) 181–198 (MR1908338 (2003f:11018)

2000 Mathematics Subject Classification: Primary 05A15; Secondary 11B37, 11B57, 11B75. Keywords: Stern sequence, enumerations of the rationals, Stern-Brocot array, Dijkstra’s “fusc” sequence, integer sequences mod m.

(Concerned with sequence \underline{A002487}.) Received August 31 2008; revised version received September 16 2008. Published in Journal of Integer Sequences, September 16 2008. Return to Journal of Integer Sequences home page.