\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Pstricks package must be loaded before hyperref to avoid color confusion.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{pst-node}
\psset{arrows=->, arcangle=45, nodesep=.1em, arrowscale=.8 .6,
linewidth=.6pt}
%Inline continued fraction notation
\newcommand{\ccfrac}[2]{{\setlength{\arraycolsep}{.2em}
  \begin{array}{c}
    \multicolumn{1}{c|}{\strut\smash{#1}}\\
    \hline\multicolumn{1}{|c}{\strut\smash{#2}}
  \end{array}}}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{defin}[theorem]{Definition}
\newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}}
\newtheorem{examp}[theorem]{Example}
\newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}}
\newtheorem{rema}[theorem]{Remark}
\newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}}

\newcommand{\cqd}[3]{\frac{#2}{#1+\sqrt{#3}}}
\def\floor#1{{\lfloor#1\rfloor}}
\newcommand{\cqu}[3]{\frac{#1+\sqrt{#3}}{#2}}
\newcommand{\half}{{\scriptstyle\frac{1}{2}}}
\newcommand{\dsh}[1]{#1^{''}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf Unisequences and Nearest Integer Continued \\
\vskip .1in
Fraction Midpoint Criteria for Pell's Equation}
\vskip 1cm
\large 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\\
\href{mailto:keithmatt@gmail.com}{\tt keithmatt@gmail.com} \\
\end{center}

\vskip .2in
\begin{abstract}
The nearest integer continued fractions of Hurwitz, Minnegerode (NICF-H) and in Perron's book {\em Die Lehre von den Kettenbr\"{u}chen} (NICF-P) are closely related.  
Midpoint criteria for solving Pell's equation $x^2-Dy^2=\pm1$ 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.  \end{abstract}

\section{Introduction}
In Perron's book \cite[p. 143]{perron}, a {\em nearest integer} continued fraction (Kettenbruch nach n\"{a}chsten Ganzen) expansion (NICF-P) of an irrational number $\xi_0$ is defined recursively by
\begin{equation}
\xi_n=q_n+\frac{\epsilon_{n+1}}{\xi_{n+1}}, -\half<\xi_n-q_n<\half,\label{eq:NICF-P1}
\end{equation}
where $\epsilon_{n+1}=\pm 1$, $q_n$ is an integer (the nearest integer to $\xi_n$) and $\mbox{sign}(\epsilon_{n+1})=\mbox{sign}(\xi_n-q_n)$.  Then we have the expansion
\begin{equation}
\xi_0=q_0+\ccfrac{\epsilon_1}{q_1}+\cdots+\ccfrac{\epsilon_{n}}{q_{n}}+\cdots\label{eq:NICF-P2}
\end{equation}
where
\begin{equation}
 q_n\geq 2,\ q_n+\epsilon_{n+1}\geq 2 \mbox{ for }n\geq 1.\label{eq:NICF-P3}
\end{equation}
 (Satz 10, \cite[p. 169]{perron}).

A. Hurwitz \cite{hurwitz} and B. Minnegerode \cite{minnegerode} defined a related nearest integer continued fraction (NICF-H) by
\begin{equation}
\xi'_n=q'_n-\frac{1}{\xi'_{n+1}}, -\half<\xi'_n-q'_n<\half,\label{eq:NICF-H1}
\end{equation}
where $q'_n$ is an integer.  Then 
\begin{equation}
\xi'_0=q'_0-\ccfrac{1}{q'_1}-\cdots-\ccfrac{1}{q'_{n}}-\cdots\label{eq:NICF-H2}
\end{equation}
and we have $|q'_n|\geq 2\mbox{ for }n\geq 1.$  Also if one of $q'_1,q'_2,\ldots$, say $q'_n$, equals $2$ (resp. $-2)$, then $q'_{n+1}<0$ (resp. $q'_{n+1}>0$) (Hurwitz \cite[p. 372]{hurwitz}).  Section \ref{section2} 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=\pm 1$ in terms of the NICF-H expansion of $\sqrt{D}$ (see Theorems 6 and 7, \cite[pp. 12--13]{hcw}).  His proof made extensive use of the singular continued fraction expansion of $\sqrt{D}$.  Theorem \ref{theorem1} of section \ref{section3} 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 \ref{lemma_singularization} of section 5, where the RCF is defined recursively by
\[
\xi_n=a_n+\frac{1}{\xi_{n+1}}, 
\]
with $a_n=\floor{\xi_n}$, the integer part of $\xi_n$. Theorem \ref{theorem2} of section \ref{section4} shows that the central part of a least period determines which of the criteria hold.  Finally, Theorem \ref{theorem3}, section \ref{section7}, describes the case where there are only odd-length {\em 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.
\section{Connections between the NICF-H and NICF-P expansions of an irrational number.}\label{section2}
\begin{lemma}
Let $q'_n, \xi'_n, A'_n/B'_n$ denote the $n$-th partial denominator, complete quotient and convergent of the \mbox{\rm NICF-H} expansion of an irrational number $\xi_0$ and $q_n, \epsilon_n, \xi_n, A_n/B_n$ denote the $n$-th partial denominator, partial numerator, complete quotient and convergent of the \mbox{\rm NICF-P} expansion of $\xi_0$,  where 
\begin{align*}
A_{-1}=1=A'_{-1}&, \quad B_{-1}=0=B'_{-1},\\
A_{-2}=0=A'_{-2}&, \quad B_{-2}=1=-B'_{-2}.\\
\end{align*}
and for $n\geq -1$, 
\begin{align*}
A_{n+1}=q_{n+1}A_n+\epsilon_{n+1}A_{n-1}, &\quad B_{n+1}=q_{n+1}B_n+\epsilon_{n+1}B_{n-1}\\
A'_{n+1}=q'_{n+1}A'_n-A'_{n-1}, &\quad B'_{n+1}=q'_{n+1}B'_n-B'_{n-1},\\
\end{align*}
where $\epsilon_0=1$.  Then
\begin{equation}
q'_n=t_nq_n, \quad\xi'_n=t_n\xi_n,\quad n\geq 0,\label{eq:1}
\end{equation}
 where $t_0=1$ and $t_n=(-1)^n\epsilon_1\cdots\epsilon_n$, if $n\geq 1$.
\begin{equation}
A'_n=s_nA_n,\quad B'_n=s_nB_n,\quad n\geq -2,\label{eq:2}
\end{equation}
where  $s_{-2}=-1, s_{-1}=1$ and $s_{n+1}=-s_{n-1}\epsilon_{n+1}$ for $n\geq -1$.
\end{lemma}
\begin{remark}  It follows that $s_0=1$ and
\begin{align}
s_{2i}&=(-1)^i\epsilon_{2i}\epsilon_{2i-2}\cdots\epsilon_2, \quad  \mbox{ if }i\geq 1,\\
s_{2i+1}&=(-1)^{i+1}\epsilon_{2i+1}\epsilon_{2i-1}\cdots\epsilon_1, \quad\mbox{ if } i\geq 0,\\
s_{n+1}s_n&=t_{n+1}, \quad\mbox{ if } n\geq -1.
\end{align}
\end{remark}
\begin{proof}
We prove \eqref{eq:1} by induction on $n\geq 0$.  These are true when $n=0$.  So we assume that
$n\geq 0$ and \eqref{eq:1} hold.  Then
\begin{align}
\xi'_{n+1}=\frac{1}{q'_n-\xi'_n}, &\quad \xi_{n+1}=\frac{\epsilon_{n+1}}{q_n-\xi_n},\\
q'_n=[\xi'_n],&\quad q_n=[\xi_n],
\end{align}
 where $[x]$ denotes the nearest integer to $x$.  Then 
\begin{align*}
\xi'_{n+1}&=\frac{1}{t_nq_n-t_n\xi_n}\\
          &=\frac{t_n}{q_n-\xi_n}=t_n(-\epsilon_{n+1}\xi_{n+1})\\
          &=t_{n+1}\xi_{n+1}.
\end{align*}
Next, 
\[
q'_{n+1}=[\xi'_{n+1}]=[t_{n+1}\xi_{n+1}]=t_{n+1}[\xi_{n+1}]=t_{n+1}q_{n+1}.
\]
Finally, we prove \eqref{eq:2} by induction on $n\geq -2$.  These hold for $n=-2$ and $-1$.  So we assume $n\geq -1$ and 
\[
A'_{n-1}=s_{n-1}A_{n-1},\quad B'_{n-1}=s_{n-1}B_{n-1},\quad
A'_n=s_nA_n,\quad B'_n=s_nB_n.
\]
Then
\begin{align*}
A'_{n+1}&=q'_{n+1}A'_n-A'_{n-1}\\
        &=(t_{n+1}q_{n+1})(s_nA_n)-s_{n-1}A_{n-1}\\
        &=q_{n+1}s_{n+1}A_n-(-s_{n+1}\epsilon_{n+1})A_{n-1}\\
        &=s_{n+1}(q_{n+1}A_n+\epsilon_{n+1}A_{n-1})\\
        &=s_{n+1}A_{n+1}.
\end{align*}
Similarly $B'_{n+1}=s_{n+1}B_{n+1}$.
\end{proof}
\begin{corollary}\label{corollary1}
Suppose $\xi_n,\ldots,\xi_{n+k-1}$ is a least period of \mbox{\rm NICF-P }complete quotients for a quadratic
 irrational $\xi_0$.
\begin{enumerate}
\item[(a)] If $\epsilon_{n+1}\cdots\epsilon_{n+k}=(-1)^k$, then 
\[
\xi'_n,\ldots,\xi'_{n+k-1}
\]
 is a least period of \mbox{\rm NICF-H }complete quotients for $\xi_0$.
\item[(b)] If $\epsilon_{n+1}\cdots\epsilon_{n+k}=(-1)^{k+1}$, then 
\begin{equation}
\xi'_n,\ldots,\xi'_{n+k-1},-\xi'_n,\ldots,-\xi'_{n+k-1}\label{eq:least_period}
\end{equation}
 is a least period of \mbox{\rm NICF-H }complete quotients for $\xi_0$.  Moreover
\[
\xi_0=q'_0-\ccfrac{1}{q'_1}-\cdots-\ccfrac{1}{\underset{*}{q'_n}}-\cdots-\ccfrac{1}{q'_{n+k-1}}
-\ccfrac{1}{-q'_n}-\cdots-\ccfrac{1}{-\underset{*}{q'_{n+k-1}}},
\]
where the asterisks correspond to the least period \eqref{eq:least_period}.
\end{enumerate}
\end{corollary}
\begin{proof}
Suppose $\xi_n,\ldots,\xi_{n+k-1}$ is a least period of \mbox{\rm NICF-P }complete quotients for $\xi_0$.  
Then $\xi_n=\xi_{n+k}$.  Hence  from \eqref{eq:1}, 
\begin{align}
t_n\xi'_n&=t_{n+k}\xi'_{n+k} \nonumber\\
(-1)^n\epsilon_1\cdots\epsilon_n\xi'_n&=(-1)^{n+k}\epsilon_1\cdots\epsilon_{n+k}\xi'_{n+k}\nonumber \\
\xi'_n&=(-1)^k\epsilon_{n+1}\cdots\epsilon_{n+k}\xi'_{n+k}.\label{eq:3}
\end{align}
(a) Suppose $\epsilon_{n+1}\cdots\epsilon_{n+k}=(-1)^k$. Then \eqref{eq:3} gives
\[
\xi'_n=\xi'_{n+k}.
\]
Then because $\xi'_n,\ldots,\xi'_{n+k-1}$ are distinct, they form a least period of complete quotients for the NICF-H 
expansion of $\xi_0$.

\noindent
(b) Suppose $\epsilon_{n+1}\cdots\epsilon_{n+k}=(-1)^{k+1}$. Then \eqref{eq:3} gives
\[
\xi'_n=-\xi'_{n+k}.
\]
Similarly
\[
\xi'_{n+1}=-\xi'_{n+k+1},\ldots,\xi'_{n+k-1}=-\xi'_{n+2k-1}.
\]
Also $\xi'_n=-\xi'_{n+k}=-(-\xi'_{n+2k})=\xi'_{n+2k}$.  Hence 
\begin{equation}
\xi'_n,\ldots,\xi'_{n+k-1},\xi'_{n+k},\ldots,\xi'_{n+2k-1}\label{eq:4}
\end{equation}
form a period of complete quotients for the NICF-H expansion of $\xi_0$.  However sequence \eqref{eq:4} is  identical with
\[
\xi'_n,\ldots,\xi'_{n+k-1},-\xi'_n,\ldots,-\xi'_{n+k-1},
\]
whose members are distinct.  Hence \eqref{eq:4} form a least period of complete quotients for the NICF-H expansion of $\xi_0$.
\end{proof}
\begin{corollary} Let $k$ and $p$ be the period-lengths of the \mbox{\rm NICF-P} and \mbox{\rm RCF} expansions of a quadratic irrational $\xi_0$ not equivalent to $(1+\sqrt{5})/2$. Then
\begin{enumerate}
\item[(a)] if $p$ is even, the period-length of the \mbox{\rm NICF-H} expansion of $\xi_0$ is equal to $k$;
\item[(b)] if $p$ is odd, the period-length of the \mbox{\rm NICF-H} expansion of $\xi_0$ is equal to $2k$ and the NICF-H expansion has the form
\[
\xi_0=q'_0-\ccfrac{1}{q'_1}-\cdots-\ccfrac{1}{\underset{*}{q'_n}}-\cdots-\ccfrac{1}{q'_{n+k-1}}
-\ccfrac{1}{-q'_n}-\cdots-\ccfrac{1}{-\underset{*}{q'_{n+k-1}}} .
\]
\end{enumerate}
\end{corollary}  
\begin{proof} Let $\xi_n,\ldots,\xi_{n+k-1}$  be a least period of NICF-P complete quotients.  Suppose that $r$ of the partial numerators $\epsilon_{n+1},\ldots,\epsilon_{n+k}$ of the NICF-P expansion of $\xi_0$ are equal to $-1$.  Now by Theorem 4 of Matthews and Robertson \cite{matthews-robertson}, $p=k+r$ and hence
\[
\epsilon_{n+1}\cdots\epsilon_{n+k}=(-1)^r=(-1)^{k+p}.
\]
Then according as $p$ is even or odd, $\epsilon_{n+1}\cdots\epsilon_{n+k}=(-1)^k$ or $(-1)^{k+1}$ and Corollary \ref{corollary1} applies.
\end{proof}
\begin{remark}
This result was obtained by Hurwitz and Minnegerode for the special case $\xi_0=\sqrt{D}$.
\end{remark}
We give some examples.
\begin{enumerate}
\item[(1)] $\xi_0=(12+\sqrt{1792})/16$, (Tables 1 and 2).
\begin{table}[t]
\caption{NICF-P expansion for $(12+\sqrt{1792})/16$}
\begin{tabular}{|r|c|r|c|c|}\hline
%\multicolumn{5}{|c|}{NICF-P for $(20+\sqrt{112})/16$}\\ \hline
$i$ &  $\xi_i$ & $\epsilon_i$ & $b_i$ &$A_i/B_i$\\ \hline
$0$ & $\cqu{12}{16}{1792}$ & $1$ & $3$ & $3/1$\\
$1$ & $\cqu{36}{31}{1792}$ & $1$ & $3$ & $10/3$\\
$2$ & $\cqu{57}{47}{1792}$ & $-1$ & $2$ & $17/5$\\
$3$ & $\cqu{37}{9}{1792}$ & $1$ & $9$ & $163/48$\\
$4$ & $\cqu{44}{16}{1792}$ & $-1$ & $5$ & $798/235$\\
$5$ & $\cqu{36}{31}{1792}$ & $1$ & $3$ & $2557/753$\\\hline
\end{tabular}
\end{table}
\begin{table}[t]
\caption{NICF-H expansion for $(12+\sqrt{1792})/16$}
\begin{tabular}{|r|c|r|c|c|}\hline
%\multicolumn{5}{|c|}{NICF-P for $(20+\sqrt{112})/16$}\\ \hline
$i$ &  $\xi_i$ & $\epsilon_i$ & $b_i$ &$A_i/B_i$\\ \hline
$0$ & $\cqu{12}{16}{1792}$ & $-1$ & $3$ & $3/1$\\
$1$ & $\cqu{36}{-31}{1792}$ & $-1$ & $-3$ & ${-10}/{-3}$\\
$2$ & $\cqu{57}{-47}{1792}$ & $-1$ & $-2$ & $17/5$\\
$3$ & $\cqu{37}{9}{1792}$ & $-1$ & $9$ & $163/48$\\
$4$ & $\cqu{44}{16}{1792}$ & $-1$ & $5$ & $798/235$\\
$5$ & $\cqu{36}{-31}{1792}$ & $-1$ & $-3$ & ${-2557}/{-753}$\\\hline
\end{tabular}
\end{table}
Here $k=4, r=2$, $\xi_1,\xi_2,\xi_3,\xi_4$ form a period of NICF-P complete quotients, 
$
\epsilon_2\epsilon_3\epsilon_4\epsilon_5=(-1)(1)(-1)(1)=1=(-1)^k
$ and the NICF-P and NICF-H expansions have the same period-length. Also $p=6$.
\item[(2)]  $\xi_0=(5+\sqrt{13})/4$,  (Table 3 and 4).
\begin{table}[t]
\caption{NICF-P expansion for $(5+\sqrt{13})/4$}
\begin{tabular}{|r|c|r|c|c|}\hline
%\multicolumn{5}{|c|}{NICF-P for $(20+\sqrt{112})/16$}\\ \hline
$i$ &  $\xi_i$ & $\epsilon_i$ & $b_i$ &$A_i/B_i$\\ \hline
$0$ & $\cqu{5}{4}{13}$ & $1$ & $2$ & $2/1$\\
$1$ & $\cqu{3}{1}{13}$ & $1$ & $7$ & $15/7$\\
$2$ & $\cqu{4}{3}{13}$ & $-1$ & $3$ & $43/20$\\
$3$ & $\cqu{5}{4}{13}$ & $-1$ & $2$ & $71/33$\\ \hline
\end{tabular}
\end{table}
\begin{table}[t]
\caption{NICF-H expansion for $(5+\sqrt{13})/4$}
\begin{tabular}{|r|c|r|c|c|}\hline
%\multicolumn{5}{|c|}{NICF-P for $(20+\sqrt{112})/16$}\\ \hline
$i$ &  $\xi_i$ & $\epsilon_i$ & $b_i$ &$A_i/B_i$\\ \hline
$0$ & $\cqu{5}{4}{13}$ & $1$ & $2$ & $2/1$\\
$1$ & $\cqu{3}{-1}{13}$ & $-1$ & $-7$ & $-15/{-7}$\\
$2$ & $\cqu{4}{-3}{13}$ & $-1$ & $-3$ & $43/20$\\
$3$ & $\cqu{5}{-4}{13}$ & $-1$ & $-2$ & $-71/{-33}$\\ 
$4$ & $\cqu{3}{1}{13}$ & $-1$ & $7$ & $-540/{-251}$\\
$5$ & $\cqu{4}{3}{13}$ & $-1$ & $3$ & $-1549/{-720}$\\
$6$ & $\cqu{5}{4}{13}$ & $-1$ & $2$ & $-2558/{-1189}$\\\hline
\end{tabular}
\end{table}
Here $k=3, r=2$ and $\xi_0,\xi_1,\xi_2$ form a period of NICF-P complete quotients, 
$
\epsilon_1\epsilon_2\epsilon_3=(1)(-1)(-1)=1=(-1)^{k+1}
$ and the NICF-H period-length is twice the NICF-P period-length.  Also $p=5$.
%\item[(3)]
%\begin{align*}
%\sqrt{21}&=5-\ccfrac{1}{\underset{*}{2}}+\ccfrac{1}{3}-\ccfrac{1}{2}+\ccfrac{1}{\underset{*}{9}} \quad( \mbox{\rm NICF-P}),\\
%\sqrt{21}&=5-\ccfrac{1}{\underset{*}{2}}-\ccfrac{1}{-3}-\ccfrac{1}{-2}-\ccfrac{1}{\underset{*}{9}} \quad( \mbox{\rm NICF-H}).
%\end{align*}
%The RCF period-length is $6$.
%\item[(4)]
%\begin{align*}
%\sqrt{13}&=4-\ccfrac{1}{\underset{*}{3}}-\ccfrac{1}{2}+\ccfrac{1}{\underset{*}{7}} \quad( \mbox{\rm NICF-P}),\\
%\sqrt{13}&=4-\ccfrac{1}{\underset{*}{3}}-\ccfrac{1}{2}-\ccfrac{1}{{-7}}-\ccfrac{1}{{-3}}-\ccfrac{1}{{-2}}-\ccfrac{1}{\underset{*}{7}} \quad( \mbox{\rm NICF-H)}.
%\end{align*}
%The RCF period-length is $5$.
\end{enumerate}
\section{NICF-P midpoint criteria for Pell's equation}\label{section3}
\begin{theorem}\label{theorem1}
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}$:
\begin{enumerate}
\item[1)] $P_\rho=P_{\rho+1}$, $k=2\rho, p=2h$.  Then
\begin{align*}
A_{k-1}&=B_{\rho-1}A_\rho+\epsilon_\rho A_{\rho-1}B_{\rho-2},\\
B_{k-1}&=B_{\rho-1}(B_\rho+\epsilon_\rho B_{\rho-2}).
\end{align*}
\item[2)]$P_{\rho+1}=P_{\rho}+Q_\rho$, $k=2\rho, p=2h$. Then
\begin{align*}
A_{k-1}&=B_{\rho-1}A_\rho+A_{\rho-1}B_{\rho-2}-A_{\rho-1}B_{\rho-1},\\
B_{k-1}&=B_{\rho-1}(B_\rho+B_{\rho-2}-B_{\rho-1}).
\end{align*}
\item[3)] $Q_{\rho}=Q_{\rho+1}$ and
\begin{align*}
{\rm (a)\quad} \epsilon_{\rho+1}&=-1, k=2\rho+1, p=2h, \mbox{ or}\\
{\rm (b)\quad} \epsilon_{\rho+1}&=1, k=2\rho+1, p=2h-1.
\end{align*}  Then
\begin{align*}
A_{k-1}&=A_{\rho}B_\rho+\epsilon_{\rho+1}A_{\rho-1}B_{\rho-1},\\
B_{k-1}&=B_{\rho}^2+\epsilon_{\rho+1}B_{\rho-1}^2.
\end{align*}
\item[4)] $P_{\rho+1}=Q_{\rho}+{\half}Q_{\rho+1}, \epsilon_{\rho+1}=-1, k=2\rho+1, p=2h-1$.  Then
\begin{align*}
A_{k-1}&=A_{\rho}B_\rho+2A_{\rho-1}B_{\rho-1}-(A_{\rho}B_{\rho-1}+B_{\rho}A_{\rho-1}),\\
B_{k-1}&=B_{\rho}^2+2B_{\rho-1}^2-2B_{\rho}B_{\rho-1}.
\end{align*}
\item[5)] $P_{\rho}=Q_{\rho}+{\half}Q_{\rho-1}, \epsilon_{\rho}=-1, k=2\rho, p=2h-1$.  Then
\begin{align*}
A_{k-1}&=2A_{\rho-1}B_{\rho-1}+A_{\rho-2}B_{\rho-2}-(A_{\rho-1}B_{\rho-2}+B_{\rho-1}A_{\rho-2})\\
B_{k-1}&=2B_{\rho-1}^2+B_{\rho-2}^2-2B_{\rho-1}B_{\rho-2}.
\end{align*}
\end{enumerate}
\end{theorem}

