Unisequences and Nearest Integer Continued Fraction Midpoint Criteria for Pell’s Equation

Keith R. Matthews Department of Mathematics University of Queensland Brisbane 4072 Australia and Centre for Mathematics and its Applications Australian National University Canberra ACT 0200 Australia

                  keithmatt@gmail.com

Abstract

The nearest integer continued fractions of Hurwitz, Minnegerode (NICF-H) and in Perron’s book Die Lehre von den Kettenbrüchen (NICF-P) are closely related. Midpoint criteria for solving Pell’s equation x^{2} − Dy^{2} = ±1 in terms of the NICF-H expansion of \sqrt{D} were derived by H. C. Williams using singular continued fractions. We derive these criteria without the use of singular continued fractions. We use an algorithm for converting the regular continued fraction expansion of \sqrt{D} to its NICF-P expansion.

1 Introduction

In Perron’s book [7, p. 143], a nearest integer continued fraction (Kettenbruch nach nächsten Ganzen) expansion (NICF-P) of an irrational number ξ_{0} is defined recursively by

ξ_{n} = q_{n} + \frac{ϵ_{n+1}}{ξ_{n+1}} , −\frac{1}{2} < ξ_{n} − q_{n} < \frac{1}{2},  (1)

where ϵ_{n+1} = ±1, q_{n} is an integer (the nearest integer to ξ_{n}) and sign(ϵ_{n+1}) = sign(ξ_{n} − q_{n}). Then we have the expansion

ξ_{0} = q_{0} + \frac{ϵ_{1}}{q_{1}} + ⋯ + \frac{ϵ_{n}}{q_{n}} + ⋯  (2)

where

q_{n} ≥ 2, q_{n} + ϵ_{n+1} ≥ 2 for n ≥ 1.  (3)

(Satz 10, [7, p. 169]).

A. Hurwitz [1] and B. Minnegerode [6] defined a related nearest integer continued fraction (NICF-H) by

ξ′_{n} = q′_{n} − \frac{1}{ξ′_{n+1}} , −\frac{1}{2} < ξ′_{n} − q′_{n} < \frac{1}{2},  (4)

where q′_{n} is an integer. Then

ξ′_{0} = q′_{0} − \frac{1}{q′_{1}} − ⋯ − \frac{1}{q′_{n}} − ⋯  (5)

and we have |q′_{n}| ≥ 2 for n ≥ 1. Also if one of q′_{1}, q′_{2}, …, say q′_{n}, equals 2 (resp. −2), then q′_{n+1} < 0 (resp. q′_{n+1} > 0) (Hurwitz [1, p. 372]). Section 2 relates the two types of continued fraction.

In 1980, H. C. Williams gave six midpoint criteria for solving Pell’s equation x^{2} − Dy^{2} = ±1 in terms of the NICF-H expansion of \sqrt{D} (see Theorems 6 and 7, [9, pp. 12–13]). His proof made extensive use of the singular continued fraction expansion of \sqrt{D}. Theorem 6 of section 3 of our paper gives the corresponding criteria for the NICF-P expansion of \sqrt{D}. In an attempt to give a derivation of the latter criteria without the use of singular continued fractions, the author studied the conversion of the regular continued fraction (RCF) expansion of \sqrt{D} to the NICF given by Lemma 9 of section 5, where the RCF is defined recursively by

ξ_{n} = a_{n} + \frac{1}{ξ_{n+1}} ,

with a_{n} = ⌊ξ_{n}⌋, the integer part of ξ_{n}. Theorem 8 of section 4 shows that the central part of a least period determines which of the criteria hold. Finally, Theorem 18, section 7, describes the case where there are only odd-length unisequences, i.e., consecutive sequences of partial quotients equal to 1, in the RCF expansion of \sqrt{D}; in this case the NICF-P expansion of \sqrt{D} exhibits the usual symmetry properties of the RCF expansion.

2 Connections between the NICF-H and NICF-P expansions of an irrational number.

Lemma 1. Let q′_{n}, ξ′_{n}, A′_{n}/B′_{n} denote the n-th partial denominator, complete quotient and convergent of the NICF-H expansion of an irrational number ξ_{0} and q_{n}, ϵ_{n}, ξ_{n}, A_{n}/B_{n} denote the n-th partial denominator, partial numerator, complete quotient and convergent of the NICF-P expansion of ξ_{0}, where

A_{−1} = 1 = A′_{−1}, B_{−1} = 0 = B′_{−1},
A_{−2} = 0 = A′_{−2}, B_{−2} = 1 = −B′_{−2}.

and for n ≥ −1,

A_{n+1} = q_{n+1}A_{n} + ϵ_{n+1}A_{n−1}, B_{n+1} = q_{n+1}B_{n} + ϵ_{n+1}B_{n−1}
A′_{n+1} = q′_{n+1}A′_{n} − A′_{n−1}, B′_{n+1} = q′_{n+1}B′_{n} − B′_{n−1},

where ϵ_{0} = 1. Then

q′_{n} = t_{n}q_{n}, ξ′_{n} = t_{n}ξ_{n}, n ≥ 0,  (6)

where t_{0} = 1 and t_{n} = (−1)^{n}ϵ_{1} ⋯ ϵ_{n}, if n ≥ 1.

A′_{n} = s_{n}A_{n}, B′_{n} = s_{n}B_{n}, n ≥ −2,  (7)

where s_{−2} = −1, s_{−1} = 1 and s_{n+1} = −s_{n−1}ϵ_{n+1} for n ≥ −1.

Remark 2. It follows that s_{0} = 1 and

s_{2i} = (−1)^{i}ϵ_{2i}ϵ_{2i−2} ⋯ ϵ_{2}, if i ≥ 1,  (8)
s_{2i+1} = (−1)^{i+1}ϵ_{2i+1}ϵ_{2i−1} ⋯ ϵ_{1}, if i ≥ 0,  (9)
s_{n+1}s_{n} = t_{n+1}, if n ≥ −1.  (10)

Proof. We prove (6) by induction on n ≥ 0. These are true when n = 0. So we assume that n ≥ 0 and (6) hold. Then

ξ′_{n+1} = \frac{1}{q′_{n} − ξ′_{n}} , ξ_{n+1} = \frac{ϵ_{n+1}}{q_{n} − ξ_{n}} ,  (11)
q′_{n} = [ξ′_{n}], q_{n} = [ξ_{n}],  (12)

where [x] denotes the nearest integer to x. Then

ξ′_{n+1} = \frac{1}{t_{n}q_{n} − t_{n}ξ_{n}}

= \frac{t_{n}}{q_{n} − ξ_{n}} = t_{n}(−ϵ_{n+1}ξ_{n+1})

= t_{n+1}ξ_{n+1}.

Next,

q′_{n+1} = [ξ′_{n+1}] = [t_{n+1}ξ_{n+1}] = t_{n+1}[ξ_{n+1}] = t_{n+1}q_{n+1}.

Finally, we prove (7) by induction on n ≥ −2. These hold for n = −2 and −1. So we assume n ≥ −1 and

A′_{n−1} = s_{n−1}A_{n−1}, B′_{n−1} = s_{n−1}B_{n−1}, A′_{n} = s_{n}A_{n}, B′_{n} = s_{n}B_{n}.

Then

A′_{n+1} = q′_{n+1}A′_{n} − A′_{n−1}
= (t_{n+1}q_{n+1})(s_{n}A_{n}) − s_{n−1}A_{n−1}
= q_{n+1}s_{n+1}A_{n} − (−s_{n+1}ϵ_{n+1})A_{n−1}
= s_{n+1}(q_{n+1}A_{n} + ϵ_{n+1}A_{n−1})
= s_{n+1}A_{n+1}.

Similarly B′_{n+1} = s_{n+1}B_{n+1}.

Corollary 3. Suppose ξ_{n}, …, ξ_{n+k−1} is a least period of NICF-P complete quotients for a quadratic irrational ξ_{0}.

(a) If ϵ_{n+1} ⋯ ϵ_{n+k} = (−1)^{k}, then

ξ′_{n}, …, ξ′_{n+k−1}

is a least period of NICF-H complete quotients for ξ_{0}.

(b) If ϵ_{n+1} ⋯ ϵ_{n+k} = (−1)^{k+1}, then

ξ′_{n}, …, ξ′_{n+k−1}, −ξ′_{n}, …, −ξ′_{n+k−1}  (13)

is a least period of NICF-H complete quotients for ξ_{0}. Moreover

