An Analogue of Stern’s Sequence for ℤ[\sqrt{2}]

Sam Northshield Department of Mathematics SUNY-Plattsburgh Plattsburgh, NY 12901 USA

                   northssw@plattsburgh.edu

Abstract

We introduce a sequence b(n) of algebraic integers that is an analogue of Stern’s diatomic sequence, not only in definition, but also in many of its properties. Just as Stern’s sequence arises from Ford circles, so too b(n) arises from an array of circles. We study the generating function for b(n) and derive several closed formulas for the sequence. Two second order recurrence formulas for b(n) are found. It is shown that, for t the square root of 2, the ratios t·b(n+1)/b(n) enumerate the positive rational numbers. Finally, we use b(n) to create a function f(x) that is an analogue of Conway’s box function and that has inverse a singular function analogous to Minkowski’s questionmark function.

1 Introduction

Stern’s diatomic sequence is a particularly well studied sequence; see the survey paper by Northshield [9], sequence \underline{A002487} in [12], and the references therein. In this paper, we introduce a new sequence in ℤ[\sqrt{2}] that is an analogue of Stern’s sequence both in definition and also in most of the properties described by Northshield [9].

In Section 2, we introduce the sequence (b_{n})_{n≥0}. We also describe a “diatomic array” so, as for Stern’s sequence, it earns the adjective “diatomic”. We also develop some basic properties of the sequence.

In Section 3, we recall “Ford circles” and their parameterization by rational numbers. Stern’s sequence appears as numerators and denominators in various generations of these circles. A variant of the family of Ford circles is introduced, perhaps first studied by Guettler and Mallows [5], and we show how our sequence (b_{n}) arises from these circles.

In Section 4, we find a closed formula for the generating function for (b_{n}). Just as Fibonacci numbers have a closed formula in terms of roots of a certain equation (Binet’s formula), Northshield [9] showed that an analogous closed formula exists for Stern’s sequence (involving s_{2}(n), the number of ones in the binary representation of an n). Here we derive an analogous closed formula for (b_{n}), this time involving s_{3,1}(n), the number of ones in the ternary representation of n. Another closed formula is given in terms of generalized Lucas numbers.

In Section 5, we show that (b_{n}) satisfies a three-term recurrence

b_{n+1} = (2ν_{3}(n) + 1)\sqrt{2}b_{n} − b_{n−1}

where ν_{3}(n) := max{k : 3^{k}|n}. We show that a similar formula holds for Stern’s sequence (a_{n}) as well:

a_{n+1} = (2ν_{2}(n) + 1)a_{n} − a_{n−1}

where ν_{2}(n) := max{k : 2^{k}|n}. We are also able to give a modified Fibonacci recurrence for (b_{n}) as follows:

b_{n+1} = \sqrt{2}b_{n} + b_{n−1} − 2(b_{n−1} mod (\sqrt{2}b_{n}))

which is analogous to a result of Northshield [9, Proposition 4.3]:

a_{n+1} = a_{n} + a_{n−1} − 2(a_{n−1} mod a_{n}).

In Section 6, we define a function on the triadic rationals in [0, 1] by

f (\frac{k}{3^{n}} ) = \frac{b_{k}}{b_{k} + b_{3^{n}−k}} .

We determine the range of f and consequently identify the set {[b_{k}, b_{k+1}]} as the pairs of non-negative relatively prime integers (in the ring ℤ[\sqrt{2}]) such that \sqrt{2}b_{k+1}/b_{k} ∈ ℚ. It follows that the map n ↦ R_{n} defined by

R_{1} = 2, R_{n} = 4ν_{3}(n) + 2 − \frac{2}{R_{n−1}}

is a bijection from ℤ^{+} to ℚ^{+}. Alternatively, the iterates of 2 + \frac{2}{x} − 4 \{\frac{1}{x}\}, starting at 2, span the entire set of positive rational numbers.

In Section 7, the function f introduced in Section 6 is shown to extend to a continuous strictly increasing function on [0, 1]. Its inverse is an analogue of Minkowski’s question-mark function ?(x) and, in fact, it shares the same formula in terms of the continued fraction expansion of x as the original ?(x) except for the base of 2 is changed to 3.

In Section 8 we give some directions for future research and, in Section 9, we give Maple code for the sequence (b_{n}) as well as the first 101 terms of (b_{n}).

2 The sequence

Throughout this paper, for notational convenience, we let τ := \sqrt{2}. Let b_{0} := 0, b_{1} := 1, and

\begin{matrix}b_{3n} := b_{n}; \\ b_{3n+1} := τ · b_{n} + b_{n+1}; \\ b_{3n+2} := b_{n} + τ · b_{n+1}. \end{matrix}  (1)

Looking at the first few terms, we get

0, 1, τ, 1, 2τ, 3, τ, 3, 2τ, 1, 3τ, 5, 2τ, 7, 5τ, 3, 4τ, 5, τ, 5, 4τ, 3, 5τ, 7, 2τ, 5, …

Maple code for constructing this sequence, and a longer list of its elements, is in the Appendix (Section 9).

Consider an (infinite) array of numbers with first three rows given as follows:

1  τ
1 2τ 3 τ
1 3τ 5 2τ 7 5τ 3 4τ 5 τ
. . . . . . . . . .

This is similar to Pascal’s triangle in that every entry in all but the top row is the weighted sum of certain entries above. Specifically, given the nth row, we get the next row by repeating the nth row but, between each two entries, we put the sums of those entries weighted by [τ, 1] and [1, τ], respectively. Any entry which is at the top of a column is the sum of two entries on the previous row while any other entry just repeats the entry directly above it.

Any entry not in the first or last column contribute to five below and receive from either one or two above, so that its “valence” (here meaning the number of bonds made with other entries) is 6 or 7. We say the array is “diatomic”: Conceivably, an alloy with two types of atoms, of chemical valence 6 or 7, could combine to make a kind of crystal described by the diatomic array. Of course, such a crystal could only exist in hyperbolic space since row size increases exponentially. The sequence (b_{n}) arises from this array: the nth row is b_{3^{n}}, …, b_{2·3^{n}} (and the reverse of the nth row is b_{2·3^{n}}, …, b_{3^{n+1}}). Just as it was for Stern’s diatomic sequence, the adjective “diatomic” is appropriate for (b_{n}) as well.

We observe that the nth row of the diatomic array contains 3^{n−1} + 1 elements while the sum of the elements in the nth row satisfies the recurrence S_{n+1} = η^{2}(S_{n} − 1) where η := 1 + \sqrt{2} is the fundamental unit of ℤ[\sqrt{2}] (i.e., all a + b\sqrt{2} with norm a^{2} − 2b^{2} = ±1 are of the form ±η^{n} for some n ∈ ℤ). Note that S_{n} = x_{n} + y_{n}\sqrt{2} where (x_{n}) and (y_{n}) are the integer sequences \underline{A046090} and \underline{A011900} in [12], respectively.

Each segment b_{3^{n}}, …, b_{3^{n+1}} of our original sequence (b_{n}) is palindromic and we may express this symmetry as a formula:

Proposition 1. For all n and all k between 0 and 2 · 3^{n},