\begin{proof} We only exhibit the calculations for criterion 1) of Theorem \ref{theorem1}. This corresponds to criterion 1) of Theorem 6, Williams \cite[p. 12]{hcw}, which states that $P'_\rho=P'_{\rho+1}$, $k=2\rho$, $p=2h$ and
\begin{align}
|A'_{k-1}|&=|B'_{\rho-1}A'_\rho-A'_{\rho-1}B'_{\rho-2}|,\label{eq:5}\\
|B'_{k-1}|&=|B'_{\rho-1}(B'_\rho-B'_{\rho-2})|. \label{eq:6}
\end{align}
Then from equations \eqref{eq:2},
\begin{align*}
B'_{\rho-1}A'_\rho-A'_{\rho-1}B'_{\rho-2}&=s_{\rho-1}s_{\rho}B_{\rho-1}A_\rho-s_{\rho-1}s_{\rho-2}A_{\rho-1}B_{\rho-2}\\
                                         &=t_{\rho}B_{\rho-1}A_\rho-t_{\rho-1}A_{\rho-1}B_{\rho-2}\\
                                         &=-t_{\rho-1}\epsilon_{\rho}B_{\rho-1}A_\rho-t_{\rho-1}A_{\rho-1}B_{\rho-2}\\
                                         &=-t_{\rho-1}\epsilon_\rho(B_{\rho-1}A_\rho+\epsilon_{\rho}A_{\rho-1}B_{\rho-2}).