ξ_{0} = q′_{0} − \frac{1}{q′_{1}} − ⋯ − \frac{1}{q′_{n}_{∗}} − ⋯ − \frac{1}{q′_{n+k−1}} − \frac{1}{−q′_{n}} − ⋯ − \frac{1}{−q′_{n+k−1}_{∗}} ,

where the asterisks correspond to the least period (13).

Proof. Suppose ξ_{n}, …, ξ_{n+k−1} is a least period of NICF-P complete quotients for ξ_{0}. Then ξ_{n} = ξ_{n+k}. Hence from (6),

t_{n}ξ′_{n} = t_{n+k}ξ′_{n+k}
(−1)^{n}ϵ_{1} ⋯ ϵ_{n}ξ′_{n} = (−1)^{n+k}ϵ_{1} ⋯ ϵ_{n+k}ξ′_{n+k}
ξ′_{n} = (−1)^{k}ϵ_{n+1} ⋯ ϵ_{n+k}ξ′_{n+k}.  (14)

(a) Suppose ϵ_{n+1} ⋯ ϵ_{n+k} = (−1)^{k}. Then (14) gives

ξ′_{n} = ξ′_{n+k}.

Then because ξ′_{n}, …, ξ′_{n+k−1} are distinct, they form a least period of complete quotients for the NICF-H expansion of ξ_{0}.

(b) Suppose ϵ_{n+1} ⋯ ϵ_{n+k} = (−1)^{k+1}. Then (14) gives

ξ′_{n} = −ξ′_{n+k}.

Similarly

ξ′_{n+1} = −ξ′_{n+k+1}, …, ξ′_{n+k−1} = −ξ′_{n+2k−1}.

Also ξ′_{n} = −ξ′_{n+k} = −(−ξ′_{n+2k}) = ξ′_{n+2k}. Hence

ξ′_{n}, …, ξ′_{n+k−1}, ξ′_{n+k}, …, ξ′_{n+2k−1}  (15)

form a period of complete quotients for the NICF-H expansion of ξ_{0}. However sequence (15) is identical with

ξ′_{n}, …, ξ′_{n+k−1}, −ξ′_{n}, …, −ξ′_{n+k−1},

whose members are distinct. Hence (15) form a least period of complete quotients for the NICF-H expansion of ξ_{0}.

Corollary 4. Let k and p be the period-lengths of the NICF-P and RCF expansions of a quadratic irrational ξ_{0} not equivalent to (1 + \sqrt{5})/2. Then

(a) if p is even, the period-length of the NICF-H expansion of ξ_{0} is equal to k;

(b) if p is odd, the period-length of the NICF-H expansion of ξ_{0} is equal to 2k and the NICF-H expansion has the form

ξ_{0} = q′_{0} − \frac{1}{q′_{1}} − ⋯ − \frac{1}{q′_{n}_{∗}} − ⋯ − \frac{1}{q′_{n+k−1}} − \frac{1}{−q′_{n}} − ⋯ − \frac{1}{−q′_{n+k−1}_{∗}} .

Proof. Let ξ_{n}, …, ξ_{n+k−1} be a least period of NICF-P complete quotients. Suppose that r of the partial numerators ϵ_{n+1}, …, ϵ_{n+k} of the NICF-P expansion of ξ_{0} are equal to −1. Now by Theorem 4 of Matthews and Robertson [5], p = k + r and hence

ϵ_{n+1} ⋯ ϵ_{n+k} = (−1)^{r} = (−1)^{k+p}.

Then according as p is even or odd, ϵ_{n+1} ⋯ ϵ_{n+k} = (−1)^{k} or (−1)^{k+1} and Corollary 3 applies.

Remark 5. This result was obtained by Hurwitz and Minnegerode for the special case ξ_{0} = \sqrt{D}.

We give some examples.

(1) ξ_{0} = (12 + \sqrt{1792})/16, (Tables 1 and 2). Here k = 4, r = 2, ξ_{1}, ξ_{2}, ξ_{3}, ξ_{4} form a period of NICF-P complete quotients, ϵ_{2}ϵ_{3}ϵ_{4}ϵ_{5} = (−1)(1)(−1)(1) = 1 = (−1)^{k} and the NICF-P and NICF-H expansions have the same period-length. Also p = 6.

(2) ξ_{0} = (5 + \sqrt{13})/4, (Table 3 and 4). Here k = 3, r = 2 and ξ_{0}, ξ_{1}, ξ_{2} form a period of NICF-P complete quotients, ϵ_{1}ϵ_{2}ϵ_{3} = (1)(−1)(−1) = 1 = (−1)^{k+1} and the NICF-H period-length is twice the NICF-P period-length. Also p = 5.

Table 1: NICF-P expansion for (12 + \sqrt{1792})/16

\begin{matrix}i & ξ_{i} & ϵ_{i} & b_{i} & A_{i}/B_{i} \\ 0 & \frac{12+\sqrt{1792}}{16} & 1 & 3 & 3/1 \\ 1 & \frac{36+\sqrt{1792}}{31} & 1 & 3 & 10/3 \\ 2 & \frac{57+\sqrt{1792}}{47} & −1 & 2 & 17/5 \\ 3 & \frac{37+\sqrt{1792}}{9} & 1 & 9 & 163/48 \\ 4 & \frac{44+\sqrt{1792}}{16} & −1 & 5 & 798/235 \\ 5 & \frac{36+\sqrt{1792}}{31} & 1 & 3 & 2557/753 \end{matrix}

Table 2: NICF-H expansion for (12 + \sqrt{1792})/16

\begin{matrix}i & ξ_{i} & ϵ_{i} & b_{i} & A_{i}/B_{i} \\ 0 & \frac{12+\sqrt{1792}}{16} & −1 & 3 & 3/1 \\ 1 & \frac{36+\sqrt{1792}}{−31} & −1 & −3 & −10/−3 \\ 2 & \frac{57+\sqrt{1792}}{−47} & −1 & −2 & 17/5 \\ 3 & \frac{37+\sqrt{1792}}{9} & −1 & 9 & 163/48 \\ 4 & \frac{44+\sqrt{1792}}{16} & −1 & 5 & 798/235 \\ 5 & \frac{36+\sqrt{1792}}{−31} & −1 & −3 & −2557/−753 \end{matrix}

3 NICF-P midpoint criteria for Pell’s equation

Theorem 6. Let k and p be the respective period-lengths of NICF-P and RCF expansions of \sqrt{D}. Then precisely one of the following must hold for the NICF-P expansion of \sqrt{D}:

1) P_{ρ} = P_{ρ+1}, k = 2ρ, p = 2h. Then

A_{k−1} = B_{ρ−1}A_{ρ} + ϵ_{ρ}A_{ρ−1}B_{ρ−2},
B_{k−1} = B_{ρ−1}(B_{ρ} + ϵ_{ρ}B_{ρ−2}).

2) P_{ρ+1} = P_{ρ} + Q_{ρ}, k = 2ρ, p = 2h. Then

A_{k−1} = B_{ρ−1}A_{ρ} + A_{ρ−1}B_{ρ−2} − A_{ρ−1}B_{ρ−1},
B_{k−1} = B_{ρ−1}(B_{ρ} + B_{ρ−2} − B_{ρ−1}).

3) Q_{ρ} = Q_{ρ+1} and

(a) ϵ_{ρ+1} = −1, k = 2ρ + 1, p = 2h, or
(b) ϵ_{ρ+1} = 1, k = 2ρ + 1, p = 2h − 1.

Then

A_{k−1} = A_{ρ}B_{ρ} + ϵ_{ρ+1}A_{ρ−1}B_{ρ−1},
B_{k−1} = B_{ρ}^{2} + ϵ_{ρ+1}B_{ρ−1}^{2}.

Table 3: NICF-P expansion for (5 + \sqrt{13})/4

\begin{matrix}i & ξ_{i} & ϵ_{i} & b_{i} & A_{i}/B_{i} \\ 0 & \frac{5+\sqrt{13}}{4} & 1 & 2 & 2/1 \\ 1 & \frac{3+\sqrt{13}}{1} & 1 & 7 & 15/7 \\ 2 & \frac{4+\sqrt{13}}{3} & −1 & 3 & 43/20 \\ 3 & \frac{5+\sqrt{13}}{4} & −1 & 2 & 71/33 \end{matrix}

Table 4: NICF-H expansion for (5 + \sqrt{13})/4