b_{3^{n}+k} = b_{3^{n+1}−k}.  (2)

Proof. (Induction on n). The n = 0 case follows from the fact that b_{1} = 1 = b_{3}.

Suppose that the conclusion of the proposition is true for n and that k is between 0 and 2 · 3^{n+1}. There are three cases: k = 3j + i where i = 0, 1, or 2.

In the case where k = 3j,

b_{3^{n+1}+k} = b_{3^{n}+j} = b_{3^{n+1}−j} = b_{3^{n+2}−k}.

For k = 3j + i where j = 1 or 2, if 0 ≤ 3k + j ≤ 2 · 3^{n+1} then −j ≤ 3k ≤ 2 · 3^{n+1} − j and so 0 ≤ k ≤ 2 · 3^{n} − 1. Hence, by the inductive hypothesis,

b_{3^{n}+j+1} = b_{3^{n+1}−j−1} and b_{3^{n}+j} = b_{3^{n+1}−j}.

When k = 3j + 1,

\begin{aligned}b_{3^{n+1}+k} & = b_{3(3^{n}+j)+1} = τb_{3^{n}+j} + b_{3^{n}+j+1} \\ & = τb_{3^{n+1}−j} + b_{3^{n+1}−j−1} = b_{3(3^{n+1}−j−1)+2} = b_{3^{n+2}−k}. \end{aligned}

When k = 3j + 2,

\begin{aligned}b_{3^{n+1}+k} & = b_{3(3^{n}+j)+2} = b_{3^{n}+j} + τb_{3^{n}+j+1} \\ & = b_{3^{n+1}−j} + τb_{3^{n+1}−j−1} = b_{3(3^{n+1}−j−1)+1} = b_{3^{n+2}−k}. \end{aligned}

Consider next the crushed array formed by taking rows of b_{3^{n}}, …, b_{3^{n+1}−1} with all the terms squeezed to the left as far as possible:

1 τ
1 2τ 3 τ 3 2τ
1 3τ 5 2τ 7 5τ 3 4τ 5 τ 5 4τ 3 5τ 7 2τ 5 3τ
1 4τ 7 3τ 11 8τ 5 7τ 9 2τ 11 9τ 7 12τ 17 5τ 13 8τ …

Apparently, each column is an arithmetic sequence (i.e., successive differences are constant) and the sequence of these differences is (τb_{n}).

Proposition 2. If 0 ≤ k < 3^{n}, then

b_{3^{n}+k} − b_{3^{n}−k} = \sqrt{2}b_{k}.

Proof. (Induction on n). Since b_{1+0} − b_{1−0} = 0 = τb_{0} and b_{1+1} − b_{1−1} = b_{2} − b_{0} = τ = τb_{1}, the proposition holds for n = 0.

Suppose the proposition is true for n and let k be between 0 and 3^{n+1} −1 inclusive. There are three cases: k = 3j + i for i = 0, 1, or 2.

If k = 3j, then

b_{3^{n+1}+k} − b_{3^{n+1}−k} = b_{3(3^{n}+j)} − b_{3(3^{n}−j)} = b_{3^{n}+j} − b_{3^{n}−j} = τb_{j} = τb_{k}.

If k = 3j + 1, then

b_{3^{n+1}+k} − b_{3^{n+1}−k} = b_{3(3^{n}+j)+1} − b_{3(3^{n}−j−1)+2}
= (τb_{3^{n}+j} + b_{3^{n}+j+1}) − (b_{3^{n}−j−1} + τb_{3^{n}−j})
= τ(b_{3^{n}+j} − b_{3^{n}−j}) + (b_{3^{n}+j+1} − b_{3^{n}−j−1})
= τ^{2}b_{j} + τb_{j+1} = τb_{k}.

If k = 3j + 2, then

b_{3^{n+1}+k} − b_{3^{n+1}−k} = b_{3(3^{n}+j)+2} − b_{3(3^{n}−j−1)+1}
= (b_{3^{n}+j} + τb_{3^{n}+j+1}) − (τb_{3^{n}−j−1} + b_{3^{n}−j})
= (b_{3^{n}+j} − b_{3^{n}−j}) + τ(b_{3^{n}+j+1} − b_{3^{n}−j−1})
= τb_{j} + τ^{2}b_{j+1} = τb_{k}.

Proposition 3. For 0 ≤ k < 3^{n},

b_{k+1}b_{3^{n}−k} − b_{k}b_{3^{n}−k−1} = 1.

Although it is possible to prove Proposition 3 using induction and the two previous propositions, we will defer the proof to Section 6 (equation (7)).

Theorem 4. Let j(n) := (3^{n} + 1)/2. Then

max\{b_{k} : 3^{n} ≤ k < 3^{n+1}\} = b_{j(n)} = \frac{(\sqrt{2} + 1)^{n} + (\sqrt{2} − 1)^{n}}{2} .

Proof. Let x_{n} := ((τ + 1)^{n} + (τ − 1)^{n})/2. Since τ ± 1 are zeros of x^{2} − 2τx + 1, it follows that

x_{0} = 1, x_{1} = τ, x_{n+1} = 2τx_{n} − x_{n−1}.

We show that b_{j(n)} satisfies the same recurrence. Note b_{j(0)} = b_{1} = 1 = x_{0} and b_{j(1)} = b_{2} = τ = x_{1}. Since

b_{3k−2} = b_{3(k−1)+1} = τb_{k−1} + b_{k} = τ(b_{k−1} + τb_{k}) − b_{k} = τb_{3(k−1)+2} − b_{k} = τb_{3k−1} − b_{k},

it follows that

b_{9k−4} = b_{3k−2} + τb_{3k−1} = 2τb_{3k−1} − b_{k}.

Replacing k by j(n − 1) and using the facts that j(n) = 3j(n − 1) − 1 and j(n + 1) = 9j(n − 1) − 4,

b_{j(n+1)} = 2τb_{j(n)} − b_{j(n−1)}

and therefore b_{j(n)} = x_{n}.

A similar argument shows b_{j′(n)} = ((τ + 1)^{n} − (τ − 1)^{n})/2 where j′(n) = j(n) − 1 = (3^{n} − 1)/2. Hence b_{j(n)−1}^{2} = b_{j(n)}^{2} − 1 and so b_{j(n)−1} is the second largest value in nth row. It follows that the largest value in the (n + 1)st row is b_{j(n)−1} + τb_{j(n)} = b_{3j(n)−1} = b_{j(n+1)}. By induction, the theorem follows.

Corollary 5. lim sup_{n→∞} \frac{2b_{n}}{(2n)^{log_{3}(1+\sqrt{2})}} ≥ 1.

We conjecture that equality holds here. If true, then this is an analogue of a recent result by Coons and Tyler [3] on Stern’s sequence.

3 Ford circles

We say a circle in the x, y-plane is normal if it is above and tangent to the x-axis. For t ∈ ℝ and r > 0, let C(t, r) be the circle with center (t, r) and radius r. Hence, C(t, r) is normal. We note that every normal circle can be uniquely represented as C(t, r) for some t, r. By the Pythagorean theorem, two circles C(t, r) and C(t′, r′) are tangent (we write C(t, r)||C(t′, r′)) if and only if