\end{align*}
Hence
\begin{equation}
|B'_{\rho-1}A'_\rho-A'_{\rho-1}B'_{\rho-2}|=B_{\rho-1}A_\rho+\epsilon_{\rho}A_{\rho-1}B_{\rho-2} \label{eq:7}
\end{equation}
as $B_{\rho-1}A_\rho\geq A_{\rho-1}B_{\rho-2}$.  Hence \eqref{eq:5} and \eqref{eq:7} give the first result of criterion 1) above.  
Next, 
\begin{align*}
B'_{\rho-1}(B'_\rho-B'_{\rho-2})&=s_{\rho-1}B_{\rho-1}(s_{\rho}B_\rho-s_{\rho-2}B_{\rho-2})\\
                               &=B_{\rho-1}(t_{\rho}B_\rho-t_{\rho-1}B_{\rho-2})\\
                               &=B_{\rho-1}(-t_{\rho-1}\epsilon_{\rho}B_\rho-t_{\rho-1}B_{\rho-2})\\
                               &=-t_{\rho-1}\epsilon_{\rho}B_{\rho-1}(B_\rho+\epsilon_{\rho}B_{\rho-2}).
\end{align*}
Hence
\begin{equation}
|B'_{\rho-1}(B'_\rho-B'_{\rho-2})|=B_{\rho-1}(B_\rho+\epsilon_{\rho}B_{\rho-2}) \label{eq:8}
\end{equation}
and \eqref{eq:6} and \eqref{eq:8} give the second result of criterion 1) above.
\end{proof}
\begin{remark}
John Robertson in an email to the author, dated November 26, 2007, noted the following errors in Williams \cite[pp. 12--13]{hcw}:
\begin{enumerate}
\item[(i)] Criterion 3), Theorem 6, page 12, should be
\begin{align*}
|A'_{\pi-1}|&=A'_{\rho}B'_\rho-A'_{\rho-1}B'_{\rho-1},\\
|B'_{\pi-1}|&={B'_{\rho}}^2-{B'}_{\rho-1}^2.
\end{align*}
\item[(ii)] Criterion 6), Theorem 7, page 13, should be
\begin{align*}
|A'_{\pi-1}|&=2A'_{\rho-1}B'_{\rho-1}+A'_{\rho-2}B'_{\rho-2}-|A'_{\rho-1}B'_{\rho-2}+B'_{\rho-1}A'_{\rho-2}|,\\
|B'_{\pi-1}|&=2{B'}_{\rho-1}^2+{B'}_{\rho-2}^2-2|B'_{\rho-2}B'_{\rho-1}|.
\end{align*}
\end{enumerate}
\end{remark}
\section{Midpoint criteria in terms of unisequences}\label{section4}
The RCF of $\sqrt{D}$, with period-length $p$, has the form
\begin{equation}
\sqrt{D}=\left\{\begin{array}{ll}
[a_0,\overline{a_1,\ldots,a_{h-1},a_{h-1}\ldots,a_1,2a_0}] & \mbox{ if $p=2h-1$;}\\
\protect[a_0,\overline{a_1,\ldots,a_{h-1},a_h,a_{h-1},\ldots,a_1,2a_0}\protect] & \mbox{ if $p=2h$.}
\end{array}
\right.\label{eq:sqrtD_RCF}
\end{equation}

We have Euler's midpoint formulae for solving Pell's equation $x^2-Dy^2=\pm 1$ using the regular continued fraction (see Dickson \cite[p. 358]{dickson}):
\begin{align*}
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,
\end{align*} 
if $p=2h-1$;
\begin{align*}
P_h&=P_{h+1},\\
A_{2h-1}&=A_hB_{h-1}+A_{h-1}B_{h-2},\\
B_{2h-1}&=B_{h-1}(B_h+B_{h-2}),
\end{align*} 
if $p=2h$.  We also need the following symmetry properties from Perron \cite[p. 81]{perron}:
\begin{align}
a_t&=a_{p-t},\quad t=1,2,\ldots,p-1,\label{RCFsymmetry1}\\
P_{t+1}&=P_{p-t},\quad t=0,1,\ldots,p-1,\label{RCFsymmetry2}\\
Q_t&=Q_{p-t},\quad t=0,1,\ldots,p.\label{RCFsymmetry3}
\end{align}
\begin{theorem}\label{theorem2} Using the notation of \eqref{eq:sqrtD_RCF}, in relation to Theorem \ref{theorem1}, we have
\begin{enumerate}
\item[(1)] If $p=2h-1, h>1$ and $a_{h-1}>1$, or $p=1$, we get {\rm criterion 3)}.
\item[(2)] If $p=2h, h>1$ and $a_{h-1}>1, a_h>1$, or $p=2$ and $a_1>1$, we get {\rm criterion 1)}.
\item[(3)] Suppose $p=2h$ and $a_{h-1}=1, a_h>1$, so that $a_h$ is enclosed by two $M$-unisequences. Then
\begin{enumerate}
\item[(a)]  if $M\geq 2$ is even, we get {\rm criterion 2)}.
\item[(b)]  if $M$ is odd, we get {\rm criterion 1)}.
\end{enumerate}
\item[(4)] Suppose the centre of a period contains an $M$-unisequence, $M\geq 1$.
\begin{enumerate}
\item[(a)] If $M$ is odd, then $p=2h$ and we get {\rm criterion 1)} if $M=4t+3$, {\rm criterion 3)} if $M=4t+1$.
\item[(b)] If $M$ is even, then $p=2h-1$ and we get {\rm criterion 4)} if $M=4t$, {\rm criterion 5)} if $M=4t+2$.
\end{enumerate}
\end{enumerate}
\end{theorem}
Before we can prove Theorem \ref{theorem2}, we need some results on the RCF to NICF-P conversion.
\section{The RCF to NICF-P conversion and its properties}\label{section5}
\begin{lemma}\label{lemma_singularization}
Let $\xi_0=\cqu{P_0}{Q_0}{D}$ have NICF-P and RCF expansions:
\[
\xi_0=a'_{0}+\frac{\epsilon_1|}{|a'_1}+\cdots=a_0+\frac{1|}{|a_1}+\cdots,
\]
with complete quotients $\xi'_m, \xi_m$, respectively.  Define $f(m)$ recursively for $m\geq 0$ by $f(0)=0$ and
\begin{equation}
f(m+1)=
\begin{cases}
f(m)+1, &\text{if $\epsilon_{m+1}=1$;}\\
f(m)+2, &\text{if $\epsilon_{m+1}=-1$.}
\end{cases}\label{eq:fm}
\end{equation}
Then for $m\geq 0$,
\begin{equation}
\epsilon_{m+1}=
\begin{cases}
1, &\text{if $a_{f(m)+1}>1$;}\\
-1, &\text{if $a_{f(m)+1}=1$,}
\end{cases}\label{eq:epsilon}
\end{equation}
\begin{equation}
\xi'_{m}=
\begin{cases}
\xi_{f(m)}, &\text{if $\epsilon_{m}=1$;}\\
\xi_{f(m)}+1, &\text{if $\epsilon_{m}=-1$,}
\end{cases}\label{eq:xi}
\end{equation}
\begin{equation}
a'_{m}=
\begin{cases}
a_{f(m)}, &\text{if $\epsilon_{m}=1$ and $\epsilon_{m+1}=1$;}\\
a_{f(m)}+1, &\text{if $\epsilon_{m}\epsilon_{m+1}=-1$;}\\
a_{f(m)}+2, &\text{if $\epsilon_{m}=-1$ and $\epsilon_{m+1}=-1$.}\label{eq:adef1}
\end{cases}
\end{equation}
\end{lemma}
\begin{proof} See Theorem 2, Matthews and Robertson \cite{matthews-robertson}.
\end{proof}
\begin{remark} By virtue of \eqref{eq:fm} and \eqref{eq:xi}, we say that the $\xi'_m$ are obtained from the $\xi_n$ in {\em jumps} of $1$ or $2$.
\end{remark}
\begin{lemma}\label{nearest_integer}{\em
Let $\xi_0=(a_0,a_1,\ldots)$ be an RCF expansion.  Then if $[x]$ denotes the nearest integer to $x$, we have 
\[
[\xi_n]=\begin{cases}
a_n, &\text{if $a_{n+1}>1$;}\\
a_n+1, &\text{if $a_{n+1}=1$.}
\end{cases}
\]}
\end{lemma}
\begin{proof}
If $[\xi_n]=a_n+1$, then $\xi_n>a_n+\frac12$ and hence $a_{n+1}=1$, whereas if 
 $[\xi_n]=a_n$, then $\xi_n<a_n+\frac12$ and hence $a_{n+1}>1$.