\begin{matrix}i & ξ_{i} & ϵ_{i} & b_{i} & A_{i}/B_{i} \\ 0 & \frac{5+\sqrt{13}}{4} & 1 & 2 & 2/1 \\ 1 & \frac{3+\sqrt{13}}{−1} & −1 & −7 & −15/−7 \\ 2 & \frac{4+\sqrt{13}}{−3} & −1 & −3 & 43/20 \\ 3 & \frac{5+\sqrt{13}}{−4} & −1 & −2 & −71/−33 \\ 4 & \frac{3+\sqrt{13}}{1} & −1 & 7 & −540/−251 \\ 5 & \frac{4+\sqrt{13}}{3} & −1 & 3 & −1549/−720 \\ 6 & \frac{5+\sqrt{13}}{4} & −1 & 2 & −2558/−1189 \end{matrix}

4) P_{ρ+1} = Q_{ρ} + \frac{1}{2}Q_{ρ+1}, ϵ_{ρ+1} = −1, k = 2ρ + 1, p = 2h − 1. Then

A_{k−1} = A_{ρ}B_{ρ} + 2A_{ρ−1}B_{ρ−1} − (A_{ρ}B_{ρ−1} + B_{ρ}A_{ρ−1}),
B_{k−1} = B_{ρ}^{2} + 2B_{ρ−1}^{2} − 2B_{ρ}B_{ρ−1}.

5) P_{ρ} = Q_{ρ} + \frac{1}{2}Q_{ρ−1}, ϵ_{ρ} = −1, k = 2ρ, p = 2h − 1. Then

A_{k−1} = 2A_{ρ−1}B_{ρ−1} + A_{ρ−2}B_{ρ−2} − (A_{ρ−1}B_{ρ−2} + B_{ρ−1}A_{ρ−2})
B_{k−1} = 2B_{ρ−1}^{2} + B_{ρ−2}^{2} − 2B_{ρ−1}B_{ρ−2}.

Proof. We only exhibit the calculations for criterion 1) of Theorem 6. This corresponds to criterion 1) of Theorem 6, Williams [9, p. 12], which states that P′_{ρ} = P′_{ρ+1}, k = 2ρ, p = 2h and

|A′_{k−1}| = |B′_{ρ−1}A′_{ρ} − A′_{ρ−1}B′_{ρ−2}|,  (16)
|B′_{k−1}| = |B′_{ρ−1}(B′_{ρ} − B′_{ρ−2})|.  (17)

Then from equations (7),

B′_{ρ−1}A′_{ρ} − A′_{ρ−1}B′_{ρ−2} = s_{ρ−1}s_{ρ}B_{ρ−1}A_{ρ} − s_{ρ−1}s_{ρ−2}A_{ρ−1}B_{ρ−2}
= t_{ρ}B_{ρ−1}A_{ρ} − t_{ρ−1}A_{ρ−1}B_{ρ−2}
= −t_{ρ−1}ϵ_{ρ}B_{ρ−1}A_{ρ} − t_{ρ−1}A_{ρ−1}B_{ρ−2}
= −t_{ρ−1}ϵ_{ρ}(B_{ρ−1}A_{ρ} + ϵ_{ρ}A_{ρ−1}B_{ρ−2}).

Hence

|B′_{ρ−1}A′_{ρ} − A′_{ρ−1}B′_{ρ−2}| = B_{ρ−1}A_{ρ} + ϵ_{ρ}A_{ρ−1}B_{ρ−2}  (18)

as B_{ρ−1}A_{ρ} ≥ A_{ρ−1}B_{ρ−2}. Hence (16) and (18) give the first result of criterion 1) above. Next,

B′_{ρ−1}(B′_{ρ} − B′_{ρ−2}) = s_{ρ−1}B_{ρ−1}(s_{ρ}B_{ρ} − s_{ρ−2}B_{ρ−2})
= B_{ρ−1}(t_{ρ}B_{ρ} − t_{ρ−1}B_{ρ−2})
= B_{ρ−1}(−t_{ρ−1}ϵ_{ρ}B_{ρ} − t_{ρ−1}B_{ρ−2})
= −t_{ρ−1}ϵ_{ρ}B_{ρ−1}(B_{ρ} + ϵ_{ρ}B_{ρ−2}).

Hence

|B′_{ρ−1}(B′_{ρ} − B′_{ρ−2})| = B_{ρ−1}(B_{ρ} + ϵ_{ρ}B_{ρ−2})  (19)

and (17) and (19) give the second result of criterion 1) above. Remark 7. John Robertson in an email to the author, dated November 26, 2007, noted the following errors in Williams [9, pp. 12–13]:

(i) Criterion 3), Theorem 6, page 12, should be

|A′_{π−1}| = A′_{ρ}B′_{ρ} − A′_{ρ−1}B′_{ρ−1},
|B′_{π−1}| = B′_{ρ}^{2} − B′_{ρ−1}^{2}.

(ii) Criterion 6), Theorem 7, page 13, should be

|A′_{π−1}| = 2A′_{ρ−1}B′_{ρ−1} + A′_{ρ−2}B′_{ρ−2} − |A′_{ρ−1}B′_{ρ−2} + B′_{ρ−1}A′_{ρ−2}|,
|B′_{π−1}| = 2B′_{ρ−1}^{2} + B′_{ρ−2}^{2} − 2|B′_{ρ−2}B′_{ρ−1}|.

4 Midpoint criteria in terms of unisequences

The RCF of \sqrt{D}, with period-length p, has the form

\sqrt{D} = \{ \begin{matrix}[a_{0}, \overline{a_{1}, …, a_{h−1}, a_{h−1} …, a_{1}, 2a_{0}}] & if p = 2h − 1; \\ [a_{0}, \overline{a_{1}, …, a_{h−1}, a_{h}, a_{h−1}, …, a_{1}, 2a_{0}}] & if p = 2h. \end{matrix}  (20)

We have Euler’s midpoint formulae for solving Pell’s equation x^{2} − Dy^{2} = ±1 using the regular continued fraction (see Dickson [3, p. 358]):

Q_{h−1} = Q_{h},
A_{2h−2} = A_{h−1}B_{h−1} + A_{h−2}B_{h−2},
B_{2h−2} = B_{h−1}^{2} + B_{h−2}^{2},

if p = 2h − 1;

P_{h} = P_{h+1},
A_{2h−1} = A_{h}B_{h−1} + A_{h−1}B_{h−2},
B_{2h−1} = B_{h−1}(B_{h} + B_{h−2}),

if p = 2h. We also need the following symmetry properties from Perron [7, p. 81]:

a_{t} = a_{p−t}, t = 1, 2, …, p − 1,  (21)
P_{t+1} = P_{p−t}, t = 0, 1, …, p − 1,  (22)
Q_{t} = Q_{p−t}, t = 0, 1, …, p.  (23)

Theorem 8. Using the notation of (20), in relation to Theorem 6, we have

(1) If p = 2h − 1, h > 1 and a_{h−1} > 1, or p = 1, we get criterion 3).

(2) If p = 2h, h > 1 and a_{h−1} > 1, a_{h} > 1, or p = 2 and a_{1} > 1, we get criterion 1).

(3) Suppose p = 2h and a_{h−1} = 1, a_{h} > 1, so that a_{h} is enclosed by two M-unisequences. Then

(a) if M ≥ 2 is even, we get criterion 2).

(b) if M is odd, we get criterion 1).

(4) Suppose the centre of a period contains an M-unisequence, M ≥ 1.

(a) If M is odd, then p = 2h and we get criterion 1) if M = 4t + 3, criterion 3) if M = 4t + 1.

(b) If M is even, then p = 2h − 1 and we get criterion 4) if M = 4t, criterion 5) if

M = 4t + 2. Before we can prove Theorem 8, we need some results on the RCF to NICF-P conversion.

5 The RCF to NICF-P conversion and its properties

Lemma 9. Let ξ_{0} = \frac{P_{0}+\sqrt{D}}{Q_{0}} have NICF-P and RCF expansions:

ξ_{0} = a′_{0} + \frac{ϵ_{1}|}{|a′_{1}} + ⋯ = a_{0} + \frac{1|}{|a_{1}} + ⋯,

with complete quotients ξ′_{m}, ξ_{m}, respectively. Define f(m) recursively for m ≥ 0 by f(0) = 0 and

f(m + 1) = \begin{cases}f(m) + 1, & if ϵ_{m+1} = 1; \\ f(m) + 2, & if ϵ_{m+1} = −1. \end{cases}  (24)

Then for m ≥ 0,

ϵ_{m+1} = \begin{cases}1, & if a_{f(m)+1} > 1; \\ −1, & if a_{f(m)+1} = 1, \end{cases}  (25)
ξ′_{m} = \begin{cases}ξ_{f(m)}, & if ϵ_{m} = 1; \\ ξ_{f(m)} + 1, & if ϵ_{m} = −1, \end{cases}  (26)