(t − t′)^{2} + (r − r′)^{2} = (r + r′)^{2}

or, equivalently,

(t − t′)^{2} = 4rr′.  (3)

Given a, b ∈ ℝ with b > 0, we define

C_{a,b} := C (\frac{a}{b}, \frac{1}{2b^{2}} ) .

Then every circle above and tangent to the x-axis can be uniquely represented as C_{a,b} for some real a, b (b > 0):

C(t, r) = C_{t/\sqrt{2r},1/\sqrt{2r}}.

By (3), two such circles are tangent, i.e., C_{a,b}||C_{c,d}, if and only if |ad − bc| = 1.

From this point on, we write a ⊥ b for a, b relatively prime. We define the set of Ford circles as follows:

F := {C_{a,b} : a, b ∈ ℤ, a ⊥ b}.

Hence F is parameterized by the rationals via the map taking a/b (in lowest terms) to C_{a,b}.

Given two normal circles that are tangent to each other, there is a unique normal circle between and tangent to both. Further, it is easy to see that if these circles are C_{a,b}, C_{c,d} (i.e., |ad − bc| = 1) then C_{a+c,b+d} is the unique circle between and tangent to both.

The Ford circles are also constructed by a recursive geometric procedure: the family of Ford circles of level 0 is just {C_{0,1}, C_{1,1}} and, given any two tangent circles of a family of level

Figure 1: Ford Circles

n, add the unique circle between and tangent to those two. The family of level n together with all the circles arising as above creates the family of level n + 1. F turns out to be the union of all the families of all levels [8]. The family of Ford circles of level n is parameterized by Stern’s diatomic sequence (a_{n})_{n≥0} defined by a_{0} = 0, a_{1} = 1, a_{2n} = a_{n}, a_{2n+1} = a_{n} + a_{n+1} [9]:

{C_{a_{k},a_{k}+a_{2^{n}−k}} : k = 0, .., 2^{n}}.

A variant of the family of Ford circles has been introduced and studied by Guettler and Mallows [5]. Given any two tangent normal circles, there exists a unique triple of mutually tangent circles between them, two of which are normal. If we iterate the process of taking these two (instead of taking the unique normal circle between, as for Ford circles) then the resulting array (see Figure 2) is that of Guettler and Mallows [5]. We shall now show that the circles of level n are then of the form C_{b_{k},b_{k}+b_{3^{n}−k}}.

Figure 2: Ford Circles variant

We shall use the notation

(\begin{matrix}a & c \\ b & d \end{matrix}) (z) := \frac{az + c}{bz + d}

and thus express every Möbius transformation in terms of a (non-singular) matrix. It is well known that Möbius transformations take circles to circles (straight lines are considered circles too since, on the Riemann sphere, they are circles through ∞ [7]). For real a, b, c, d with ad − bc = 1, the Möbius transformation above preserves the x-axis and takes x/y to (ax + cy)/(bx + dy). Furthermore, since the imaginary part of m(z) is (ad − bc)/|cz + d|^{2} times the imaginary part of z, m takes normal circles to normal circles.

Lemma 6. If m is a Möbius transformation (\begin{matrix}a & c \\ b & d \end{matrix}) with ad − bc = 1, then m′(z) =

1/(bz + d)^{2},

m : C(z, r) ↦ C(m(z), |m′(z)|r),

and, consequently,

(\begin{matrix}a & c \\ b & d \end{matrix}) : C_{x,y} ↦ C_{ax+cy,bx+dy}.

Proof. Since a, b, c, d are real, the Möbius transformation (\begin{matrix}a & c \\ b & d \end{matrix}) takes the x-axis to itself

and therefore m(C(z, r)) = C(m(z), r′) for some r′ > 0. Let w ≠ z in ℝ. There exists a unique s > 0 such that C(z, r)||C(w, s). There is then some s′ such that m(C(w, s)) = C(m(w), s′). Since

4r′s′ = |m(z) − m(w)|^{2} = |m′(z)||m′(w)||z − w|^{2} = |m′(z)||m′(w)|4rs,

it follows that s′/(|m′(w)|s) is a constant function of w (equal to k := |m′(z)|r/r′). Letting w converge to z shows that \frac{1}{k} = k and so r′ = |m′(z)|r.

The second part follows.

\begin{aligned}C_{ax+cy,bx+dy} & = C (\frac{ax + cy}{bx + dy} , \frac{1}{2|bx + dy|^{2}} ) = C (m (\frac{x}{y}) , \frac{1}{2y^{2} (b(\frac{x}{y}) + d)^{2}} ) \\ & = C (m (\frac{x}{y}) , |m′ (\frac{x}{y})| · \frac{1}{2y^{2}} ) = m (C (\frac{x}{y}, \frac{1}{2y^{2}} )) = m(C_{x,y}). \end{aligned}

Theorem 7. Given two tangent normal circles C_{a,b}, C_{c,d}, there exist a unique triple of three mutually tangent circles between them so that the six circles have octahedral contact graph and such that two of those circles are normal. The two normal circles are C_{τa+c,τb+d} and C_{a+τc,b+τd}.

Proof. Given C_{0,1} and C_{1,0} (which is the line y = 1), it is easy to see that C_{τ,1}, C_{1,τ}, and its reflection across y = 1/2 are the unique (up to reflection around x = 0) three mutually tangent circles so that the collection of all six has octahedral contact graph. By Lemma 6,

(\begin{matrix}a & c \\ b & d \end{matrix}) : C_{1,0}, C_{0,1}, C_{τ,1}, C_{1,τ} ↦ C_{a,b}, C_{c,d}, C_{τa+c,τb+d}, C_{a+τc,b+τd}.

For 0 ≤ k ≤ 3^{n}, let C [\frac{k}{3^{n}} ] := C_{b_{k},b_{k}+b_{3^{n}−k}}.

Corollary 8. For 0 ≤ k < 3^{n}, C [\frac{k}{3^{n}} ] ||C [\frac{k+1}{3^{n}}] and the two normal circles as defined by Theorem 7 are given by C [\frac{3k+1}{3^{n+1}}] and C [\frac{3k+2}{3^{n+1}}].

Proof. Let A = b_{k}, B = b_{k} + b_{3^{n}−k}, C = b_{k+1}, and D = b_{k+1} + b_{3^{n}−k−1}. By Proposition 3, C_{A,B}||C_{C,D} and so C [\frac{k}{3^{n}} ] ||C [\frac{k+1}{3^{n}}]. By Theorem 7, the two “new circles” are C_{τA+C,τB+D} and C_{A+τC,B+τD}. It is easy to check, by (1), that τA + C = b_{3k+1}, A + τC = b_{3k+2}, τB + D = b_{3k+1} + b_{3^{n+1}−(3k+1)}, and B + τD = b_{3k+2} + b_{3^{n+1}−(3k+2)}. The result follows.

4 Generating function

Let B(x) := ∑_{n=0}^{∞} b_{n+1}x^{n}.

Proposition 9. B(x) := (1 + \sqrt{2}x + x^{2} + \sqrt{2}x^{3} + x^{4})B(x^{3}).

Proof. Since b_{0} = 0, ∑ b_{n}x^{n} = x ∑ b_{n+1}x^{n} and thus