\end{proof}
\begin{lemma}\label{lemmaA} Let $\xi_0=\cqu{P_0}{Q_0}{D}$ have NICF-P expansion
\[
\xi_0=a'_0+\frac{\epsilon_1|}{|a'_1}+\cdots.
\]
Then
\begin{equation}
A'_m=
\begin{cases}
A_{f(m)} &\text{if $\epsilon_{m+1}=1$;}\\
A_{f(m)+1} &\text{if $\epsilon_{m+1}=-1$,}
\end{cases}\label{eq:A_m}
\end{equation}
 where $f(m)$ is defined by \eqref{eq:fm}.
Equivalently, in the notation of Bosma \cite[p. 372]{bosma}, if $n(k)=f(k+1)-1$ for $k\geq -1$, then
\begin{equation}
n(k)=
\begin{cases}
n(k-1)+1, &\text{if $\epsilon_{k+1}=1$;}\\
n(k-1)+2, &\text{if $\epsilon_{k+1}=-1$}
\end{cases}\label{eq:nk}
\end{equation}
and \eqref{eq:A_m} has the simpler form
\begin{equation}
A'_k=A_{n(k)}\text{ for $k\geq 0$}.\label{eq:aknk}
\end{equation}
\end{lemma}
\begin{remark} From \eqref{eq:epsilon} and \eqref{eq:nk}, we see that $\epsilon_{m+1}=-1$ implies $a_{n(m)}=1$.
\end{remark}
\begin{proof} (by induction).  We first prove \eqref{eq:aknk} for $k=0$.
We use Lemma \ref{nearest_integer}.
\begin{align*}
\epsilon_1=1\implies a_1>1&\implies [\xi_0]=a_0\\
                          &\implies A'_0=A_0.\\
\epsilon_1=-1\implies a_1=1&\implies [\xi_0]=a_0+1=a_0a_1+1\\
                          &\implies A'_0=A_1.
\end{align*}
We next prove \eqref{eq:aknk} for $k=1$.  We have to prove
\[
A'_1=\begin{cases}
A_{f(1)} &\text{ if $\epsilon_2=1$;}\\
A_{f(1)+1} &\text{ if $\epsilon_2=-1$,}
\end{cases}
\]
where
\[
f(1)=
\begin{cases}
1 &\text{ if $\epsilon_{1}=1$;}\\
2 &\text{ if $\epsilon_{1}=-1$}.
\end{cases}
\]
i.e.,
\[
A'_1=\begin{cases}
A_1 & \text{ if $\epsilon_1=1, \epsilon_2=1$;}\\
A_2 & \text{ if $\epsilon_1\epsilon_2=-1$;}\\
A_3 & \text{ if $\epsilon_1=-1, \epsilon_2=-1$.}
\end{cases}
\]
Now $A'_1=a'_0a'_1+\epsilon_1$.  We have
\[
a'_0=\begin{cases}
a_0 & \text{ if $\epsilon_1=1$;}\\
a_0+1 & \text{ if $\epsilon_1=-1$}
\end{cases}
\]
and
\[
a'_1=\begin{cases}
a_{f(1)} & \text{ if $\epsilon_1=1=\epsilon_2$;}\\
a_{f(1)}+1 & \text{ if $\epsilon_1\epsilon_2=-1$;}\\
a_{f(1)}+2 &\text{ if $\epsilon_1=-1=\epsilon_2$}.
\end{cases}
\]
Hence
\[
a'_1=\begin{cases}
a_1   & \text{ if $\epsilon_1=1=\epsilon_2$;}\\
a_1+1 & \text{ if $\epsilon_1=1, \epsilon_2=-1$;}\\
a_2+1 & \text{ if $\epsilon_1=-1, \epsilon_2=1$;}\\
a_2+2 & \text{ if $\epsilon_1=-1, \epsilon_2=-1$}.
\end{cases}
\]