a′_{m} = \begin{cases}a_{f(m)}, & if ϵ_{m} = 1 and ϵ_{m+1} = 1; \\ a_{f(m)} + 1, & if ϵ_{m}ϵ_{m+1} = −1; \\ a_{f(m)} + 2, & if ϵ_{m} = −1 and ϵ_{m+1} = −1. \end{cases}  (27)

Proof. See Theorem 2, Matthews and Robertson [5].

Remark 10. By virtue of (24) and (26), we say that the ξ′_{m} are obtained from the ξ_{n} in jumps of 1 or 2.

Lemma 11. Let ξ_{0} = (a_{0}, a_{1}, …) be an RCF expansion. Then if [x] denotes the nearest integer to x, we have

[ξ_{n}] = \begin{cases}a_{n}, & if a_{n+1} > 1; \\ a_{n} + 1, & if a_{n+1} = 1. \end{cases}

Proof. If [ξ_{n}] = a_{n} + 1, then ξ_{n} > a_{n} + \frac{1}{2} and hence a_{n+1} = 1, whereas if [ξ_{n}] = a_{n}, then ξ_{n} < a_{n} + \frac{1}{2} and hence a_{n+1} > 1.

Lemma 12. Let ξ_{0} = \frac{P_{0}+\sqrt{D}}{Q_{0}} have NICF-P expansion

ξ_{0} = a′_{0} + \frac{ϵ_{1}|}{|a′_{1}} + · · · .

Then

A′_{m} = \begin{cases}A_{f(m)} & if ϵ_{m+1} = 1; \\ A_{f(m)+1} & if ϵ_{m+1} = −1, \end{cases}  (28)

where f(m) is defined by (24). Equivalently, in the notation of Bosma [2, p. 372], if n(k) = f(k + 1) − 1 for k ≥ −1, then

n(k) = \begin{cases}n(k − 1) + 1, & if ϵ_{k+1} = 1; \\ n(k − 1) + 2, & if ϵ_{k+1} = −1 \end{cases}  (29)

and (28) has the simpler form

A′_{k} = A_{n(k)} for k ≥ 0.  (30)

Remark 13. From (25) and (29), we see that ϵ_{m+1} = −1 implies a_{n(m)} = 1.

Proof. (by induction). We first prove (30) for k = 0. We use Lemma 11.

ϵ_{1} = 1 ⟹ a_{1} > 1 ⟹ [ξ_{0}] = a_{0}

⟹ A′_{0} = A_{0}.

ϵ_{1} = −1 ⟹ a_{1} = 1 ⟹ [ξ_{0}] = a_{0} + 1 = a_{0}a_{1} + 1

⟹ A′_{0} = A_{1}.

We next prove (30) for k = 1. We have to prove

A′_{1} = \begin{cases}A_{f(1)} & if ϵ_{2} = 1; \\ A_{f(1)+1} & if ϵ_{2} = −1, \end{cases}

where

f(1) = \begin{cases}1 & if ϵ_{1} = 1; \\ 2 & if ϵ_{1} = −1. \end{cases}

i.e.,

A′_{1} = \begin{cases}A_{1} & if ϵ_{1} = 1, ϵ_{2} = 1; \\ A_{2} & if ϵ_{1}ϵ_{2} = −1; \\ A_{3} & if ϵ_{1} = −1, ϵ_{2} = −1. \end{cases}

Now A′_{1} = a′_{0}a′_{1} + ϵ_{1}. We have

a′_{0} = \begin{cases}a_{0} & if ϵ_{1} = 1; \\ a_{0} + 1 & if ϵ_{1} = −1 \end{cases}

and

a′_{1} = \begin{cases}a_{f(1)} & if ϵ_{1} = 1 = ϵ_{2}; \\ a_{f(1)} + 1 & if ϵ_{1}ϵ_{2} = −1; \\ a_{f(1)} + 2 & if ϵ_{1} = −1 = ϵ_{2}. \end{cases}

Hence

a′_{1} = \begin{cases}a_{1} & if ϵ_{1} = 1 = ϵ_{2}; \\ a_{1} + 1 & if ϵ_{1} = 1, ϵ_{2} = −1; \\ a_{2} + 1 & if ϵ_{1} = −1, ϵ_{2} = 1; \\ a_{2} + 2 & if ϵ_{1} = −1, ϵ_{2} = −1. \end{cases}

Case 1. ϵ_{1} = 1 = ϵ_{2}. Then A′_{1} = a_{0}a_{1} + 1 = A_{1}. Case 2. ϵ_{1} = 1, ϵ_{2} = −1. Then a_{2} = 1 and

A′_{1} = a_{0}(a_{1} + 1) + 1,
A_{2} = (a_{0}a_{1} + 1)a_{2} + a_{0} = a_{0}a_{1} + 1 + a_{0} = A′_{1}.

Case 3. ϵ_{1} = −1, ϵ_{2} = 1. Then a_{1} = 1 and

A′_{1} = (a_{0} + 1)(a_{2} + 1) − 1

= a_{0}a_{2} + a_{0} + a_{2},

A_{2} = (a_{0}a_{1} + 1)a_{2} + a_{0}

= (a_{0} + 1)a_{2} + a_{0} = A′_{1}.

Case 4. ϵ_{1} = −1 = ϵ_{2}. Then a_{1} = 1 = a_{3} and

A′_{1} = (a_{0} + 1)(a_{2} + 2) − 1

= a_{0}a_{2} + a_{2} + 2a_{0} + 1.

Also

A_{3} = a_{3}A_{2} + A_{1}
= A_{2} + A_{1}
= ((a_{0}a_{1} + 1)a_{2} + a_{0}) + (a_{0}a_{1} + 1)
= ((a_{0} + 1)a_{2} + a_{0}) + (a_{0} + 1) = A′_{1}.

Finally, let k ≥ 0 and assume (30) holds for k and k + 1 and use the equation

A′_{k+2} = a′_{k+2}A′_{k+1} + ϵ_{k+2}A′_{k}.

Then from (27), with j = n(k + 1) + 1, we have

a′_{k+2} = \begin{cases}a_{j} & if ϵ_{k+2} = 1, ϵ_{k+3} = 1; \\ a_{j} + 1 & if ϵ_{k+2}ϵ_{k+3} = −1; \\ a_{j} = 2 & if ϵ_{k+2} = −1 = ϵ_{k+3}. \end{cases}  (31)

Case 1. Suppose ϵ_{k+2} = 1 = ϵ_{k+3} = 1. Then

n(k + 1) = n(k) + 1 = j − 1, n(k + 2) = n(k + 1) + 1 = j

and

A′_{k+2} = a_{j}A_{j−1} + A_{j−2} = A_{j} = A_{n(k+2)}.

Case 2. Suppose ϵ_{k+2} = 1, ϵ_{k+3} = −1. Then

n(k + 1) = n(k) + 1 = j − 1, n(k + 2) = n(k + 1) + 2 = j + 1

and

A′_{k+2} = (a_{j} + 1)A_{j−1} + A_{j−2}.

Now ϵ_{k+3} = −1 implies 1 = a_{n(k+2)} = a_{j+1}, so A_{j+1} = A_{j} + A_{j−1}. Hence

A′_{k+2} = A_{j+1} = A_{n(k+2)}.

Case 3. Suppose ϵ_{k+2} = −1, ϵ_{k+3} = 1. Then

n(k + 1) = n(k) + 2 = j − 1, n(k + 2) = n(k + 1) + 1 = j

and

A′_{k+2} = (a_{j} + 1)A_{j−1} − A_{j−3}.

Now ϵ_{k+2} = −1 implies 1 = a_{n(k+1)} = a_{j−1}, so A_{j−1} = A_{j−2} + A_{j−3}. Hence

A′_{k+2} = a_{j}A_{j−1} + A_{j−2} = A_{j} = A_{n(k+2)}.

Case 4. Suppose ϵ_{k+2} = −1 = ϵ_{k+3}. Then

n(k + 1) = n(k) + 2 = j − 1, n(k + 2) = n(k + 1) + 2 = j + 1 and

A′_{k+2} = (a_{j} + 2)A_{j−1} − A_{j−3}.

Now ϵ_{k+3} = −1 ⟹ 1 = a_{n(k+2)} = a_{j+1} and ϵ_{k+2} = −1 ⟹ 1 = a_{n(k+1)} = a_{j−1}, so

A_{j+1} = A_{j} + A_{j−1} and A_{j−1} = A_{j−2} + A_{j−3}.

Hence