B(x) = ∑ b_{n+1}x^{n} = ∑ b_{3n+1}x^{3n} + ∑ b_{3n+2}x^{3n+1} + ∑ b_{3n+3}x^{3n+2}
= ∑(τb_{n} + b_{n+1})x^{3n} + ∑(b_{n} + τb_{n+1})x^{3n+1} + ∑ b_{n+1}x^{3n+2}
= τ ∑ b_{n}x^{3n} + ∑ b_{n+1}x^{3n} + x ∑ b_{n}x^{3n} + xτ ∑ b_{n+1}x^{3n} + x^{2} ∑ b_{n+1}x^{3n}
= (τx^{3} + 1 + x^{4} + xτ + x^{2}) ∑ b_{n+1}x^{3n}

and the proposition follows.

We let ⟨N_{1}, N_{2}, …, N_{n}⟩_{k} be 1 or 0 according to whether the integers N_{i} share no non-zero digits in their respective k-ary expansions or not. Northshield [9, Theorem 4.1] expressed Stern’s sequence (a_{n}) thus:

a_{n+1} = ∑_{a+2b=n}⟨a, b⟩_{2}.

We have an analogue of this theorem for (b_{n}):

Theorem 10. For n ≥ 0, b_{n+1} = ∑_{a+2b+3c+4d=n}⟨a, b, c, d⟩_{3} · (\sqrt{2})^{a+c}.

Proof. By the preceding proposition,

\begin{aligned}B(x) & = (1 + τx + x^{2} + τx^{3} + x^{4}) · (1 + τx^{3} + x^{6} + τx^{9} + x^{12}) \\ & · (1 + τx^{9} + x^{18} + τx^{27} + x^{36}) ⋯ \end{aligned}

and so B(x) can be written as a sum indexed by all choices of four integers with no ternary digits in common:

B(x) = ∑_{⟨a,b,c,d⟩_{3}=1} τ^{a+c}x^{a+2b+3c+4d}.

The result follows by equating coefficients.

Some immediate consequences are that, if n is even, then b_{n} is an integer multiple of τ; if n is odd then b_{n} is an odd integer.

The following leads to another closed formula for (b_{n}).

Lemma 11. 1 + \sqrt{2}x + x^{2} + \sqrt{2}x^{3} + x^{4} = (1 + \frac{1+\sqrt{3}}{\sqrt{2}}x + x^{2})(1 + \frac{1−\sqrt{3}}{\sqrt{2}}x + x^{2}).

Proof. Suppose 1+τx+x^{2} +τx^{3} +x^{4} = (1+ax+x^{2})(1+bx+x^{2}). Multiplying the right side out and equating coefficients, a+b = τ and 2+ab = 1. Then a, b are roots of x^{2} −τx−1 = 0 and the result follows.

Note that the zeros of 1 + τx + x^{2} + τx^{3} + x^{4} can easily be seen to be ζω, \overline{ζ}ω, ζ\overline{ω}, and \overline{ζ}\overline{ω} where ζ = e^{i5π/12} and ω = e^{i2π/3}.

Recall Binet’s formula for the nth Fibonacci number: for ϕ and \overline{ϕ} the zeros of x^{2} − x − 1,

F_{n} = \frac{ϕ^{n} − \overline{ϕ}^{n}}{ϕ − \overline{ϕ}} .

Alternatively, we may write

F_{n+1} = ∑_{k=0}^{n} ϕ^{k}\overline{ϕ}^{n−k}.

Northshield [9, Proposition 4.4] proved a Binet type formula for Stern’s sequence: for σ and \overline{σ} the zeros of x^{2} + x + 1 and s_{2}(n) the number of ones in the binary expansion of n,

a_{n+1} = ∑_{k=0}^{n} σ^{s_{2}(k)}\overline{σ}^{s_{2}(n−k)}.

The following is a Binet type formula for (b_{n}). Let s(n) denote the number of ones in the ternary representation of n (\underline{A062756} in [12]).

Theorem 12. For ρ and \overline{ρ} the zeros of x^{2} − \sqrt{2}x − 1 and s(n) the number of ones in the ternary representation of n,

b_{n+1} = ∑_{k=0}^{n} ρ^{s(k)}\overline{ρ}^{s(n−k)}.

Proof. The zeros of x^{2} − τx − 1 are (1 ± \sqrt{3})/τ. By Proposition 9 and Lemma 11,

\begin{aligned}B(x) & = ∏_{n=0}^{∞}(1 + τx^{3^{n}} + x^{2·3^{n}} + τx^{3·3^{n}} + x^{4·3^{n}}) \\ & = ∏_{n=0}^{∞}(1 + ax^{3^{n}} + x^{2·3^{n}}) · ∏_{n=0}^{∞}(1 + bx^{3^{n}} + x^{2·3^{n}}) \end{aligned}

where a = \frac{1 + \sqrt{3}}{τ} and b = \frac{1 − \sqrt{3}}{τ}. Since

∏_{n=0}^{∞}(1 + ax^{3^{n}} + x^{2·3^{n}}) = ∑_{k=0}^{∞} a^{s(k)}x^{k},

B(x) = (∑_{k=0}^{∞} a^{s(k)}x^{k}) (∑_{k=0}^{∞} b^{s(k)}x^{k}) = ∑_{n=0}^{∞} (∑_{k=0}^{n} a^{s(k)}b^{s(n−k)}) x^{n}.

Let (l_{n})_{n≥0} denote the generalized Lucas numbers 2, τ, 4, 5τ, 14, 19τ, 52, 71τ, … defined by

l_{0} = 2, l_{1} = τ, l_{n+1} = τl_{n} + l_{n−1}.

We note that (l_{2n})_{n≥0} is sequence \underline{A003500} in [12] and (l_{2n+1}/\sqrt{2})_{n≥0} is sequence \underline{A001834} in [12].

Corollary 13. b_{n+1} = \frac{1}{2} ∑_{k=0}^{n}(−1)^{s(k)∧s(n−k)}l_{|s(k)−s(n−k)|}.

Proof. It is easy to see that

∑_{k=0}^{n}(ab)^{s(k)∧s(n−k)}(a^{|s(k)−s(n−k)|} + b^{|s(k)−s(n−k)|}) = 2 ∑_{k=0}^{n} a^{s(k)}b^{s(n−k)}

holds generally for any a, b and any natural numbers s(k). For the choice a = (1 + \sqrt{3})/\sqrt{2} and b = (1 − \sqrt{3})/\sqrt{2}, ab = −1 and the result follows from Theorem 12.

5 Recurrence formulas

For a prime p, let ν_{p}(n) be the largest k so that p^{k} divides n. The sequences (ν_{2}(n)) and (ν_{3}(n)) appear as, respectively, \underline{A007814} and \underline{A007949} in [12].

Theorem 14. The sequence (b_{n}) satisfies, for n > 0,

b_{n+1} = (2ν_{3}(n) + 1)τb_{n} − b_{n−1}.

Proof. Let r_{n} := b_{n+1} + b_{n−1} − τb_{n}. Then