\noindent
Case 1. $\epsilon_1=1=\epsilon_2$.  Then $A'_1=a_0a_1+1=A_1.$

\noindent
Case 2. $\epsilon_1=1, \epsilon_2=-1$.  Then $a_2=1$ and
\begin{align*}
A'_1&=a_0(a_1+1)+1,\\
A_2&=(a_0a_1+1)a_2+a_0=a_0a_1+1+a_0=A'_1.
\end{align*}
Case 3.  $\epsilon_1=-1, \epsilon_2=1$. Then $a_1=1$ and
\begin{align*}
A'_1&=(a_0+1)(a_2+1)-1\\
    &=a_0a_2+a_0+a_2,\\
A_2&=(a_0a_1+1)a_2+a_0\\
&=(a_0+1)a_2+a_0=A'_1.
\end{align*}
Case 4.  $\epsilon_1=-1=\epsilon_2$. Then $a_1=1=a_3$ and
\begin{align*}
A'_1&=(a_0+1)(a_2+2)-1\\
    &=a_0a_2+a_2+2a_0+1.
\end{align*}
Also
\begin{align*}
A_3&=a_3A_2+A_1\\
   &=A_2+A_1\\
   &=((a_0a_1+1)a_2+a_0)+(a_0a_1+1)\\
   &=((a_0+1)a_2+a_0)+(a_0+1)=A'_1.
\end{align*}
 Finally, let $k\geq 0$ and assume \eqref{eq:aknk} holds for $k$ and $k+1$ and use the equation
\[
A'_{k+2}=a'_{k+2}A'_{k+1}+\epsilon_{k+2}A'_k.
\]
Then from \eqref{eq:adef1}, with $j=n(k+1)+1$, we have
\begin{equation}
a'_{k+2}=
\begin{cases}
a_j   &\text{ if $\epsilon_{k+2}=1, \epsilon_{k+3}=1$;}\\
a_j+1 &\text{ if $\epsilon_{k+2}\epsilon_{k+3}=-1$;}\\
a_j=2 &\text{ if $\epsilon_{k+2}=-1=\epsilon_{k+3}$.}
\end{cases}\label{eq:adef2}
\end{equation}
Case 1. Suppose $\epsilon_{k+2}=1=\epsilon_{k+3}=1$.  Then 
\[
n(k+1)=n(k)+1=j-1,\quad n(k+2)=n(k+1)+1=j
\]
and
\[
A'_{k+2}=a_jA_{j-1}+A_{j-2}=A_j=A_{n(k+2)}.
\]
Case 2. Suppose $\epsilon_{k+2}=1, \epsilon_{k+3}=-1$.  Then 
\[
n(k+1)=n(k)+1=j-1,\quad n(k+2)=n(k+1)+2=j+1
\]
and
\[
A'_{k+2}=(a_j+1)A_{j-1}+A_{j-2}.
\]
Now $\epsilon_{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 $\epsilon_{k+2}=-1, \epsilon_{k+3}=1$.  Then 
\[
n(k+1)=n(k)+2=j-1,\quad n(k+2)=n(k+1)+1=j
\]
and
\[
A'_{k+2}=(a_j+1)A_{j-1}-A_{j-3}.
\]
Now $\epsilon_{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_jA_{j-1}+A_{j-2}=A_j=A_{n(k+2)}.
\]
Case 4. Suppose $\epsilon_{k+2}=-1=\epsilon_{k+3}$.  Then 
\[
n(k+1)=n(k)+2=j-1,\quad n(k+2)=n(k+1)+2=j+1
\]
and
\[
A'_{k+2}=(a_j+2)A_{j-1}-A_{j-3}.
\]
Now $\epsilon_{k+3}=-1\implies 1=a_{n(k+2)}=a_{j+1}$
and $\epsilon_{k+2}=-1\implies 1=a_{n(k+1)}=a_{j-1}$, so
\[
A_{j+1}=A_j+A_{j-1} \text{ and } A_{j-1}=A_{j-2}+A_{j-3}.
\]
Hence
\begin{align*}
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)}.
\end{align*}
\end{proof}
\begin{lemma}\label{lemma:hit}
Each $a_n>1$, $n\geq 1$ will be visited by the algorithm of Lemma \ref{lemma_singularization}, i.e., there exists an $m$ such that $n=f(m)$. 
\end{lemma}
\begin{proof} Let $a_n>1$ and  $f(m)\leq n<f(m+1)$. If $f(m)<n$, then $f(m+1)=f(m)+2$ and $\epsilon_{m+1}=-1$; also $n=f(m)+1$. 
Then from \eqref{eq:epsilon}, $a_n=a_{f(m)+1}=1$.
\end{proof}
Note that in the RCF to NICF-P transformation, we have $f(k)=p$, where $k$ is the NICF-P period-length.
\begin{lemma}\label{lemmajumps}
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$.
\end{lemma}
\begin{proof}
Suppose the unisequences in $[a_r,a_s]$ have lengths $m_1,\ldots,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}, \text{ where }
 e_i=\begin{cases}
0 &\text{if $m_i$ is odd;}\\
1 &\text{if $m_i$ is even.}
\end{cases}
\]
Then
\begin{align*}
J&=\sum_{i=1}^Nj_i=\sum_{i=1}^N\frac{m_i+1+e_i}{2}\\
 &=\half(N+\sum_{i=1}^Nm_i)+\frac{E}{2}\\
 &=\frac{s-r}{2}+\frac{E}{2}=\frac{s-r+E}{2}.
\end{align*}
\end{proof}
\begin{corollary}\label{jump_symmetry} 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\leq p/2$.
\end{corollary}
\begin{proof} This follows from Lemma \ref{lemmajumps} and the symmetry of an RCF period.
\end{proof}
\noindent

\section{Proof of Theorem \ref{theorem2}}\label{section6}  We use the notation of Lemmas \ref{lemma_singularization} and \ref{lemmaA}.

\noindent
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}=[\rnode[t]{n0}{8},\underset{*}{1},\rnode[t]{n1}{1},\rnode[t]{n2}{5},\rnode[t]{n3}{5},1,\rnode[t]{n4}{1},\rnode[t]{n5}{\underset{*}{16}}]\ncarc{n0}{n1}\ncarc{n1}{n2}\ncarc{n2}{n3}\ncarc{n3}{n4}\ncarc{n4}{n5}$ or $\sqrt{89}=[\rnode[t]{n0}{9},\rnode[t]{n1}{\underset{*}{2}},\rnode[t]{n2}{3},\rnode[t]{n3}{3},\rnode[t]{n4}{2},\rnode[t]{n5}{\underset{*}{18}}]\ncarc{n0}{n1} \ncarc{n1}{n2} \ncarc{n2}{n3} \ncarc{n3}{n4} \ncarc{n4}{n5}$.  Let $f(m)=h-1$, where $m$ is the number of jumps in $[a_0,a_{h-1}]$.  Then $f(m+1)=h$ and
\begin{align*}
\xi'_m&=\xi_{h-1},\ \epsilon_m=1,\\
\xi'_{m+1}&=\xi_{h},\ \epsilon_{m+1}=1.
\end{align*}
By Corollary \ref{jump_symmetry}, $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 \ref{theorem1}.  Also
\begin{align*}
\epsilon_m=1&\implies f(m)=f(m-1)+1,\  A'_{m-1}=A_{f(m-1)},\\
\epsilon_{m+1}=1&\implies f(m+1)=f(m)+1,\  A'_{m}=A_{f(m)}.
\end{align*}
Hence $A'_{m-1}=A_{h-2},\ A'_{m}=A_{h-1},\ B'_{m-1}=B_{h-2},\ B'_{m}=B_{h-1}$ and
\begin{align*}
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}+\epsilon_{m+1}A'_{m-1}B'_{m-1}.
\end{align*}
Also 
\begin{align*}
B_{p-1}&=B_{h-1}^2+B_{h-2}^2\\
       &={B'}_{m}^2+{B'}_{m-1}^2\\
       &={B'}_{m}^2+\epsilon_{m+1}{B'}_{m-1}^2.
\end{align*}
If $p=1$, $\sqrt{D}=[a,\overline{2a}]$ and the NICF and RCF expansions are identical.  Also $Q'_0=Q'_1=1, \epsilon_1=1$ and we have criterion 3).