A′_{k+2} = (a_{j} + 2)A_{j−1} − (A_{j−1} − A_{j−2})
= A_{j} + A_{j−1} = A_{j+1} = A_{n(k+2)}.

Lemma 14. Each a_{n} > 1, n ≥ 1 will be visited by the algorithm of Lemma 9, i.e., there exists an m such that n = f(m).

Proof. Let a_{n} > 1 and f(m) ≤ n < f(m + 1). If f(m) < n, then f(m + 1) = f(m) + 2 and ϵ_{m+1} = −1; also n = f(m) + 1. Then from (25), a_{n} = a_{f(m)+1} = 1.

Note that in the RCF to NICF-P transformation, we have f(k) = p, where k is the NICF-P period-length.

Lemma 15. Suppose that RCF partial quotients a_{r} and a_{s} satisfy a_{r} > 1, a_{s} > 1, r < s. Then the number J of jumps in the RCF to NICF-P transformation when starting from a_{r} and finishing at a_{s} is J = (s − r + E)/2, where E is the number of even unisequences in the interval [a_{r}, a_{s}]. Here we include zero unisequences [a_{i}, a_{i+1}], where a_{i} > 1 and a_{i+1} > 1.

Proof. Suppose the unisequences in [a_{r}, a_{s}] have lengths m_{1}, …, m_{N} and let j_{i} be the number of jumps occurring in a unisequence of length m_{i}. Then

j_{i} = \frac{m_{i} + 1 + e_{i}}{2} , where e_{i} = \begin{cases}0 & if m_{i} is odd; \\ 1 & if m_{i} is even. \end{cases}

Then

J = ∑_{i=1}^{N} j_{i} = ∑_{i=1}^{N} \frac{m_{i} + 1 + e_{i}}{2}

= \frac{1}{2}(N + ∑_{i=1}^{N} m_{i}) + \frac{E}{2}

= \frac{s − r}{2} + \frac{E}{2} = \frac{s − r + E}{2} .

Corollary 16. The number of jumps in the interval [a_{0}, a_{r}], a_{r} > 1, equals the number in the interval [a_{p−r}, a_{p}], where p is the period-length and r ≤ p/2.

Proof. This follows from Lemma 15 and the symmetry of an RCF period.

6 Proof of Theorem 8

We use the notation of Lemmas 9 and 12. Case (1)(i). Assume p = 2h − 1, h > 1 and there is an even length unisequence, or no unisequence, on each side of a_{h−1} > 1, a_{h} > 1, e.g., \sqrt{73} = [8, 1_{∗}, 1, 5, 5, 1, 1, 16_{∗}] or \sqrt{89} = [9, 2_{∗}, 3, 3, 2, 18_{∗}]. Let f(m) = h − 1, where m is the number of jumps in [a_{0}, a_{h−1}]. Then f(m + 1) = h and

ξ′_{m} = ξ_{h−1}, ϵ_{m} = 1,
ξ′_{m+1} = ξ_{h}, ϵ_{m+1} = 1.

By Corollary 16, m is also the number of jumps in [a_{h}, a_{p}]. There is also one jump in [a_{h−1}, a_{h}]. Hence k = 2m + 1. As Q_{h−1} = Q_{h}, we have Q′_{m} = Q′_{m+1}, which is criterion 3) of Theorem 6. Also

ϵ_{m} = 1 ⟹ f(m) = f(m − 1) + 1, A′_{m−1} = A_{f(m−1)},
ϵ_{m+1} = 1 ⟹ f(m + 1) = f(m) + 1, A′_{m} = A_{f(m)}.

Hence A′_{m−1} = A_{h−2}, A′_{m} = A_{h−1}, B′_{m−1} = B_{h−2}, B′_{m} = B_{h−1} and

A_{p−1} = A_{h−1}B_{h−1} + A_{h−2}B_{h−2}
= A′_{m}B′_{m} + A′_{m−1}B′_{m−1}
= A′_{m}B′_{m} + ϵ_{m+1}A′_{m−1}B′_{m−1}.

Also

B_{p−1} = B_{h−1}^{2} + B_{h−2}^{2}
= B′_{m}^{2} + B′_{m−1}^{2}
= B′_{m}^{2} + ϵ_{m+1}B′_{m−1}^{2}.

If p = 1, \sqrt{D} = [a, \overline{2a}] and the NICF and RCF expansions are identical. Also Q′_{0} = Q′_{1} = 1, ϵ_{1} = 1 and we have criterion 3). Case (1)(ii). Assume p = 2h − 1, with an odd length unisequence on each side of a_{h−1} > 1, a_{h} > 1, e.g., \sqrt{113} = [10, 1_{∗}, 1, 1, 2, 2, 1, 1, 1, 20_{∗}]. Let f(m) = h − 1. Then f(m + 1) = h and

ξ′_{m} = ξ_{h−1} + 1, ϵ_{m} = −1,
ξ′_{m+1} = ξ_{h}, ϵ_{m+1} = 1,

and as in Case (1)(i), k = 2m + 1. As Q_{h−1} = Q_{h}, we have Q′_{m} = Q′_{m+1}, which is criterion 3). Also

ϵ_{m} = −1 ⟹ f(m) = f(m − 1) + 2, A′_{m−1} = A_{f(m−1)+1},
ϵ_{m+1} = 1 ⟹ f(m + 1) = f(m) + 1, A′_{m} = A_{f(m)}.

Hence A′_{m−1} = A_{h−2}, A′_{m} = A_{h−1} and B′_{m−1} = B_{h−2}, B′_{m} = B_{h−1}. Then as in Case (1)(i), we get

A′_{m}B′_{m} + ϵ_{m+1}A′_{m−1}B′_{m−1} = A_{p−1} and B′_{m}^{2} + ϵ_{m+1}B′_{m−1}^{2} = B_{p−1}.

Case (2) Assume p = 2h, h > 1, a_{h−1} > 1, a_{h} > 1, e.g., \sqrt{92} = [9, 1_{∗}, 1, 2, 4, 2, 1, 1, 18_{∗}]. Let f(m) = h. Then f(m + 1) = h + 1 and

ξ′_{m} = ξ_{h}, ϵ_{m} = 1,
ξ′_{m+1} = ξ_{h+1}, ϵ_{m+1} = 1,

Also by Corollary 16, m is the number of jumps in [a_{h}, a_{p}]. Hence k = 2m. Then P_{h} = P_{h+1} gives P′_{m} = P′_{m+1} and we have criterion 1) of Theorem 6. Also

ϵ_{m} = 1 ⟹ f(m) = f(m − 1) + 1, A′_{m−1} = A_{f(m−1)},
ϵ_{m+1} = 1 ⟹ f(m + 1) = f(m) + 1, A′_{m} = A_{f(m)}.

Hence A′_{m−1} = A_{h−1}, A′_{m} = A_{h} and B′_{m−1} = B_{h−1}, B′_{m} = B_{h}. Then

A_{p−1} = A_{h}B_{h−1} + A_{h−1}B_{h−2}
= A′_{m}B′_{m−1} + A′_{m−1}B_{h−2}.  (32)

But B_{h−2} = B_{h} − a_{h}B_{h−1} = B′_{m} − a′_{m}B_{m−1} = B′_{m−2}. Hence (32) gives

A_{p−1} = A′_{m}B′_{m−1} + A′_{m−1}B′_{m−2}
= A′_{m}B′_{m−1} + ϵ_{m}A′_{m−1}B′_{m−2}.

Also

B_{p−1} = B_{h−1}(B_{h} + B_{h−2})
= B′_{m−1}(B′_{m} + B′_{m−2}).

Case (3)(a). Assume p = 2h, with an even length unisequence each side of a_{h} > 1, e.g., \sqrt{21} = [4, 1_{∗}, 1, 2, 1, 1, 8_{∗}]. Let f(m) = h. Then f(m + 1) = h + 2. As in Case(2), k = 2m. Also

ξ′_{m} = ξ_{h}, ϵ_{m} = 1,
ξ′_{m+1} = ξ_{h+2} + 1, ϵ_{m+1} = −1.

Then

ϵ_{m} = 1 ⟹ f(m) = f(m − 1) + 1, A′_{m−1} = A_{f(m−1)},
ϵ_{m+1} = −1 ⟹ f(m + 1) = f(m) + 2, A′_{m} = A_{f(m)+1}.

Hence A′_{m−1} = A_{h−1}, A′_{m} = A_{h+1} and B′_{m−1} = B_{h−1}, B′_{m} = B_{h+1}. We prove criterion 2) of Theorem 6, P′_{m+1} = P′_{m} + Q′_{m}, i.e., P_{h+2} + Q_{h+2} = P_{h} + Q_{h}.