\begin{aligned}r_{3n+1} & = b_{3n+2} + b_{3n} − τb_{3n+1} = b_{n} + τb_{n+1} + b_{n} − τ(τb_{n} + b_{n+1}) \\ & = b_{n} + τb_{n+1} + b_{n} − 2b_{n} − τb_{n+1} = 0, \end{aligned}

\begin{aligned}r_{3n+2} & = b_{3n+3} + b_{3n+1} − τb_{3n+2} = b_{n+1} + τb_{n} + b_{n+1} − τ(b_{n} + τb_{n+1}) \\ & = 2b_{n+1} + τb_{n} − τb_{n} − 2b_{n+1} = 0, \end{aligned}

and

\begin{aligned}r_{3n} & = b_{3n+1} + b_{3n−1} − τb_{3n} = τb_{n} + b_{n+1} + b_{n−1} + τb_{n} − τb_{n} \\ & = b_{n+1} + b_{n−1} + τb_{n} = r_{n} + 2τb_{n}. \end{aligned}

By induction, r_{n} = 2τν_{3}(n)b_{n} and the result follows. Corollary 15. Let R_{n} := τ \frac{b_{n+1}}{b_{n}}. Then R_{1} = 2 and

R_{n} = 4ν_{3}(n) + 2 − \frac{2}{R_{n−1}} .

Remark 16. An analogue of this result works for Stern’s diatomic sequence (proof, using ν_{2}(n) = ⌊a_{n−1}/a_{n}⌋, is left to the reader): if r_{n} := a_{n+1}/a_{n}, then

r_{n} = 2ν_{2}(n) + 1 − \frac{1}{r_{n−1}} .

Lemma 17. For n > 0, ⌊\frac{1}{R_{n−1}} ⌋ = ν_{3}(n).

Proof. For n > 0, let Y_{n} := \frac{b_{n−1}}{τb_{n}} = \frac{1}{R_{n−1}} . Then

Y_{3n} = 1 + Y_{n}, Y_{3n+1} = \frac{b_{n}}{2b_{n} + τb_{n+1}} , and Y_{3n+2} = \frac{τb_{n} + b_{n+1}}{τb_{n} + 2b_{n+1}} .

Hence ⌊Y_{3n}⌋ = 1 + ⌊Y_{n}⌋, ⌊Y_{3n+1}⌋ = 0, and ⌊Y_{3n+2}⌋ = 0. Since Y_{1} = 0, the result follows by induction.

We may then get recurrences new for (R_{n}) and (b_{n}). Theorem 18. For n > 0,

R_{n+1} = 2 + \frac{2}{R_{n}} − 4 \{\frac{1}{R_{n}} \}

and

b_{n+1} = \sqrt{2}b_{n} + b_{n−1} − 2(b_{n−1} mod (\sqrt{2}b_{n})).

Proof. By Corollary 15 and Lemma 17,

\begin{aligned}R_{n} & = 4ν_{3}(n) + 2 − \frac{2}{R_{n−1}} = 4 ⌊\frac{1}{R_{n−1}} ⌋ + 2 − \frac{2}{R_{n−1}} \\ & = 2 + \frac{2}{R_{n−1}} + 4 (⌊\frac{1}{R_{n−1}} ⌋ − \frac{1}{R_{n−1}} ) = 2 + \frac{2}{R_{n−1}} − 4 \{\frac{1}{R_{n−1}} \} \end{aligned}

which shows the first part.

Using Corollary 15 again,

\frac{τb_{n+1}}{b_{n}} = 4ν_{3}(n) + 2 − \frac{2b_{n−1}}{τb_{n}} .

Multiplying by b_{n}/τ, we find

\begin{aligned}b_{n+1} & = 2τb_{n}ν_{3}(n) + τb_{n} − b_{n−1} \\ & = τb_{n} + b_{n−1} − 2(b_{n−1} − τb_{n}ν_{3}(n)) \end{aligned}

and the result follows from Lemma 17 and the fact that

b_{n−1} mod (τb_{n}) = b_{n−1} − τb_{n} ⌊\frac{b_{n−1}}{τb_{n}} ⌋ = b_{n−1} − τb_{n}ν_{3}(n).

6 Enumerating the rationals

Let D denote the set {k/3^{n} : k, n ∈ ℕ^{+}, k ≤ 3^{n}} of triadic rationals in the unit interval and consider the function f : D → ℚ(τ) defined by

f(k/3^{n}) := \frac{b_{k}}{b_{k} + b_{3^{n}−k}} .

This function is well-defined since

f(3k/3^{n+1}) = \frac{b_{3k}}{b_{3k} + b_{3^{n+1}−3k}} = \frac{b_{k}}{b_{k} + b_{3^{n}−k}} = f(k/3^{n}).

In this section, we find the image of the triadic rationals under the map f.

Let

B_{0} := (\begin{matrix}1 & τ \\ 0 & 1 \end{matrix}) , B_{1} := (\begin{matrix}τ & 1 \\ 1 & τ \end{matrix}) , B_{2} := (\begin{matrix}1 & 0 \\ τ & 1 \end{matrix}) and, for n ∈ ℤ^{+}, v_{n} := (\begin{matrix}b_{n+1} \\ b_{n} \end{matrix}) .

Then, for i = 0, 1, and 2,

B_{i}v_{n} = v_{3n+i}.

If m = ∑_{k=0}^{n} i_{k}3^{k} then

\begin{matrix}B_{i_{0}}B_{i_{1}} ⋯ B_{i_{n}}v_{0} = v_{m}; \\ B_{i_{0}}B_{i_{1}} ⋯ B_{i_{n}}v_{1} = v_{3^{n+1}+m}. \end{matrix}  (4)

Hence,

B_{i_{0}}B_{i_{1}} ⋯ B_{i_{n}}B_{0} = (\begin{matrix}b_{m+1} & b_{3^{n+1}+m+1} \\ b_{m} & b_{3^{n+1}+m} \end{matrix})  (5)

and so, since ^{t}B_{i} = B_{2−i} and ^{t}(A · B) =^{t}B ·^{t}A,

B_{2}B_{2−i_{n}}B_{2−i_{n−1}} ⋯ B_{2−i_{0}} = (\begin{matrix}b_{3^{n+1}+m} & b_{3^{n+1}+m+1} \\ b_{m} & b_{m+1} \end{matrix}) .  (6)

Since the determinant of each B_{i} is 1, by (5),

b_{k+1}b_{3^{n}−k} − b_{k}b_{3^{n}−k−1} = 1  (7)

which thus proves Proposition 3.

The following is an immediate consequence of (5) and (6).

Proposition 19. For natural numbers m, n satisfying m < 3^{n+1}, there exists k such that

(\begin{matrix}b_{3^{n+1}+m} \\ b_{m} \end{matrix}) = (\begin{matrix}b_{k+1} \\ b_{k} \end{matrix}) .

We define the slow Euclidean algorithm on ordered pairs of real numbers:

E : [x, y] ↦ \begin{cases}[x − τy, y], & if \frac{y}{x} ≤ \frac{1}{τ}; \\ [τx − y, τy − x], & if \frac{1}{τ} < \frac{y}{x} ≤ τ; \\ [x, y − τx], & if \frac{y}{x} > τ; \\ stop, & if xy = 0. \end{cases}