\noindent
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}=[\rnode[t]{n0}{10},\underset{*}{1},\rnode[t]{n1}{1},1,\rnode[t]{n2}{2},\rnode[t]{n3}{2},1,\rnode[t]{n4}{1},1,\rnode[t]{n5}{\underset{*}{20}}]\ncarc{n0}{n1}\ncarc{n1}{n2}\ncarc{n2}{n3}\ncarc{n3}{n4}\ncarc{n4}{n5}$.  Let $f(m)=h-1$.  Then $f(m+1)=h$ and
\begin{align*}
\xi'_m&=\xi_{h-1}+1,\ \epsilon_m=-1,\\
\xi'_{m+1}&=\xi_{h},\ \epsilon_{m+1}=1,
\end{align*}
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
\begin{align*}
\epsilon_m=-1&\implies f(m)=f(m-1)+2,\  A'_{m-1}=A_{f(m-1)+1},\\
\epsilon_{m+1}=1&\implies f(m+1)=f(m)+1,\  A'_{m}=A_{f(m)}.
\end{align*}
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}+\epsilon_{m+1}A'_{m-1}B'_{m-1}=A_{p-1} \mbox{ and }{B'}_{m}^2+\epsilon_{m+1}{B'}_{m-1}^2=B_{p-1}.
\]
\noindent
Case (2) Assume $p=2h, h>1, a_{h-1}>1, a_h>1$,  e.g., $\sqrt{92}=[\rnode[t]{n0}{9},\underset{*}{1},\rnode[t]{n1}{1},\rnode[t]{n2}{2},\rnode[t]{n3}{4},\rnode[t]{n4}{2},1,\rnode[t]{n5}{1},\rnode[t]{n6}{\underset{*}{18}}]\ncarc{n0}{n1} \ncarc{n1}{n2} \ncarc{n2}{n3} \ncarc{n3}{n4} \ncarc{n4}{n5}\ncarc{n5}{n6}$.  

\noindent
Let $f(m)=h$.  Then $f(m+1)=h+1$ and
\begin{align*}
\xi'_m&=\xi_h,\ \epsilon_m=1,\\
\xi'_{m+1}&=\xi_{h+1},\ \epsilon_{m+1}=1,
\end{align*}
Also by Corollary \ref{jump_symmetry}, $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 \ref{theorem1}. Also
\begin{align*}
\epsilon_m=1&\implies f(m)=f(m-1)+1,\  A'_{m-1}=A_{f(m-1)},\\
\epsilon_{m+1}=1&\implies f(m+1)=f(m)+1,\  A'_{m}=A_{f(m)}.
\end{align*}
Hence $A'_{m-1}=A_{h-1},\ A'_{m}=A_h$ and $B'_{m-1}=B_{h-1},\ B'_{m}=B_h$.  Then
\begin{align}
A_{p-1}&=A_hB_{h-1}+A_{h-1}B_{h-2}\notag\\
       &=A'_mB'_{m-1}+A'_{m-1}B_{h-2}.\label{eq:17}
\end{align}
But $B_{h-2}=B_h-a_hB_{h-1}=B'_m-a'_mB_{m-1}=B'_{m-2}$.  Hence \eqref{eq:17} gives 
\begin{align*}
A_{p-1}&=A'_mB'_{m-1}+A'_{m-1}B'_{m-2}\\
       &=A'_mB'_{m-1}+\epsilon_{m}A'_{m-1}B'_{m-2}.
\end{align*}
Also 
\begin{align*}
B_{p-1}&=B_{h-1}(B_h+B_{h-2})\\
       &=B'_{m-1}(B'_m+B'_{m-2}).
\end{align*}
Case (3)(a). Assume $p=2h$, with an even length unisequence each side of $a_h>1$,
e.g., $\sqrt{21}=[\rnode[t]{n0}{4},\underset{*}{1},\rnode[t]{n1}{1},\rnode[t]{n2}{2},1,\rnode[t]{n3}{1},\rnode[t]{n4}{\underset{*}{8}}]\ncarc{n0}{n1} \ncarc{n1}{n2} \ncarc{n2}{n3} \ncarc{n3}{n4}$.  Let $f(m)=h$. Then $f(m+1)=h+2$. As in Case(2), $k=2m$. Also
\begin{align*}
\xi'_m&=\xi_h,\ \epsilon_m=1,\\
\xi'_{m+1}&=\xi_{h+2}+1,\ \epsilon_{m+1}=-1.
\end{align*}
Then
\begin{align*}
\epsilon_m=1&\implies f(m)=f(m-1)+1,\  A'_{m-1}=A_{f(m-1)},\\
\epsilon_{m+1}=-1&\implies f(m+1)=f(m)+2,\  A'_{m}=A_{f(m)+1}.
\end{align*}
Hence $A'_{m-1}=A_{h-1},\ A'_{m}=A_{h+1}$ and $B'_{m-1}=B_{h-1},\ B'_{m}=B_{h+1}$. 

\noindent
We prove criterion 2) of Theorem \ref{theorem1}, $P'_{m+1}=P'_m+Q'_m$, i.e., $P_{h+2}+Q_{h+2}=P_h+Q_h.$ 

\noindent
We note  from Theorem 10.19, Rosen \cite{rosen}, that $a_{h+1}=1$ implies $P_{h+2}+P_{h+1}=Q_{h+1}$.  Also
\begin{align*}
P_{h+2}^2&=D-Q_{h+1}Q_{h+2},\\
P_{h+1}^2&=D-Q_{h}Q_{h+1}.
\end{align*}
Hence
\begin{align*}
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}).
\end{align*}
Hence
\begin{align}
P_{h+2}-P_{h+1}&=Q_h-Q_{h+2},\notag\\
P_{h+2}+Q_{h+2}&=P_{h+1}+Q_h\notag\\
               &=P_h+Q_h\label{eq:170}
\end{align}
We next prove
\begin{align}
A_{p-1}&=B'_{m-1}(A'_m-A'_{m-1})+A'_{m-1}B'_{m-2},\label{eq:18}\\
B_{p-1}&=B'_{m-1}(B'_m-B'_{m-1}+B'_{m-2}).\label{eq:19}
\end{align}
First note that by equations \eqref{eq:adef1},  $\epsilon_m=1$ and $\epsilon_{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
\begin{align*}
B_{h-2}&=B_h-a_hB_{h-1}\\
       &=(B'_m-B'_{m-1})-(a'_m-1)B'_{m-1}\\
       &=B'_m-a'_mB'_{m-1}=B'_{m-2}.
\end{align*}
Then 
\begin{align*}
A_{p-1}&=A_hB_{h-1}+A_{h-1}B_{h-2}\\
       &=(A'_m-A'_{m-1})B'_{m-1}+A'_{m-1}B'_{m-2},
\end{align*}
proving \eqref{eq:18}.  Also 
\begin{align*}
B_{p-1}&=B_{h-1}(B_h+B_{h-2})\\
       &=B'_{m-1}(B'_m-B'_{m-1}+B'_{m-2}),
\end{align*}
proving \eqref{eq:19}.

\medskip
\noindent
If $p=2$ and $a_1>1$, then $D=a^2+b, 1<b<2a, b$ dividing $2a$ (Rosen \cite[p. 389]{rosen}).  Then $\sqrt{D}=[\rnode[t]{n0}{a},\rnode[t]{n1}{\underset{*}{2a/b}},\rnode[t]{n2}{\underset{*}{2a}}] \ncarc{n0}{n1}\ncarc{n1}{n2}$ and the NICF and RCF expansions are identical. Then $\xi'_1=\cqu{a}{b}{D}, \xi'_2=a+\sqrt{D}, P'_1=P'_2=a, \epsilon_1=1$ and we have criterion 1).

\noindent
Case (3)(b). Assume $p=2h$, with an odd length unisequence each side of $a_h>1$,
 e.g., $\sqrt{14}=[\rnode[t]{n0}{3},\underset{*}{1},\rnode[t]{n1}{2},1,\rnode[t]{n2}{\underset{*}{6}}\ncarc{n0}{n1} \ncarc{n1}{n2}]$.
Let $f(m)=h$.  Then $f(m+1)=h+2$ and $k=2m$. Then
\begin{align*}
\xi'_m&=\xi_h+1,\ \epsilon_m=-1,\\
\xi'_{m+1}&=\xi_{h+2}+1,\ \epsilon_{m+1}=-1.
\end{align*}
  Then
\begin{align*}
\epsilon_m=-1&\implies f(m)=f(m-1)+2,\  A'_{m-1}=A_{f(m-1)+1},\\
\epsilon_{m+1}=-1&\implies f(m+1)=f(m)+2,\  A'_{m}=A_{f(m)+1}.
\end{align*}
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 \eqref{eq:170}, we get
\begin{align*}
P'_{m+1}=P_{h+2}+Q_{h+2}=P_h+Q_h=P'_m,
\end{align*}
which is criterion 1) of Theorem \ref{theorem1}.  

\noindent
As $\epsilon_m=-1$, it remains to prove
\begin{align*}
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}).
\end{align*}
First, $a_{h+1}=1$ implies $A_{h+1}=A_h+A_{h-1}$, i.e., $A'_m=A_h+A_{h-1}.$
  Also $\epsilon_m=-1=\epsilon_{m+1}$ implies $a'_m=a_{f(m)}+2=a_h+2$. 
Hence
\begin{align*}
-B'_{m-2}&=\epsilon_mB'_{m-2}\\
         &=B'_m-a'_mB'_{m-1}\\
         &=(B_h+B_{h-1})-(a_h+2)B_{h-1}\\
         &=B_h-B_{h-1}-a_hB_{h-1}\\
         &=B_{h-2}-B_{h-1}.
\end{align*}
Hence
\begin{align*}
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}.
\end{align*}
Finally, 
\begin{align*}
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}.
\end{align*}

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