We note from Theorem 10.19, Rosen [8], that a_{h+1} = 1 implies P_{h+2} + P_{h+1} = Q_{h+1}. Also

P_{h+2}^{2} = D − Q_{h+1}Q_{h+2},
P_{h+1}^{2} = D − Q_{h}Q_{h+1}.

Hence

P_{h+2}^{2} − P_{h+1}^{2} = Q_{h+1}(Q_{h} − Q_{h+2})
= (P_{h+2} + P_{h+1})(Q_{h} − Q_{h+2}).

Hence

P_{h+2} − P_{h+1} = Q_{h} − Q_{h+2},
P_{h+2} + Q_{h+2} = P_{h+1} + Q_{h}
= P_{h} + Q_{h}  (33)

We next prove

A_{p−1} = B′_{m−1}(A′_{m} − A′_{m−1}) + A′_{m−1}B′_{m−2},  (34)
B_{p−1} = B′_{m−1}(B′_{m} − B′_{m−1} + B′_{m−2}).  (35)

First note that by equations (27), ϵ_{m} = 1 and ϵ_{m+1} = 1 imply

a′_{m} = a_{f(m)} + 1 = a_{h} + 1.

Also a_{h+1} = 1 implies B_{h+1} = B_{h} + B_{h−1}, i.e., B′_{m} = B_{h} + B′_{m−1}. Hence

B_{h−2} = B_{h} − a_{h}B_{h−1}
= (B′_{m} − B′_{m−1}) − (a′_{m} − 1)B′_{m−1}
= B′_{m} − a′_{m}B′_{m−1} = B′_{m−2}.

Then

A_{p−1} = A_{h}B_{h−1} + A_{h−1}B_{h−2}
= (A′_{m} − A′_{m−1})B′_{m−1} + A′_{m−1}B′_{m−2},

proving (34). Also

B_{p−1} = B_{h−1}(B_{h} + B_{h−2})
= B′_{m−1}(B′_{m} − B′_{m−1} + B′_{m−2}),

proving (35). If p = 2 and a_{1} > 1, then D = a^{2} + b, 1 < b < 2a, b dividing 2a (Rosen [8, p. 389]). Then \sqrt{D} = [a, 2a/b_{∗}, 2a_{∗}] and the NICF and RCF expansions are identical. Then ξ′_{1} = \frac{a+\sqrt{D}}{b}, ξ′_{2} = a + \sqrt{D}, P′_{1} = P′_{2} = a, ϵ_{1} = 1 and we have criterion 1).

Case (3)(b). Assume p = 2h, with an odd length unisequence each side of a_{h} > 1, e.g., \sqrt{14} = [3, 1_{∗}, 2, 1, 6_{∗}]. Let f(m) = h. Then f(m + 1) = h + 2 and k = 2m. Then

ξ′_{m} = ξ_{h} + 1, ϵ_{m} = −1,
ξ′_{m+1} = ξ_{h+2} + 1, ϵ_{m+1} = −1.

Then

ϵ_{m} = −1 ⟹ f(m) = f(m − 1) + 2, A′_{m−1} = A_{f(m−1)+1},
ϵ_{m+1} = −1 ⟹ f(m + 1) = f(m) + 2, A′_{m} = A_{f(m)+1}.

We have A′_{m−1} = A_{h−1}, A′_{m} = A_{h+1}, B′_{m−1} = B_{h−1}, B′_{m} = B_{h+1}. Then using (33), we get

P′_{m+1} = P_{h+2} + Q_{h+2} = P_{h} + Q_{h} = P′_{m},

which is criterion 1) of Theorem 6. As ϵ_{m} = −1, it remains to prove

A_{p−1} = B′_{m−1}A′_{m} − A′_{m−1}B′_{m−2}
B_{p−1} = B′_{m−1}(B′_{m} − B′_{m−2}).

First, a_{h+1} = 1 implies A_{h+1} = A_{h} + A_{h−1}, i.e., A′_{m} = A_{h} + A_{h−1}. Also ϵ_{m} = −1 = ϵ_{m+1} implies a′_{m} = a_{f(m)} + 2 = a_{h} + 2. Hence

−B′_{m−2} = ϵ_{m}B′_{m−2}
= B′_{m} − a′_{m}B′_{m−1}
= (B_{h} + B_{h−1}) − (a_{h} + 2)B_{h−1}
= B_{h} − B_{h−1} − a_{h}B_{h−1}
= B_{h−2} − B_{h−1}.

Hence

B′_{m−1}A′_{m} − A′_{m−1}B′_{m−2} = B_{h−1}(A_{h} + A_{h−1}) − A_{h−1}(B_{h−1} − B_{h−2})
= B_{h−1}A_{h} + A_{h−1}B_{h−2}
= A_{p−1}.

Finally,

B′_{m−1}(B′_{m} − B′_{m−2}) = B_{h−1}((B_{h} + B_{h−1}) + (B_{h−2} − B_{h−1}))
= B_{h−1}(B_{h} + B_{h−2})
= B_{p−1}.

Case (4)(a). Assume p = 2h with an M-unisequence, M odd, at the centre of a period. There are two cases:

M = 4t + 3, e.g., \sqrt{88} = [9, 2_{∗}, 1, 1, 1, 2, 18_{∗}]. Let f(m) = h. Then f(m + 1) = h + 2 and

ξ′_{m} = ξ_{h} + 1, ϵ_{m} = −1;
ξ′_{m+1} = ξ_{h+2} + 1, ϵ_{m+1} = −1.

and as with case (3)(b), we have criterion 1) of Theorem 6. Now m is the number of jumps in [a_{0}, a_{h}]. Then we have a central unisequence [a_{r}, a_{p−r}] of length 4t + 3. There are t + 1 jumps of 2 in [a_{r}, a_{h}], so r + 2t + 2 = h. Let J be the number of jumps in [a_{0}, a_{r}]. Hence m = J + (t + 1). There are t + 1 jumps of 2 in [a_{h}, a_{p−r}] and J jumps in [a_{p−r}, a_{p}]. Hence

k = (J + t + 1) + (t + 1) + J = 2(J + t + 1) = 2m.

M = 4t + 1, e.g., \sqrt{91} = [9, 1_{∗}, 1, 5, 1, 5, 1, 1, 18_{∗}]. Let f(m) = h − 1. Then f(m + 1) = h + 1 and

ξ′_{m+1} = ξ_{h+1} + 1, ϵ_{m+1} = −1.

Also ξ′_{m} = ξ_{h−1} or ξ_{h−1} + 1. We have a central unisequence [a_{r}, a_{p−r}] of length 4t + 1. There are t jumps of 2 in [a_{r}, a_{h−1}], so r + 2t = h − 1. Let J be the number of jumps in [a_{0}, a_{r}]. Hence m, being the number of jumps in [a_{0}, a_{h−1}] satisfies m = J +t. There is also one jump in [a_{h−1}, a_{h+1}], t jumps of 2 in [a_{h+1}, a_{p−r}] and J jumps in [a_{p−r}, a_{p}]. Hence

k = (J + t) + 1 + t + J = 2(J + t) + 1 = 2m + 1.

Then Q′_{m+1} = Q_{h+1} and Q′_{m} = Q_{h−1}, so Q_{h−1} = Q_{h+1} implies Q′_{m} = Q′_{m+1} and we have criterion 3) of Theorem 6. We have A′_{m} = A_{f(m)+1} = A_{h}. Also, regardless of the sign of ϵ_{m}, we have A′_{m−1} = A_{h−2}. We now prove

A_{k−1} = A′_{m}B′_{m} − A′_{m−1}B′_{m−1},  (36)
B_{k−1} = B′_{m}^{2} − B′_{m−1}^{2}.  (37)

Noting that a_{h} = 1 gives A_{h} = A_{h−1} + A_{h−2} and B_{h} = B_{h−1} + B_{h−2}, we have

A′_{m}B′_{m} − A′_{m−1}B′_{m−1} = A_{h}B_{h} − A_{h−2}B_{h−2}
= A_{h}(B_{h−1} + B_{h−2}) − (A_{h} − A_{h−1})B_{h−2}
= A_{h}B_{h−1} + A_{h−1}B_{h−2}
= A_{p−1}.

Also

B′_{m}^{2} − B′_{m−1}^{2} = B_{h}^{2} − B_{h−2}^{2}
= (B_{h} − B_{h−2})(B_{h} + B_{h−2})
= B_{h−1}(B_{h} + B_{h−2})
= B_{p−1}.

Case (4)(b) Assume p = 2h − 1 with an M-unisequence, M even, at the centre of a period. There are two cases:

M = 4t, e.g., \sqrt{13} = [3, 1_{∗}, 1, 1, 1, 6_{∗}]. Let f(m) = h − 1. Then f(m + 1) = h + 1 and

ξ′_{m} = ξ_{h−1} + 1, ϵ_{m} = −1,
ξ′_{m+1} = ξ_{h+1} + 1, ϵ_{m+1} = −1.

We have a central unisequence [a_{r}, a_{p−r}] of length 4t with r + 2t = h − 1. Let J be the number of jumps in [a_{0}, a_{r}]. There are t jumps of 2 in [a_{r}, a_{h−1}]. Hence m, being the number of jumps in [a_{0}, a_{h−1}] satisfies m = J + t. There are also t jumps of 2 in [a_{h−1}, a_{p−r−1}], one jump in [a_{p−r−1}, a_{p−r}] and J jumps in [a_{p−r}, a_{p}]. Hence

k = (J + t) + t + 1 + J = 2(J + t) + 1 = 2m + 1.

Then

ϵ_{m} = −1 ⟹ f(m) = f(m − 1) + 2, A′_{m−1} = A_{f(m−1)+1},
ϵ_{m+1} = −1 ⟹ f(m + 1) = f(m) + 2, A′_{m} = A_{f(m)+1}.

We have A′_{m−1} = A_{h−2}, A′_{m} = A_{h}. We now verify criterion 4) of Theorem 6.

P′_{m+1} = Q′_{m} + \frac{1}{2}Q′_{m+1}.  (38)

We note that a_{h} = 1 implies P_{h+1} = Q_{h} − P_{h}. Then

P′_{m+1} = P_{h+1} + Q_{h+1}
= Q_{h} − P_{h} + Q_{h+1}.

Also

Q′_{m} + \frac{1}{2}Q′_{m+1} = Q_{h−1} + \frac{1}{2}Q_{h+1}.

Hence (38) holds if and only if

Q_{h} − P_{h} + Q_{h+1} = Q_{h−1} + \frac{1}{2}Q_{h+1},
i.e., Q_{h−1} − P_{h} + Q_{h+1} = Q_{h−1} + \frac{1}{2}Q_{h+1},
i.e., P_{h} = \frac{1}{2}Q_{h+1}.

However

P_{h}^{2} = D − Q_{h−1}Q_{h},
P_{h+1}^{2} = D − Q_{h}Q_{h+1},
P_{h}^{2} − P_{h+1}^{2} = Q_{h}(Q_{h+1} − Q_{h−1}),
P_{h} − P_{h+1} = Q_{h+1} − Q_{h−1},
P_{h} − (Q_{h} − P_{h}) = Q_{h+1} − Q_{h},
2P_{h} = Q_{h+1}.

Next we prove

A_{p−1} = A′_{m}B′_{m} + 2A′_{m−1}B′_{m−1} − (A′_{m}B′_{m−1} + B′_{m}A′_{m−1}),  (39)
B_{p−1} = B′_{m}^{2} + 2B′_{m−1}^{2} − 2B′_{m}B′_{m−1}.  (40)

Let

T = A′_{m}B′_{m} + 2A′_{m−1}B′_{m−1} − (A′_{m}B′_{m−1} + B′_{m}A′_{m−1}).

Then

T = A_{h}B_{h} + 2A_{h−2}B_{h−2} − (A_{h}B_{h−2} + B_{h}A_{h−2})
= A_{h}(B_{h} − B_{h−2}) + A_{h−2}(B_{h−2} − B_{h}) + A_{h−2}B_{h−2}
= A_{h}B_{h−1} − A_{h−2}B_{h−1} + A_{h−2}B_{h−2}
= A_{h}B_{h−1} + A_{h−2}(B_{h−2} − B_{h−1})
= (A_{h−1} + A_{h−2})B_{h−1} + A_{h−2}(B_{h−2} − B_{h−1})
= A_{h−1}B_{h−1} + A_{h−2}B_{h−2}
= A_{p−1}.

Also

B′_{m}^{2} + 2B′_{m−1}^{2} − 2B′_{m}B′_{m−1} = B_{h}^{2} + 2B_{h−2}^{2} − 2B_{h}B_{h−2}
= B_{h}(B_{h} − 2B_{h−2}) + 2B_{h−2}^{2}
= (B_{h−1} + B_{h−2})(B_{h−1} − B_{h−2}) + 2B_{h−2}^{2}
= B_{h−1}^{2} − B_{h−2}^{2} + 2B_{h−2}^{2}
= B_{h−1}^{2} + B_{h−2}^{2}
= B_{p−1}.

M = 4t+2, e.g., \sqrt{29} = [5, 2_{∗}, 1, 1, 2, 10_{∗}]. Let f(m) = h. Then ϵ_{m} = −1 and ξ′_{m} = ξ_{h}+1. Also f(m) = f(m − 1) + 2, so A′_{m−1} = A_{f(m−1)+1} = A_{h−1}. Then we have a central unisequence [a_{r}, a_{p−r}] of length 4t + 2. There are t + 1 jumps in [a_{r}, a_{h}], so r + 2t + 2 = h. Let J be the number of jumps in [a_{0}, a_{r}]. Hence m, being the number of jumps in [a_{0}, a_{h}] satisfies m = J + t + 1. There are also t jumps of 2 in [a_{h}, a_{p−r−1}], one jump in [a_{p−r−1}, a_{p−r}] and J jumps in [a_{p−r}, a_{p}]. Hence

k = (J + t + 1) + t + 1 + J = 2(J + t + 1) = 2m.

We now verify Case 5) of the midpoint criteria:

P′_{m} = Q′_{m} + \frac{1}{2}Q′_{m−1}.  (41)

Then, as ξ′_{m−1} = ξ_{h−2} or ξ_{h−2} + 1, we have Q′_{m−1} = Q_{h−2} and

P′_{m} = Q′_{m} + \frac{1}{2}Q′_{m−1} ⟺ P_{h} + Q_{h} = Q_{h} + \frac{1}{2}Q_{h−2}
⟺ P_{h} = \frac{1}{2}Q_{h−2}.

But a_{h−1} = 1 implies P_{h} = Q_{h−1} − P_{h−1}. Hence

P_{h−1}^{2} − P_{h}^{2} = (D − Q_{h−2}Q_{h−1}) − (D − Q_{h−1}Q_{h}),
(P_{h−1} − P_{h})Q_{h−1} = Q_{h−1}(Q_{h} − Q_{h−2}),
P_{h−1} − P_{h} = Q_{h} − Q_{h−2},
Q_{h−1} − 2P_{h} = Q_{h−1} − Q_{h−2},
2P_{h} = Q_{h−2}.

Next we prove

A_{p−1} = 2A′_{m−1}B′_{m−1} + A′_{m−2}B′_{m−2} − (A′_{m−1}B′_{m−2} + B′_{m−1}A′_{m−2}),  (42)
B_{p−1} = 2B′_{m−1}^{2} + B′_{m−2}^{2} − 2B′_{m−1}B′_{m−2}.  (43)

Note that regardless of the sign of ϵ_{m−1}, we have A′_{m−2} = A_{h−3}. To prove (42), let

T = 2A′_{m−1}B′_{m−1} + A′_{m−2}B′_{m−2} − (A′_{m−1}B′_{m−2} + B′_{m−1}A′_{m−2}).

Then

T = 2A_{h−1}B_{h−1} + A_{h−3}B_{h−3} − (A_{h−1}B_{h−3} + B_{h−1}A_{h−3})
= 2A_{h−1}B_{h−1} + (A_{h−1} − A_{h−2})(B_{h−1} − B_{h−2})
− A_{h−1}(B_{h−1} − B_{h−2}) − B_{h−1}(A_{h−1} − A_{h−2})
= A_{h−1}B_{h−1} + A_{h−2}B_{h−2}
= A_{p−1}.

Finally, we prove (43).

2B′_{m−1}^{2} + B′_{m−2}^{2} − 2B′_{m−1}B′_{m−2} = 2B_{h−1}^{2} + B_{h−3}^{2} − 2B_{h−1}B_{h−3}
= 2B_{h−1}^{2} + (B_{h−1} − B_{h−2})^{2}
− 2B_{h−1}(B_{h−1} − B_{h−2})
= B_{h−1}^{2} + B_{h−2}^{2}
= B_{p−1}.

This completes the proof of Theorem 8.

7 RCF periods with only odd length unisequences

Lemma 17. Suppose there are no even length (≥ 2) unisequences in an RCF period of length p for \sqrt{D}. If k is the NICF period-length and 0 ≤ t ≤ k/2, then