Proposition 20. For x, y ∈ ℤ[\sqrt{2}], E preserves greatest common divisor.

Proof. The determinant of each B_{i} is 1 and so B_{i} is invertible over ℤ[\sqrt{2}]. Hence, for p a prime in ℤ[\sqrt{2}], p| gcd(x, y) iff p| gcd(x−τy, y) iff p| gcd(x−τy, y−τx) iff p| gcd(x, y−τx).

Let L := \{[x, y] ∈ ℤ[\sqrt{2}]^{2} : x ⊥ y, τx/y ∈ ℚ, x, y ≥ 0\} where x ⊥ y means x and y are relatively prime in ℤ[\sqrt{2}].

Theorem 21. The set L satisfies L = {[b_{k}, b_{k+1}] : k ∈ ℤ^{+}}.

Proof. Let [x, y] ∈ L. Note that E([x, y]) ∈ L. By induction on the length of the ternary expansion of k, since [b_{0}, b_{1}] = [0, 1] ∈ L, every [b_{k}, b_{k+1}] ∈ L.

Suppose [x, y] ∈ L but is not equal to any [b_{k}, b_{k+1}]. Without loss of generality, we may assume that x + y is as small as possible. Let [u, v] = E([x, y]). Then [u, v] ∈ L and u + v < x + y. Then [u, v] = [b_{k}, b_{k+1}] for some k and therefore

[x, y] ∈ {[b_{3k}, b_{3k+1}], [b_{3k+1}, b_{3k+2}], [b_{3k+2}, b_{3k+3}]}

– a contradiction.

Using Proposition 19, Corollary 22. The sets \{\frac{b_{k}}{b_{3^{n}+k}} : k < 3^{n}\} and \{r\sqrt{2} : r ∈ ℚ\} are the same.

Corollary 23. The image of the triadic rationals in [0, 1] under f is the set

\{\frac{m}{m + (n − m)\sqrt{2}} : n > 0, m ≥ 0\} .

Proof. Since b_{3^{N} +k}/b_{k} = τn/m for some n, m, Proposition 2 implies b_{3^{N} −k}/b_{k} = τ(n − m)/m and so f(k/3^{N}) = m/(m + (n − m)τ).

Recall the sequence (R_{n})_{n≥1} defined by R_{n} := \sqrt{2}\frac{b_{n+1}}{b_{n}}. By Corollary 15, the sequence (R_{n}) is rational. The first few terms are, starting with n = 1,

2, 1, 4, 3/2, 2/3, 3, 4/3, 1/2, 6, 5/3, 4/5, 7/2, 10/7, 3/5, 8/3, 5/4, 2/5, 5, 8/5, 3/4, …

By Proposition 19 and Corollary 22, the range of R_{n} is all of the positive rationals and therefore, by Corollary 15,

Theorem 24. With R_{n} defined by

R_{1} = 2, R_{n} = 4ν_{3}(n) + 2 − \frac{2}{R_{n−1}} ,

the map n ↦ R_{n} is a bijection from ℤ^{+} to ℚ^{+}.

Remark 25. A version of Theorem 24 appeared as a problem in the American Mathematical Monthly [10].

The following is a consequence of Theorems 18 and 24.

Corollary 26. The iterates of 2 + \frac{2}{x} − 4 \{\frac{1}{x}\}, starting at 2, span the entire set of positive rational numbers.

This is similar, but not equivalent to, the fact [9, Theorem 5.2] that the iterates of 1 + \frac{1}{x} − 2 \{\frac{1}{x}\}, starting at 1, span the entire set of positive rational numbers.

“Negative continued fractions” have been studied by Eustis ([4]) and others, but to significantly lesser extent than regular continued fractions. They are of the form

(c_{0}, c_{1}, c_{2}, …) := c_{0} − \frac{1}{c_{1} − _{\frac{1}{c_{2}− \frac{1}{c_{3}−...}}}}

where c_{i} ∈ ℤ. Theorem 24 shows that every positive rational is a (finite) negative continued fraction of the form

R_{n} = 2u_{n} − \frac{2}{2u_{n−1} − _{\frac{2}{2u_{n−2}− \frac{2}{2u_{n−3}−...}}}} = (2u_{n}, u_{n−1}, 2u_{n−2}, u_{n−3}, …)

where u_{n} = 2ν_{3}(n) + 1.

Allouche and Shallit [1] introduced k-regular sequences; recall that a sequence (x_{n})_{n≥0} (in a ring) is 3-regular if there are finitely many sequences such that (x_{3^{i}n+j})_{n≥0} is a ℤ-linear combination of those sequences.

Proposition 27. The sequence (b_{n}) is 3-regular.

Proof. If n = ∑_{l=0}^{k} i_{l}3^{l} and j = ∑_{l=0}^{i−1} j_{l}3^{l} for some i ≥ 1, then

3^{i}n + j = ∑_{l=0}^{k} i_{l}3^{l+i} + ∑_{l=0}^{i−1} j_{l}3^{l}.

In terms of the matrices B_{j} and vectors v_{j} defined at the beginning of this section, and by equation (4),

v_{3^{i}n+j} = B_{j_{0}}B_{j_{1}} ⋯ B_{j_{i−1}}v_{n}

and so

b_{3^{i}n+j} = (0 1) · B_{j_{0}}B_{j_{1}} ⋯ B_{j_{i−1}}v_{n}.

That is, b_{3^{i}n+j} is ℤ-linear combination of b_{n} and b_{n+1}, the entries of v_{n}.

The sequence of rationals R_{n} := \frac{τb_{n+1}}{b_{n}} can be written in lowest terms as

\frac{2}{1}, \frac{1}{1}, \frac{4}{1}, \frac{3}{2}, \frac{2}{3}, \frac{3}{1}, \frac{4}{3}, \frac{1}{2}, \frac{6}{1}, \frac{5}{3}, \frac{4}{5}, \frac{7}{2}, \frac{10}{7}, \frac{3}{5}, \frac{8}{3}, \frac{5}{4}, \frac{2}{5}, \frac{5}{1}, \frac{8}{5}, \frac{3}{4}, …

The integer sequences that form the numerators and denominators are

2, 1, 4, 3, 2, 3, 4, 1, 6, 5, 4, 7, 10, 3, 8, 5, 2, 5, 8, 3, …

and

1, 1, 1, 2, 3, 1, 3, 2, 1, 3, 5, 2, 7, 5, 3, 4, 5, 1, 5, 4, …,

respectively.

We show that these sequences are 3-regular. First we shall define two integer sequences in terms of (b_{n}) and show that they are term-wise relatively prime and that their term-wise ratios correspond to R_{n} (and thus we will have formulas for the numerator and denominator sequences). From this, we show that these two sequences are also 3-regular since each is a product of (b_{n}) with another 3-regular sequence.

Recall that two numbers x, y in a Euclidean domain E = ℤ or ℤ[\sqrt{2}] are relatively prime (we write x ⊥ y) if and only if there exist u, v ∈ E such that ux + vy = 1. If x ⊥ y and |ad − bc| = 1 then ax + by ⊥ cx + dy (since the matrix ( \begin{matrix}a & b \\ c & d \end{matrix}) is invertible over E).