\noindent
$M=4t+3$,  e.g., $\sqrt{88}=[\rnode[t]{n0}{9},\rnode[t]{n1}{\underset{*}{2}},1,\rnode[t]{n2}{1},1,\rnode[t]{n3}{2},\rnode[t]{n4}{\underset{*}{18}}]\ncarc{n0}{n1} \ncarc{n1}{n2} \ncarc{n2}{n3} \ncarc{n3}{n4}$.  Let $f(m)=h$.  Then $f(m+1)=h+2$ and
\begin{align*}
\xi'_m&=\xi_h+1,\ \epsilon_m=-1;\\
\xi'_{m+1}&=\xi_{h+2}+1,\ \epsilon_{m+1}=-1.
\end{align*}
and as with case (3)(b), we have criterion 1) of Theorem \ref{theorem1}. 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}=[\rnode[t]{n0}{9},\underset{*}{1},\rnode[t]{n1}{1},\rnode[t]{n2}{5},1,\rnode[t]{n3}{5},1,\rnode[t]{n4}{1},\rnode[t]{n5}{\underset{*}{18}}]\ncarc{n0}{n1} \ncarc{n1}{n2} \ncarc{n2}{n3} \ncarc{n3}{n4} \ncarc{n4}{n5}$.  Let $f(m)=h-1$.  Then $f(m+1)=h+1$ and
\[
\xi'_{m+1}=\xi_{h+1}+1,\ \epsilon_{m+1}=-1.
\]
Also $\xi'_m=\xi_{h-1}$ or $\xi_{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 \ref{theorem1}.   We have $A'_m=A_{f(m)+1}=A_h$.  Also, regardless of the sign of $\epsilon_m$, we have $A'_{m-1}=A_{h-2}$.  We now prove 
\begin{align}
A_{k-1}&=A'_mB'_m-A'_{m-1}B'_{m-1},\label{eq:191}\\
B_{k-1}&={B'}_m^2-{B'}_{m-1}^2\label{eq:192}.
\end{align}
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 
\begin{align*}
A'_mB'_m-A'_{m-1}B'_{m-1}&=A_hB_h-A_{h-2}B_{h-2}\\
                         &=A_h(B_{h-1}+B_{h-2})-(A_h-A_{h-1})B_{h-2}\\
                         &=A_hB_{h-1}+A_{h-1}B_{h-2}\\
                         &=A_{p-1}.
\end{align*}
Also \begin{align*}
{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}.
\end{align*}

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

\medskip
\noindent
$M=4t$, e.g., $\sqrt{13}=[\rnode[t]{n0}{3},\underset{*}{1},\rnode[t]{n1}{1},1,\rnode[t]{n2}{1},\rnode[t]{n3}{\underset{*}{6}}]\ncarc{n0}{n1} \ncarc{n1}{n2} \ncarc{n2}{n3}$.  Let $f(m)=h-1$. Then $f(m+1)=h+1$ and
\begin{align*}
\xi'_m&=\xi_{h-1}+1,\ \epsilon_m=-1,\\
\xi'_{m+1}&=\xi_{h+1}+1,\ \epsilon_{m+1}=-1.
\end{align*}
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
\begin{align*}
\epsilon_m=-1&\implies f(m)=f(m-1)+2,\  A'_{m-1}=A_{f(m-1)+1},\\
\epsilon_{m+1}=-1&\implies f(m+1)=f(m)+2,\  A'_{m}=A_{f(m)+1}.
\end{align*}
We have $A'_{m-1}=A_{h-2},\ A'_{m}=A_h$.  We now verify criterion 4) of Theorem \ref{theorem1}.
\begin{equation}
P'_{m+1}=Q'_m+{\half}Q'_{m+1}.\label{eq:20}
\end{equation}
  We note that $a_h=1$ implies $P_{h+1}=Q_h-P_h$. Then
\begin{align*}
P'_{m+1}&=P_{h+1}+Q_{h+1}\\
        &=Q_h-P_h+Q_{h+1}.
\end{align*}
Also 
\[
Q'_{m}+{\half}Q'_{m+1}=Q_{h-1}+\half Q_{h+1}. 
\]
 Hence  \eqref{eq:20} holds if and only if
\begin{align*}
Q_h-P_h+Q_{h+1}&=Q_{h-1}+\half Q_{h+1},\\
\text{i.e., }Q_{h-1}-P_h+Q_{h+1}&=Q_{h-1}+\half Q_{h+1},\\
\text{i.e., }P_h&=\half Q_{h+1}.
\end{align*}
However
\begin{align*}
P_h^2&=D-Q_{h-1}Q_h,\\
P_{h+1}^2&=D-Q_hQ_{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}.
\end{align*}
Next we prove
\begin{align}
A_{p-1}&=A'_mB'_m+2A'_{m-1}B'_{m-1}-(A'_mB'_{m-1}+B'_mA'_{m-1}),\label{eq:21}\\
B_{p-1}&={B'}_m^2+2{B'}_{m-1}^2-2B'_mB'_{m-1}.\label{eq:22}
\end{align}
  Let 
\[
T=A'_mB'_m+2A'_{m-1}B'_{m-1}-(A'_mB'_{m-1}+B'_mA'_{m-1}). 
\]
Then
\begin{align*}
T&=A_hB_h+2A_{h-2}B_{h-2}-(A_hB_{h-2}+B_hA_{h-2})\\
&=A_h(B_h-B_{h-2})+A_{h-2}(B_{h-2}-B_h)+A_{h-2}B_{h-2}\\
&=A_hB_{h-1}-A_{h-2}B_{h-1}+A_{h-2}B_{h-2}\\
&=A_hB_{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}.
\end{align*}
Also
\begin{align*}
{B'}_m^2+2{B'}_{m-1}^2-2B'_mB'_{m-1}&=B_h^2+2B_{h-2}^2-2B_hB_{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}.
\end{align*}

\medskip
\noindent
$M=4t+2$,  e.g., $\sqrt{29}=[\rnode[t]{n0}{5},\rnode[t]{n1}{\underset{*}{2}},1,\rnode[t]{n2}{1},\rnode[t]{n3}{2},\rnode[t]{n4}{\underset{*}{10}}]\ncarc{n0}{n1} \ncarc{n1}{n2} \ncarc{n2}{n3} \ncarc{n3}{n4}$.  Let $f(m)=h$.   Then
$\epsilon_m=-1$ and $\xi'_m=\xi_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:
\begin{equation}
P'_m=Q'_m+{\half}Q'_{m-1}.\label{eq:23}
\end{equation}
Then, as $\xi'_{m-1}=\xi_{h-2}$ or $\xi_{h-2}+1$, we have $Q'_{m-1}=Q_{h-2}$ and
\begin{align*}
P'_m=Q'_m+{\half}Q'_{m-1}&\iff P_h+Q_h=Q_h+{\half}Q_{h-2}\\
                         &\iff P_h={\half}Q_{h-2}.
\end{align*}
But $a_{h-1}=1$ implies $P_h=Q_{h-1}-P_{h-1}$.  Hence
\begin{align*}
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}.
\end{align*}
Next we prove
\begin{align}
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}),\label{eq:24}\\
B_{p-1}&=2{B'}_{m-1}^2+{B'}_{m-2}^2-2B'_{m-1}B'_{m-2}.\label{eq:25}
\end{align}
Note that regardless of the sign of $\epsilon_{m-1}$, we have $A'_{m-2}=A_{h-3}$.  

\noindent
To prove \eqref{eq:24}, 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 
\begin{eqnarray*}
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})\\
& &\mbox{}-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}.
\end{eqnarray*}
Finally, we prove \eqref{eq:25}.  
\begin{eqnarray*}
2{B'}_{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\\
                                            & &\mbox{}-2B_{h-1}(B_{h-1}-B_{h-2})\\
                                            &=&B_{h-1}^2+B_{h-2}^2\\
                                            &=&B_{p-1}.
\end{eqnarray*}
This completes the proof of Theorem \ref{theorem2}.  
\section{RCF periods with only odd length unisequences}\label{section7}
\begin{lemma}\label{lemmaoddm}
Suppose there are no even length ($\geq 2$) unisequences in an RCF period of length $p$ for $\sqrt{D}$. 
If $k$ is the NICF period-length and $0\leq t\leq k/2$, then
\begin{equation}
f(k-t)=p-f(t),\label{eq:27}
\end{equation}
\end{lemma}
\begin{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)$.
\end{proof}
\begin{theorem}\label{theorem3} Suppose there are no even length ($\geq 2$) unisequences in a RCF period of length $p$ for $\sqrt{D}$.  Then if $k$ is the NICF period-length, for $1\leq t\leq k/2$, we have
\begin{enumerate}
\item[(i)] $\epsilon_t=\epsilon_{k+1-t}$;
\item[(ii)] $P'_t=P'_{k+1-t}$;
\item[(iii)] $Q'_t=Q'_{k-t}$;
\item[(iv)] $a'_t=a'_{k-t}$,
\end{enumerate}
where $\xi'_t=\cqu{P'_t}{Q'_t}{D}$ is the $t$-th complete quotient of the NICF-P expansion of $\sqrt{D}$.
\end{theorem}
\begin{remark} In particular, if $k=2h$, then (ii) implies $P'_h=P'_{h+1}$ and we have criterion 1) of Theorem \ref{theorem1}; while if $k=2h+1$, then (iii) implies $Q'_h=Q'_{h+1}$ and we have criterion 3) of Theorem \ref{theorem1}.
\end{remark}
\begin{proof} (i) We use \eqref{eq:fm} and Lemma \ref{lemmaoddm}
\begin{align*}
\epsilon_t=1&\iff f(t)=f(t-1)+1\\
            &\iff p-f(k-t)=p-f(k-t+1)+1\\
            &\iff f(k-t+1)=f(k-t)+1\\
            &\iff \epsilon_{k-t+1}=1.