f(k − t) = p − f(t),  (44)

Proof. Let f(t) = r. Then we have t jumps on [a_{0}, a_{r}]. Because of the symmetry of the partial quotients and the absence of even length unisequences, we get the same t jumps but in reverse order on [a_{p−r}, a_{p}]. There are k jumps on [a_{0}, a_{p}] and hence k − t jumps on [a_{0}, a_{p−r}]. Hence f(k − t) = p − r = p − f(t).

Theorem 18. Suppose there are no even length (≥ 2) unisequences in a RCF period of length p for \sqrt{D}. Then if k is the NICF period-length, for 1 ≤ t ≤ k/2, we have

(i) ϵ_{t} = ϵ_{k+1−t}; (ii) P′_{t} = P′_{k+1−t}; (iii) Q′_{t} = Q′_{k−t}; (iv) a′_{t} = a′_{k−t}, where ξ′_{t} = \frac{P′_{t}+\sqrt{D}}{Q′_{t}} is the t-th complete quotient of the NICF-P expansion of \sqrt{D}. Remark 19. In particular, if k = 2h, then (ii) implies P′_{h} = P′_{h+1} and we have criterion 1) of Theorem 6; while if k = 2h + 1, then (iii) implies Q′_{h} = Q′_{h+1} and we have criterion 3) of Theorem 6. Proof. (i) We use (24) and Lemma 17

ϵ_{t} = 1 ⟺ f(t) = f(t − 1) + 1
⟺ p − f(k − t) = p − f(k − t + 1) + 1
⟺ f(k − t + 1) = f(k − t) + 1
⟺ ϵ_{k−t+1} = 1.

(ii) (a) Assume ϵ_{t} = 1. Then ϵ_{k+1−t} = 1 and f(t) = f(t − 1) + 1. Hence ξ′_{t} = ξ_{f(t)} = \frac{P_{f(t)}+\sqrt{D}}{Q_{f(t)}} and

ξ′_{k+1−t} = ξ_{f(k+1−t)} = ξ_{p−f(t−1)} = ξ_{p+1−f(t)}

= \frac{P_{p+1−f(t)} + \sqrt{D}}{Q_{p+1−f(t)}}

= \frac{P_{f(t)} + \sqrt{D}}{Q_{f(t)−1}}.

Hence P′_{t} = P_{f(t)} = P′_{k+1−t}.

(b) Assume ϵ_{t} = −1. Then ϵ_{k+1−t} = −1 and f(t) = f(t − 1) + 2. Hence ξ′_{t} = ξ_{f(t)} + 1 = \frac{P_{f(t)}+Q_{f(t)}+\sqrt{D}}{Q_{f(t)}} and

ξ′_{k+1−t} = ξ_{f(k+1−t)} + 1 = ξ_{p−f(t−1)} + 1

= \frac{P_{p−f(t−1)} + \sqrt{D}}{Q_{p−f(t−1)}} + 1 = \frac{P_{f(t−1)+1} + Q_{f(t−1)} + \sqrt{D}}{Q_{f(t−1)}}.

Hence

P′_{t} = P_{f(t)} + Q_{f(t)},
P′_{k+1−t} = P_{f(t−1)+1} + Q_{f(t−1)}
= P_{f(t)−1} + Q_{f(t)−2}.

For brevity, write r = f(t) − 1. We have to prove P′_{t} = P′_{k+1−t}, i.e.,

P_{r} + Q_{r−1} = P_{r+1} + Q_{r+1}.  (45)

We have

P_{r+1}^{2} − P_{r}^{2} = (D − Q_{r}Q_{r+1}) − (D − Q_{r−1}Q_{r})
= Q_{r}(Q_{r−1} − Q_{r+1}).  (46)

Now ϵ_{t} = −1 implies a_{f(t−1)+1} = 1 = a_{f(t)−1} = a_{r} and hence P_{r+1} + P_{r} = a_{r}Q_{r} = Q_{r}. Then (46) gives

P_{r+1} − P_{r} = Q_{r−1} − Q_{r+1}

and hence (45). (iii) To prove Q′_{t} = Q′_{k−t}, we observe that

ξ′_{t} = ξ_{f(t)} or ξ_{f(t)} + 1,
ξ′_{k−t} = ξ_{f(k−t)} or ξ_{f(k−t)} + 1.

Then

Q′_{k−t} = Q_{f(k−t)} = Q_{p−f(t)} = Q_{f(t)} = Q′_{t}.

(iv)

a′_{t} = \begin{cases}a_{f(t)} if (ϵ_{t}, ϵ_{t+1}) = (1, 1); \\ a_{f(t)} + 1 if (ϵ_{t}, ϵ_{t+1}) = (1, −1) or (−1, 1); \\ a_{f(t)} + 2 if (ϵ_{t}, ϵ_{t+1}) = (−1, −1). \end{cases}

a′_{k−t} = \begin{cases}a_{f(k−t)} if (ϵ_{k−t}, ϵ_{k−t+1}) = (1, 1); \\ a_{f(k−t)} + 1 if (ϵ_{k−t}, ϵ_{k−t+1}) = (1, −1) or (−1, 1); \\ a_{f(k−t)} + 2 if (ϵ_{k−t}, ϵ_{k−t+1}) = (−1, −1). \end{cases}

Then as (ϵ_{t}, ϵ_{t+1}) = (ϵ_{k+1−t}, ϵ_{k−t}) and a_{f(k−t)} = a_{p−f(t)} = a_{f(t)}, it follows that a′_{t} = a′_{k−t}.

We give examples of even and odd NICF period-length in which only odd length unisequences occur.

(a) \sqrt{1532} = [39, 7_{∗}, 9, 1, 1, 1, 3, 1, 18, 1, 3, 1, 1, 1, 9, 7, 78_{∗}]

= 39 + \frac{1}{7_{∗}} + \frac{1}{10} − \frac{1}{3} − \frac{1}{5} − \frac{1}{20} − \frac{1}{5} − \frac{1}{3} − \frac{1}{10} + \frac{1}{7} + \frac{1}{78_{∗}} .

Here p = 16, k = 10, P′_{5} = P′_{6}.

(b) \sqrt{277} = [16, 1_{∗}, 1, 1, 4, 10, 1, 7, 2, 2, 3, 3, 2, 2, 7, 1, 10, 4, 1, 1, 1, 32_{∗}] =
17 − \frac{1}{3_{∗}} − \frac{1}{5} + \frac{1}{11} − \frac{1}{8} + \frac{1}{2} + \frac{1}{2} + \frac{1}{3} + \frac{1}{3} + \frac{1}{2} + \frac{1}{2} + \frac{1}{8} − \frac{1}{11} + \frac{1}{5} − \frac{1}{3} − \frac{1}{34_{∗}} .

Here p = 21, k = 15, Q′_{7} = Q′_{8}.

8 Acknowledgements

The author thanks John Robertson and Jim White for helpful remarks on the paper of H. C. Williams. The author also thanks Alan Offer for his help with the graphics package pstricks, and the referee for improving the presentation of the paper.

References

[1] A. Hurwitz, Über eine besondere Art der Kettenbruch-Entwicklung reeller Grössen, Acta Math. 12 (1889), 367–405.

[2] W. Bosma, Optimal continued fractions, Indag. Math. 49 (1987), 353—379.

[3] L. E. Dickson, History of the Theory of Numbers, Vol. 2, Chelsea AMS reprint, 1999.

[4] K. R. Matthews, J. P. Robertson and J. White, Midpoint criteria for solving Pell’s equation using the nearest square continued fraction, to appear in Math. Comp.

[5] K. R. Matthews and J. P. Robertson, Equality of quadratic surd period-lengths for NICF and NSCF, in preparation.

[6] B. Minnegerode, Über eine neue Methode, die Pellische Gleichung aufzulösen, Gött. Nachr. 23 (1873), 619–653.

[7] O. Perron, Die Lehre von den Kettenbrüchen, Band 1, Teubner, 1954.

[8] K. Rosen, Introduction to Number Theory and its Applications, Addison-Wesley, 1984.

[9] H. C. Williams, Some results concerning the nearest integer continued fraction expansion of \sqrt{D}, J. Reine Angew. Math. 315 (1980), 1–15.

2000 Mathematics Subject Classification: Primary 11A55, 11Y65. Keywords: nearest integer continued fraction, period–length, midpoint criteria, unisequence.

Received May 18 2009; revised version received September 3 2009. Published in Journal of Integer Sequences, September 22 2009.

Return to Journal of Integer Sequences home page.