By the recurrence (1), if b_{n} ⊥ b_{n+1} then b_{3n} ⊥ b_{3n+1}, b_{3n+1} ⊥ b_{3n+2}, and b_{3n+2} ⊥ b_{3n+3}. An induction argument shows that b_{n} ⊥ b_{n+1} over ℤ[\sqrt{2}] for all n. Recall that, by Theorem 10, b_{2n+1} is an odd integer for each n and that b_{2n} is an integer multiple of τ for each n. Let

γ(n) = \begin{cases}1, & if n is odd; \\ τ, & if n is even. \end{cases}

We then define D(n) := b_{n}/γ(n), and N(n) := γ(n+1)b_{n+1}. Then (D(n))_{n≥0} and (N(n))_{n≥0} are integer sequences and, for all n, D(n) ⊥ N(n). Note that N(n)/D(n) = τb_{n+1}/b_{n} and, therefore, (N(n)) and (D(n)) are the numerator and denominator sequences of (R_{n}).

Since γ(3^{i}n + j) = γ(n) or γ(n + 1) according to whether j is even or odd, respectively, the sequence (γ(n))_{n≥0} is 3-regular. Since the product of 3-regular sequences is 3-regular, the sequences (N(n))_{n≥0} and (D(n))_{n≥0} are 3-regular.

7 A singular function

Let d_{n,k} := b_{k} + b_{3^{n}−k} so that f (\frac{k}{3^{n}} ) = \frac{b_{k}}{d_{n,k}} .

Lemma 28. For 0 ≤ k < 3^{n}, d_{n,k}d_{n,k+1} ≥ n + 1.

Proof. Note that

d_{n+1,3k} = d_{n,k}
d_{n+1,3k+1} = τd_{n,k} + d_{n,k+1}
d_{n+1,3k+2} = d_{n,k} + τd_{n,k+1}.

Then

d_{n+1,3k}d_{n+1,3k+1} = τd_{n,k}^{2} + d_{n,k}d_{n,k+1} ≥ d_{n,k}d_{n,k+1} + 1,

\begin{aligned}d_{n+1,3k+1}d_{n+1,3k+2} & = (τd_{n,k} + d_{n,k+1})(d_{n,k} + τd_{n,k+1}) \\ & = 3d_{n,k}d_{n,k+1} + τ(d_{n,k}^{2} + d_{n,k+1}^{2}) ≥ d_{n,k}d_{n,k+1} + 1, \end{aligned}

and

\begin{aligned}d_{n+1,3k+2}d_{n+1,3k+3} & = (d_{n,k} + τd_{n,k+1})d_{n,k+1} \\ & = d_{n,k}d_{n,k+1} + τd_{n,k+1}^{2} ≥ d_{n,k}d_{n,k+1} + 1. \end{aligned}

Hence, for 0 ≤ j < 3^{n+1}, d_{n+1,j}d_{n+1,j+1} ≥ d_{n,⌊j/3⌋}d_{n,⌊j/3⌋+1} + 1 and so the lemma follows by induction.

Theorem 29. The function f (\frac{k}{3^{n}} ) := \frac{b_{k}}{b_{k}+b_{3^{n}−k}} on the triadic rationals in [0, 1] extends to a continuous and strictly increasing function on [0, 1].

Proof. By Lemma 28 and Proposition 3 (equation (7)),

\begin{aligned}f (\frac{k + 1}{3^{n}}) & − f (\frac{k}{3^{n}} ) = \frac{b_{k+1}}{d_{n,k+1}} − \frac{b_{k}}{d_{n,k}} \\ & = \frac{b_{k+1}b_{3^{n}−k} − b_{k}b_{3^{n}−k−1}}{d_{n,k}d_{n,k+1}} = \frac{1}{d_{n,k}d_{n,k+1}} ∈ (0, \frac{1}{n}) . \end{aligned}

The result follows.

Recall the notation for continued fractions [6]: for positive integers c_{1}, c_{2}, c_{3}, …,

[0; c_{1}, c_{2}, c_{3}, …] := 1/(c_{1} + 1/(c_{2} + 1/(c_{3} + ⋯))).

Every irrational positive number between 0 and 1 can be written uniquely in that form (rational numbers have non-unique finite expansions).

In 1904, Minkowski introduced a singular function (continuous and strictly increasing with derivative existing and 0 almost everywhere) ? : [0, 1] → [0, 1]. Its value at x is defined in terms of the continued fraction expansion of x: If x = [0, c_{1}, c_{2}, …] then

?(x) := ∑_{k≥1} \frac{(−1)^{k+1}}{2^{c_{1}+···+c_{k}−1}} .  (8)

One of the question mark function’s most interesting properties is that it maps quadratic surds to rational numbers (since the sequence c_{1}, c_{2}, … is eventually periodic precisely when x is a quadratic surd). The inverse of ?(x) is known as Conway’s box function [11, p. 82] and it is known by, for example, Northshield [9, Theorem 6.2], that Stern’s sequence is related to it:

?^{−1} (\frac{k}{2^{n}} ) = \frac{a_{k}}{a_{k} + a_{2^{n}−k}} .

Figure 3: The graphs of f(x) and its inverse.

For convenience, we define a function on the triadic rationals D:

g (\frac{k}{3^{n}} ) := \frac{b_{k}}{b_{3^{n}+k}} .

The functions f and g are closely related: by Proposition 2,

\frac{b_{3^{n}+k}}{b_{k}} = \frac{b_{3^{n}−k} + \sqrt{2}b_{k}}{b_{k}} = \frac{b_{3^{n}−k} + b_{k}}{b_{k}} + \sqrt{2} − 1

and therefore

g (\frac{k}{3^{n}} ) = \frac{1}{\frac{1}{f(k/3^{n})} + \sqrt{2} − 1} and f (\frac{k}{3^{n}} ) = \frac{1}{\frac{1}{g(k/3^{n})} + 1 − \sqrt{2}}.  (9)

By Theorem 7 and equation (9), g extends to a continuous, strictly increasing function on [0, 1].

Lemma 30. For 0 ≤ x < 3, g (\frac{3 − x}{3^{n}}) = \frac{1}{n\sqrt{2} + g(x)}.

Proof. Let k < 3^{m+1}. By Propositions 1 and 2,

b_{3^{m+2}−k} = b_{3^{m+1}−k} + τb_{k}.

By an induction argument,

b_{3^{n+m+1}−k} = b_{3^{m+1}−k} + nτb_{k}.

Replacing k by 3^{m+1} − k, and using Proposition 1,

b_{3^{n+m}+3^{m+1}−k} = b_{k} + nτb_{3^{m+1}−k}.

Hence,

g (\frac{3^{m+1} − k}{3^{n+m}} ) = \frac{b_{3^{m+1}−k}}{b_{3^{m+n}+3^{m+1}−k}} = \frac{b_{3^{m}+k}}{b_{k} + nτb_{3^{m}+k}} = \frac{1}{nτ + g(k/3^{m})}.

Letting k/3^{m} → x, the result follows.

Consider now continued fractions [0; c_{1}\sqrt{2}, c_{2}\sqrt{2}, c_{3}\sqrt{2}, …]. By Lemma 30,