\end{align*}
(ii) (a) Assume $\epsilon_t=1$.  Then $\epsilon_{k+1-t}=1$ and $f(t)=f(t-1)+1$.  Hence
 $\xi'_t=\xi_{f(t)}=\cqu{P_{f(t)}}{Q_{f(t)}}{D}$ and

\begin{align*}
\xi'_{k+1-t}&=\xi_{f(k+1-t)}=\xi_{p-f(t-1)}=\xi_{p+1-f(t)}\\
            &=\cqu{P_{p+1-f(t)}}{Q_{p+1-f(t)}}{D}\\
            &=\cqu{P_{f(t)}}{Q_{f(t)-1}}{D}.
\end{align*}
Hence $P'_t=P_{f(t)}=P'_{k+1-t}$.

(b) Assume $\epsilon_t=-1$.  Then $\epsilon_{k+1-t}=-1$ and $f(t)=f(t-1)+2$.  

\noindent
Hence $\xi'_t=\xi_{f(t)}+1=\cqu{P_{f(t)}+Q_{f(t)}}{Q_{f(t)}}{D}$ and
\begin{align*}
\xi'_{k+1-t}&=\xi_{f(k+1-t)}+1=\xi_{p-f(t-1)}+1\\
            &=\cqu{P_{p-f(t-1)}}{Q_{p-f(t-1)}}{D}+1=\cqu{P_{f(t-1)+1}+Q_{f(t-1)}}{Q_{f(t-1)}}{D}.
\end{align*}
Hence 
\begin{align*}
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}.
\end{align*}
For brevity, write $r=f(t)-1$. We have to prove $P'_t=P'_{k+1-t}$, i.e., 
\begin{equation}
P_r+Q_{r-1}=P_{r+1}+Q_{r+1}.\label{eq:290}
\end{equation}
We have
\begin{align}
P_{r+1}^2-P_r^2&=(D-Q_rQ_{r+1})-(D-Q_{r-1}Q_r)\notag\\
               &=Q_r(Q_{r-1}-Q_{r+1}).\label{eq:30}
\end{align}
Now $\epsilon_t=-1$ implies $a_{f(t-1)+1}=1=a_{f(t)-1}=a_r$
and hence $P_{r+1}+P_r=a_rQ_r=Q_r$.  Then \eqref{eq:30} gives
\[ 
P_{r+1}-P_r=Q_{r-1}-Q_{r+1}
\]
and hence \eqref{eq:290}.

\noindent
(iii) To prove $Q'_t=Q'_{k-t}$, we observe that
\begin{align*}
\xi'_t&=\xi_{f(t)} \text{\ or \ } \xi_{f(t)}+1,\\
\xi'_{k-t}&=\xi_{f(k-t)} \text{\ or \ } \xi_{f(k-t)}+1.
\end{align*}
Then
\[
Q'_{k-t}=Q_{f(k-t)}=Q_{p-f(t)}=Q_{f(t)}=Q'_t.
\]
(iv) 
\begin{align*}
a'_t&=\begin{cases}
a_{f(t)} \text{\ if $(\epsilon_t,\epsilon_{t+1})=(1,1)$;}\\
a_{f(t)}+1\text{\ if $(\epsilon_t,\epsilon_{t+1})=(1,-1)$ or $(-1,1)$;}\\
a_{f(t)}+2\text{\ if $(\epsilon_t,\epsilon_{t+1})=(-1,-1)$.}
\end{cases}\\
a'_{k-t}&=\begin{cases}
a_{f(k-t)} \text{\ if $(\epsilon_{k-t},\epsilon_{k-t+1})=(1,1)$;}\\
a_{f(k-t)}+1\text{\ if $(\epsilon_{k-t},\epsilon_{k-t+1})=(1,-1)$ or $(-1,1)$;}\\
a_{f(k-t)}+2\text{\ if $(\epsilon_{k-t},\epsilon_{k-t+1})=(-1,-1)$.}
\end{cases}\\
\end{align*}
Then as $(\epsilon_t,\epsilon_{t+1})=(\epsilon_{k+1-t},\epsilon_{k-t})$ and
 $a_{f(k-t)}=a_{p-f(t)}=a_{f(t)}$, it follows that $a'_t=a'_{k-t}$.
\end{proof}

\noindent
We give examples of even and odd NICF period-length in which only odd length unisequences occur.
\begin{align*}
\text{(a)\quad}\sqrt{1532}&=[\rnode[t]{n0}{39},\rnode[t]{n1}{\underset{*}{7}},\rnode[t]{n2}{9},1,\rnode[t]{n3}{1},1,\rnode[t]{n4}{3},1,\rnode[t]{n5}{18},1,\rnode[t]{n6}{3},1,\rnode[t]{n7}{1},1,\rnode[t]{n8}{9},\rnode[t]{n9}{7},\rnode[t]{n10}{\underset{*}{78}}]\ncarc{n0}{n1} \ncarc{n1}{n2} \ncarc{n2}{n3} \ncarc{n3}{n4} \ncarc{n4}{n5} \ncarc{n5}{n6} \ncarc{n6}{n7} \ncarc{n7}{n8} \ncarc{n8}{n9} \ncarc{n9}{n10}\\
                          &=39+\ccfrac{1}{\underset{*}{7}}+\ccfrac{1}{10}-\ccfrac{1}{3}-\ccfrac{1}{5}-\ccfrac{1}{20}-\ccfrac{1}{5}-\ccfrac{1}{3}-\ccfrac{1}{10}+\ccfrac{1}{7}+\ccfrac{1}{\underset{*}{78}}.
\end{align*}

Here $p=16, k=10, P'_5=P'_6$.

\begin{align*}
\text{(b)\quad}\sqrt{277}&=[\rnode[t]{n0}{16},\underset{*}{1},\rnode[t]{n1}{1},1,\rnode[t]{n2}{4},\rnode[t]{n3}{10},1,\rnode[t]{n4}{7},\rnode[t]{n5}{2},\rnode[t]{n6}{2},\rnode[t]{n7}{3},\rnode[t]{n8}{3},\rnode[t]{n9}{2},\rnode[t]{n10}{2},\rnode[t]{n11}{7},1,\rnode[t]{n12}{10},\rnode[t]{n13}{4},1,\rnode[t]{n14}{1},1,\rnode[t]{n15}{\underset{*}{32}}]=\ncarc{n0}{n1}
\ncarc{n1}{n2}
\ncarc{n2}{n3}
\ncarc{n3}{n4}
\ncarc{n4}{n5}
\ncarc{n5}{n6}
\ncarc{n6}{n7}
\ncarc{n7}{n8}
\ncarc{n8}{n9}
\ncarc{n9}{n10}
\ncarc{n10}{n11}
\ncarc{n11}{n12}
\ncarc{n12}{n13}
\ncarc{n13}{n14}
\ncarc{n14}{n15}
\\
17-\ccfrac{1}{\underset{*}{3}}-\ccfrac{1}{5}&+\ccfrac{1}{11}-\ccfrac{1}{8}+\ccfrac{1}{2}+\ccfrac{1}{2}+\ccfrac{1}{3}+\ccfrac{1}{3}+\ccfrac{1}{2}+\ccfrac{1}{2}+\ccfrac{1}{8}-\ccfrac{1}{11}+\ccfrac{1}{5}-\ccfrac{1}{3}-\ccfrac{1}{\underset{*}{34}}.
\end{align*}

Here $p=21, k=15, Q'_7=Q'_8$.
\section{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 {\tt pstricks}, and the referee for improving the presentation of the paper.

\begin{thebibliography}{10}

\bibitem{hurwitz} A.~Hurwitz, 
\"{U}ber eine besondere Art der Kettenbruch-Entwicklung reeller Gr\"{o}ssen,
{\it Acta Math.} {\bf 12} (1889), 367--405.

\bibitem{bosma} W.~Bosma, 
Optimal continued fractions,
{\it Indag. Math.} {\bf 49} (1987), 353---379.

\bibitem{dickson} L.~E.~Dickson,
{\it History of the Theory of Numbers}, 
Vol. 2, Chelsea AMS reprint, 1999.  

\bibitem{matthews-robertson-white} 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 {\it Math. Comp.}

\bibitem{matthews-robertson} K.~R.~Matthews and J.~P.~Robertson,
	Equality of quadratic surd period-lengths for NICF and NSCF,
         in preparation.

\bibitem{minnegerode} B.~Minnegerode, 
\"{U}ber eine neue Methode, die Pellische Gleichung aufzul\"{o}sen,
{\it G\"{o}tt. Nachr.} {\bf 23} (1873), 619--653.

\bibitem{perron} O.~Perron,
{\it Die Lehre von den Kettenbr\"{u}chen},
	Band 1, Teubner, 1954.

\bibitem{rosen} K.~Rosen,
{\it Introduction to Number Theory and its Applications}, Addison-Wesley, 1984.
	\bibitem{hcw} H.~C.~Williams, 
Some results concerning the nearest integer continued fraction expansion of $\sqrt{D}$,
{\it J. Reine Angew. Math.}  {\bf 315} (1980), 1--15.
\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 11A55, 11Y65.

\noindent \emph{Keywords: }nearest integer continued fraction, period--length, midpoint criteria, unisequence.
\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received May 18 2009;
revised version received  September 3 2009.
Published in {\it Journal of Integer Sequences}, September 22 2009.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                


.