g^{−1} (\frac{1}{n\sqrt{2} + x}) = \frac{3 − g^{−1}(x)}{3^{n}}

and thus

g^{−1}([0, c_{1}\sqrt{2}, c_{2}\sqrt{2}, c_{3}\sqrt{2}, …]) = \frac{3 − g^{−1}([0, c_{2}\sqrt{2}, c_{3}\sqrt{2}, c_{4}\sqrt{2}, …])}{3^{c_{1}}}.

An induction argument shows the following.

Figure 4: Homeomorphic fractals

Theorem 31. For c_{1}, c_{2}, … ∈ ℤ^{+},

g^{−1}([0, c_{1}\sqrt{2}, c_{2}\sqrt{2}, c_{3}\sqrt{2}, …]) = ∑_{k} \frac{(−1)^{k+1}}{3^{c_{1}+...+c_{k}−1}} .

Figure 4 gives a geometric way of viewing our analogue of Minkowski’s ?–function. We consider each of the two objects to be lying in the complex plane with bottom edge coinciding with the unit interval. Clearly they are homeomorphic and there is a unique homeomorphism from the figure on the left to that on the right which takes the unit interval to itself and fixes its endpoints. The restriction of this homeomorphism to the unit interval can be shown to be f(x).

8 Future directions

The contact graph of a set of circles (with non-intersecting interiors) is the graph with that vertex set such that we place an edge between two vertices if and only if the circles are tangent. Ford circles are formed by iteratively completing triangles in a contact graph by adding a new vertex (so as to form a graph tetrahedron out of the triangle). If we consider this process “tetrahedral”, then the process generating the variant Ford circles of Section 3 is “octahedral”. It then seems that any polyhedron with triangular faces could be used to generate a new set of circles and, thus, a new sequence of (presumably) algebraic integers.

At the end of Section 4, generalized Lucas numbers (a^{n} +b^{n}) were defined. This sequence displayed a type of combinatorial reciprocity [2]: the even terms and the odd terms (divided by τ) are sequences of positive integers (\underline{A003500} and \underline{A001834} in [12] respectively) that are known to count various sets of objects. One can consider generalized Fibonacci numbers (a^{n} − b^{n})/(a − b) as well and investigate its even and odd terms. At the end of Section 6, the sequences of numerators and denominators of R_{n} were considered. What do these sequences count? Further, is there some kind of combinatorial reciprocity [2] occurring here?

The three term recurrence of Theorem 14 is reminiscent of the type of recurrence that defines orthogonal polynomials. What are the polynomials generated by that recurrence (with τ as variable)? What measure makes them orthogonal?

In Section 6, we have seen sequences satisfying

r_{1} = 1, r_{n} = 2ν_{2}(n) + 1 − \frac{1}{r_{n−1}}

and

R_{1} = 2, R_{n} = 4ν_{3}(n) + 2 − \frac{2}{r_{n−1}} .

How does this generalize?

9 Appendix

The following is Maple code for a function b where b_{n} = b(n).

b := proc (n);
if  $n\le 1$ then n
elif n mod 3 = 0 then b(n/3)
elif n mod 3 = 1 then sqrt(2)*b((n-1)/3)+b((n+2)/3)
else b((n-2)/3)+sqrt(2)*b((n+1)/3); fi;
end proc;

Output for n = 0..100:

0, 1, \sqrt{2}, 1, 2\sqrt{2}, 3, \sqrt{2}, 3, 2\sqrt{2}, 1, 3\sqrt{2}, 5, 2\sqrt{2}, 7, 5\sqrt{2}, 3, 4\sqrt{2}, 5, \sqrt{2}, 5, 4\sqrt{2}, 3, 5\sqrt{2},

7, 2\sqrt{2}, 5, 3\sqrt{2}, 1, 4\sqrt{2}, 7, 3\sqrt{2}, 11, 8\sqrt{2}, 5, 7\sqrt{2}, 9, 2\sqrt{2}, 11, 9\sqrt{2}, 7, 12\sqrt{2}, 17, 5\sqrt{2}, 13,

8\sqrt{2}, 3, 7\sqrt{2}, 11, 4\sqrt{2}, 13, 9\sqrt{2}, 5, 6\sqrt{2}, 7, \sqrt{2}, 7, 6\sqrt{2}, 5, 9\sqrt{2}, 13, 4\sqrt{2}, 11, 7\sqrt{2}, 3, 8\sqrt{2},

13, 5\sqrt{2}, 17, 12\sqrt{2}, 7, 9\sqrt{2}, 11, 2\sqrt{2}, 9, 7\sqrt{2}, 5, 8\sqrt{2}, 11, 3\sqrt{2}, 7, 4\sqrt{2}, 1, 5\sqrt{2}, 9, 4\sqrt{2},

15, 11\sqrt{2}, 7, 10\sqrt{2}, 13, 3\sqrt{2}, 17, 14\sqrt{2}, 11, 19\sqrt{2}, 27, 8\sqrt{2}, 21, 13\sqrt{2}, 5, 12\sqrt{2}.

References

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

[2] M. Beck, Combinatorial reciprocity theorems, Jahresber. Dtsch. Math.-Ver. 114 (2012), 3–22.

[3] M. Coons and J. Tyler, The maximal order of Stern’s diatomic sequence, Mosc. J. Comb. Number Theory 4 (2014), 3–14.

[4] A. Eustis, The negs and regs of continued fractions, senior thesis, Harvey Mudd College, 2006. Available at

    https://www.math.hmc.edu/seniorthesis/archives/2006/aeustis/aeustis-2006-thesis.pdf.

[5] G. Guettler and C. Mallows, A generalization of Apollonian packing of circles, J. Comb. 1 (2010), 1–27.

[6] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, fifth edition. Oxford University Press, 1979.

[7] T. Needham, Visual Complex Analysis, Oxford University Press, 2000.

[8] S. Northshield, Ford circles and spheres, preprint, 2015. Available at

    http://arxiv.org/abs/1503.00813.

[9] S. Northshield, Stern’s diatomic sequence 0, 1, 1, 2, 1, 3, 2, 3, 2, 1, 4, …, Amer. Math. Monthly 117 (2010), 581–598.

[10] S. Northshield, Problem 11852, Amer. Math. Monthly 122 (2015), 700.

[11] J. Paradis, P. Viader, and L. Bibiloni, The derivative of Minkowski’s ?(x) Function, J. Math. Anal. Appl. 253 (2001) 107–125.

[12] N. J. A. Sloane, ed., The On-Line Encyclopedia of Integer Sequences, http://oeis.org.

2010 Mathematics Subject Classification: Primary 11B83; Secondary 05A15, 05B40, 11A55, 11B37, 11B39, 40A15, 52C26. Keywords: continued fraction, recurrence, generating function, circle packing, Fibonacci number.

(Concerned with sequences \underline{A001834}, \underline{A002487}, \underline{A003500}, \underline{A007814}, \underline{A007949}, \underline{A011900}, \underline{A046090}, and \underline{A062756}.)

Received March 17 2015; revised versions received December 7 2015; December 13 2015. Published in Journal of Integer Sequences, December 15 2015.

Return to Journal of Integer Sequences home page.