\documentclass[12pt,reqno]{amsart}

\usepackage{color}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
%\definecolor{webgreen}{rgb}{0,.5,0}
%\definecolor{webbrown}{rgb}{.6,0,0}
%\usepackage{psfig,epsf,latexsym}
\usepackage{epsf}
\usepackage{float}


\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\textheight}{8.7in}
\setlength{\topmargin}{0.0in}

\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{lemma}{Lemma}
\newtheorem{corollary}{Corollary}

\theoremstyle{definition}
\newtheorem{example}[theorem]{Example}

\numberwithin{equation}{section}
\def\floor#1{{\lfloor#1\rfloor}}
\def\bigfloor#1{{\left\lfloor#1\right\rfloor}}
\newcommand{\Lf}{\left\lfloor}
\newcommand{\Rf}{\right\rfloor}
\newcommand{\Lc}{\left\lceil}
\newcommand{\Rc}{\right\rceil}

\begin{document}

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

\title{On Shanks' algorithm for computing the continued fraction of $\log_b{a}$}

\author{Terence Jackson$^1$ and Keith Matthews$^2$}

\maketitle

\begin{center}
$^1$ Department of Mathematics \\
University of York, Heslington \\
York YO105DD, England\\
UK\\
{\tt thj1@york.ac.uk}\\

\ \\

$^2$ Department of Mathematics \\
University of Queensland \\ 
Brisbane, Australia, 4072\\
{\tt krm@maths.uq.edu.au}\\
\end{center}

\begin{abstract} 
We give a more practical variant of Shanks' 1954 algorithm for computing the continued fraction of $\log_b{a}$, for integers $a>b>1$, using the floor and ceiling functions and an integer parameter $c>1$. 
The variant, when repeated for a few values of $c=10^r$, enables one to guess if $\log_b{a}$ is rational and to find approximately $r$ partial quotients.
\end{abstract}


\section{Shanks' algorithm}
 In his article \cite{shanks}, Shanks gave an algorithm for computing the partial quotients of $\log_b{a}$, where $a>b$ are positive integers greater than $1$. Construct two sequences $a_0=a,a_1=b,a_2,\ldots$ and $n_0,n_1,n_2,\ldots$, where the $a_i$ are positive rationals and the $n_i$ are positive integers, by the following rule:  If $i\geq 1$ and $a_{i-1}>a_i>1$, then

\begin{eqnarray}
a_i^{n_{i-1}}&\leq&a_{i-1}<a_i^{n_{i-1}+1}\label{eq:1}\\ 
a_{i+1}&=&a_{i-1}/a_i^{n_{i-1}}.\label{eq:1a}
\end{eqnarray}

Clearly (\ref{eq:1}) and (\ref{eq:1a}) imply $a_i>a_{i+1}\geq 1$. Also (\ref{eq:1}) implies $a_i\leq a_{i-1}^{1/n_{i-1}}$ for $i\geq 1$ and hence by induction on $i\geq 0$,
\begin{equation}
a_{i+1}\leq a_0^{1/n_0\cdots n_i}.\label{eq:1b}
\end{equation}

Also by induction on $j\geq 0$, we get
\begin{equation}
a_{2j}=a_0^r/a_1^s,\quad a_{2j+1}=a_1^u/a_0^v,\label{eq:1bb}
\end{equation}
where $r$ and $u$ are positive integers and $s$ and $v$ are non--negative 
integers.

Two possibilities arise:
\begin{enumerate}
\item[(i)] $a_{r+1}=1$ for some $r\geq 1$. Then equations (\ref{eq:1bb}) 
imply a relation $a_0^q=a_1^p$ for positive integers $p$ and $q$ and so 
$\log_{a_1}{a_0}=p/q$.
\item[(ii)] $a_{i+1}>1$ for all $i$. In this case the decreasing sequence 
$\{a_i\}$ tends to $a\geq 1$. Also (\ref{eq:1b}) implies $a=1$, unless perhaps 
$n_i=1$ for all sufficiently large $i$; but then (\ref{eq:1a}) becomes 
$a_{i+1}=a_{i-1}/a_i$ and hence $a=a/a=1$. 
\end{enumerate}

If $a_{i-1}>a_i>1$, then from (\ref{eq:1}) we have 
\begin{equation}
n_{i-1}=\bigfloor{\frac{\log{a_{i-1}}}{\log{a_{i}}}}.\label{eq:1c}
\end{equation}

Let $x_i=\log_{a_{i+1}}{a_i}$ if $a_{i+1}>1$. Then we have

\begin{lemma} If $a_{i+2}>1$, then
\begin{equation}
 x_{i}=n_{i}+1/x_{i+1}.\label{eq:3}
\end{equation}
\end{lemma}

\begin{proof}From (\ref{eq:1a}), we have
\begin{eqnarray}
\log{a_{i+2}}&=&\log{a_{i}}-n_{i}\log{a_{i+1}}\\
1&=&\frac{\log{a_{i}}}{\log{a_{i+1}}}\cdot\frac{\log{a_{i+1}}}{\log{a_{i+2}}}-n_{i}\cdot\frac{\log{a_{i+1}}}{\log{a_{i+2}}}\\
&=&x_{i}x_{i+1}-n_{i}x_{i+1},
\end{eqnarray}
from which (\ref{eq:3}) follows.
\end{proof}

\medskip
From Lemma 1.1 and (\ref{eq:1c}), we deduce

\begin{lemma}
\begin{enumerate}
\item[(a)] If $\log_{a_1}{a_0}$ is irrational, then 
\[
 x_{i}=n_{i}+1/x_{i+1}\mbox{ for all } i\geq 0.
\]
\item[(b)] If $\log_{a_1}{a_0}$ is rational, with $a_{r+1}=1$, then 
\[
x_i=\left\{\begin{array}{ll}
n_i+1/x_{i+1},& \mbox{if\/ $0\leq i< r-1$;}\\
n_{r-1},&\mbox{if \/ $i=r-1$.}
\end{array}
\right.
\]
\end{enumerate}
\end{lemma}

In view of the equation $\log_{a_1}{a_0}=x_0$, Lemma 2 leads immediately to

\begin{corollary} 
\begin{equation}
\log_{a_1}{a_0}=\left\{\begin{array}{ll}
[n_0,n_1,\ldots],&\mbox{ if \/ $\log_{a_1}{a_0}$ is irrational;}\\
\left[n_0,n_1,\ldots,n_{r-1}\right],&\mbox{ if \/ $\log_{a_1}{a_0}$ is rational and $a_{r+1}=1$.\label{eq:40}}
\end{array}
\right.
\end{equation}
\end{corollary}

\noindent
{\bf Remark}. It is an easy exercise to show that for $j\geq 0$,
\begin{equation}
 a_{2j}=a_0^{q_{2j-2}}/a_1^{p_{2j-2}},\quad 
 a_{2j+1}=a_1^{p_{2j-1}}a_0^{q_{2j-1}}\label{eq:4}
\end{equation}
where $p_k/q_k$ is the $k$--th convergent to $\log_{a_1}{a_0}$.

\noindent
\begin{example} $\log_2{10}$: Here $a_0=10, \ a_1=2$. Then $2^3<10<2^4$, so $n_0=3$ and $a_2=10/2^3=1.25$.

 Further, $1.25^3<2<1.25^4$, so $n_1=3$ and $a_3=2/1.25^3=1.024$. 

Also, $1.024^9<1.25<1.024^{10}$, so $n_2=9$ and 
\begin{eqnarray*}
 a_4&=&1.25/1.024^9\\
&=&1250000000000000000000000000/1237940039285380274899124224\\
&=&1.0097419586\cdots
\end{eqnarray*}

Continuing in this fashion, we obtain Table \ref{table1}
 and $\log_2{10}=[3,3,9,2,2,4,6,2,1,1,\ldots]$.

\begin{table}[H]
%\caption{Shanks' Algorithm for $a=10, b=2$}
\small
\begin{center}
\begin{tabular}{|c|c|c|c|}\hline
$i$ & $n_i$ & $a_i$ & $p_i/q_i$\\ \hline
$0$ & $3$ & $10$ & $3/1$\\ \hline
$1$ & $3$ & $2$ & $10/3$\\ \hline
$2$ & $9$ & $1.25$ & $93/28$\\ \hline
$3$ & $2$ & $1.024$ &$196/59$\\ \hline
$4$ & $2$ & $1.0097419586\cdots$ & $485/146$ \\ \hline
$5$ & $4$ & $1.0043362776\cdots$ & $2136/643$ \\ \hline
$6$ & $6$ & $1.0010415475\cdots$ & $13301/4004$\\ \hline
$7$ & $2$ & $1.0001628941\cdots$ &$28738/8651$\\ \hline
$8$ & $1$ & $1.0000637223\cdots$ & $42039/12655$\\ \hline
$9$ & $1$ & $1.0000354408\cdots$ & $70777/21306$\\ \hline
$10$ & $$ & $1.0000282805\cdots$ & $$ \\ \hline
$11$ & $$ & $1.0000071601\cdots$  & $$\\ \hline
\end{tabular}
\end{center}
\bigskip
\caption{}\label{table1}
\end{table}
\end{example}

\section{Some Pseudocode}
In Table~\ref{table2} we present pseudocode for the Shanks algorithm.

It soon becomes impractical to perform the calculations in multiprecision 
arithmetic, as the numerators and denominators $a_i$ grow rapidly.  
If we truncate the decimal expansions of the {\tt a[i]} to $r$ places and 
represent a positive rational $a$ as $g(a)/10^r$, where 
$g(a)=\lfloor 10^ra\rfloor$, the ratio {\tt aa/bb} will be calculated as 
$\bigfloor{10^rg(aa)/g(bb)}$. Working explicitly in integers, using the $g(a)$,
then  results in algorithm 1, also depicted in Table \ref{table2}, with $c=10^r$, where \verb+int(x,y)+ equals $\lfloor x/y\rfloor$, when $x$ and $y$ are integers.  

As shown in the next section, the {\tt A[i]} decrease strictly until they reach
 {\tt c}. Also {\tt m[0]}$=${\tt n[0]} and we can expect a number 
of the initial {\tt m[i]} will be partial quotients.  Naturally, the larger we 
take $c$, the more partial quotients will be produced.

\begin{table}[H]
\begin{center}
\begin{tabular}{|l|l|}
\hline
Shanks' algorithm & algorithm 1\\
\hline

{\tt input: integers a$>$b$>$1} & {\tt input: integers a$>$b$>$1, c$>1$}\\
{\tt output: n[0],n[1],$\ldots$}   & {\tt output: m[0],m[1],$\ldots$}\\

        {\tt s:= 0} & {\tt s:= 0} \\
       {\tt a[0]:= a; a[1]:= b} & {\tt A[0]:= a*c; A[1]:= b*c}\\
        {\tt aa:= a[0]; bb:= a[1]} & {\tt aa:= A[0]; bb:= A[1]}\\
        {\tt while(bb $>$ 1)\{} &  {\tt while(bb $>$ c)\{}\\
        \quad    {\tt i:=0} &\quad {\tt i:=0}\\
         \quad   {\tt while(aa $\geq$ bb)}\{ & \quad {\tt while(aa $\geq$ bb)\{}\\
          \quad     \quad {\tt aa:= aa/bb} &\quad\quad {\tt aa:= int(aa*c,bb)}\\
           \quad    \quad {\tt i:= i+1}    &\quad\quad{\tt  i:= i+1} \\
           \quad {\tt\}} & \quad{\tt\}}\\
           \quad {\tt a[s+2]:= aa} &\quad {\tt A[s+2]:= aa}\\
           \quad {\tt n[s]:= i} &\quad {\tt m[s]:= i}\\
            \quad {\tt t:= bb} & \quad {\tt t:= bb}\\
         \quad   {\tt  bb:= aa} &\quad {\tt  bb:= aa}\\
        \quad     {\tt aa:= t} &\quad  {\tt aa:= t}\\
          \quad   {\tt s:= s+1} &\quad {\tt  s:= s+1}\\
       {\tt \}} & {\tt \}} \\
& \\
\hline
\end{tabular}
\bigskip
\caption{}\protect\label{table2}
\end{center}
\end{table}

\section{Formal description of algorithm 1}
We show in Theorem 2.1 below, that algorithm 1 will give the correct partial 
quotients when $\log_{a_1}{a_0}$ is rational and otherwise gives a parameterised
 sequence of integers which tend to the correct partial quotients when 
$\log_{a_1}{a_0}$ is irrational. 

Algorithm 1 is now explicitly described. We define two integer sequences $\{A_{i,c}\},\,i=0,\ldots,l(c)$ and $\{m_{j,c}\},\,j=0,\ldots,l(c)-2$, as follows.

Let $A_{0,c}=c\cdot a_0, A_{1,c}=c\cdot a_1$. 
Then if $i\geq 1$ and $A_{i-1,c}>A_{i,c}>c$, we define $m_{i-1,c}$ and 
$A_{i+1,c}$ by means of an intermediate sequence $\{B_{i,r,c}\}$, defined 
for $r\geq 0$, by $B_{i,0,c}=A_{i-1,c}$ and
\begin{equation}
 B_{i,r+1,c}=\Lf\frac{cB_{i,r,c}}{A_{i,c}}\Rf, r\geq 0.\label{eq:floor}
\end{equation}

Then $c\leq B_{i,r+1,c}<B_{i,r,c}$, if $B_{i,r,c}\geq A_{i,c}>c$ and hence there is a unique integer $m=m_{i-1,c}\geq 1$ such that
\[
 B_{i,m,c} < A_{i,c} \leq B_{i,m-1,c}.
\]

Then we define $A_{i+1,c}=B_{i,m,c}$. Hence $A_{i+1,c}\geq c$ and 
the sequence $\{A_{i,c}\}$ decreases strictly until $A_{l(c),c}=c$. 


There are two possible outcomes, depending on whether or not $\log_b(a)$ is rational:

\begin{theorem} 
\begin{enumerate}
\item[(1)] If $\log_{a_1}a_0$ is a rational number $p/q$
with $p>q\geq1$ and $\gcd(p,q)=1$, then
\begin{enumerate}
\item $a_0=d^p,\,a_1=d^q$ for some positive integer $d$;
\item if $p/q=[n_0,\ldots,n_{r-1}]$, where $n_{r-1}>1$ if $r>1$, then 
\begin{enumerate}
\item[(i)] $A_{r+1,c}=c, a_{r+1}=1$;
\item[(ii)] $A_{i,c}=c\cdot a_i$ for $0\leq i\leq r+1$;
\item[(iii)] $m_{i,c}=n_i$ for $0\leq i\leq r-1$.
\end{enumerate}
\end{enumerate}

\item[(2)] If $\log_{a_1}a_0$ is irrational, then
\begin{enumerate}
\item $m_{0,c}=n_0$;
\item $l(c)\to\infty$ and for fixed $i$, $ A_{i,c}/c\to a_i$  as $c\to\infty$ and $m_{i,c}=n_i$ for all large $c$.
\end{enumerate}
\end{enumerate}
\end{theorem}
\begin{proof} 1(a) follows from the equation $a_1^p=a_0^q$.

1(b) is also straightforward on noticing that $a_i$ is a power of $d$ and that 
we are implicitly performing Euclid's algorithm on the pair $(p,q)$. 

For 2(a), we have
\begin{equation}
a_1^{n_0}<a_0<a_1^{n_0+1}\label{eq:5}
\end{equation}
and $A_{0,c}=c\cdot a_0$, 
 $A_{1,c}=c\cdot a_1$. Also by induction on $0\leq r\leq n_0$,
\begin{eqnarray}
B_{1,r,c}&\geq& ca_1^{n_0-r},\label{eq:6}\\
B_{1,r,c}&\leq& \frac{ca_0}{a_1^r}.\label{eq:7}
\end{eqnarray}

Inequality (\ref{eq:6}) with $r\leq n_0-1$ gives $B_{1,r,c}\geq A_{1,c}$, while
 inequality (\ref{eq:7}) with $r=n_0$ gives 
\[
B_{1,n_0,c}\leq \frac{ca_0}{a_1^{n_0}}<ca_1=A_{1,c},
\]
by inequality (\ref{eq:5}). Hence $m_{0,c}=n_0$.

For 2(b), we use induction on $i\geq 1$ and assume $l(c)\geq i$ holds for 
all large $c$ and that $A_{i-1,c}/c\to a_{i-1}$ and $A_{i,c}/c\to a_i$ as $c\to
\infty$. This is clearly true when $i=1$.

By properties of the integer part symbol, equation (\ref{eq:floor}) gives
\begin{equation}
\frac{c^rA_{i-1,c}}{A_{i,c}^r}-\frac{(1-\frac{c^r}{A_{i,c}^r})}{1-\frac{c}{A_{i,c}}}<B_{i,r,c}\leq \frac{c^rA_{i-1,c}}{A_{i,c}^r}.\label{eq:approx}
\end{equation}
for $r\geq 0$.

Hence for $r<n_{i-1}$, inequalities (\ref{eq:approx}) give  
\[
B_{i,r,c}/c\to a_{i-1}/a_i^r\geq a_{i-1}/a_i^{n_{i-1}-1}> a_i.
\]
Then, because $A_{i,c}/c\to a_i$, it follows that $B_{i,r,c}>A_{i,c}$ for all
 large $c$.

Also $B_{i,n_{i-1},c}/c\to a_{i-1}/a_i^{n_{i-1}}<a_i$,
 so $B_{i,n_{i-1},c}<A_{i,c}$ for all large $c$. Hence $m_{i-1,c}=n_{i-1}$ 
for all large $c$.
 Also $A_{i+1,c}=B_{i,n_{i-1},c}>c$, so $l(c)>i+1$  for all large $c$. Moreover 
$A_{i+1,c}/c\to a_{i-1}/a_i^{n_{i-1}}=a_{i+1}$ and the induction goes through.
\end{proof}

\begin{example} Table \ref{table3} lists the sequences $m_{0,c},\ldots,m_{l(c)-2,c}$ for $c=2^u, u=1,\ldots,30$, when $a_0=3,a_1=2$. 

\begin{table}[H]
\begin{verbatim}
          1,1,
          1,1,1,
          1,1,1,1,
          1,1,1,2,
          1,1,1,2,
          1,1,1,2,3,
          1,1,1,2,2,2,
          1,1,1,2,2,2,1,
          1,1,1,2,2,2,1,2,
          1,1,1,2,2,3,2,3,
          1,1,1,2,2,3,2,
          1,1,1,2,2,3,1,2, 1, 1,1, 2,
          1,1,1,2,2,3,1,3, 1, 1,3, 1,
          1,1,1,2,2,3,1,4, 3, 1,
          1,1,1,2,2,3,1,4, 1, 9,1,
          1,1,1,2,2,3,1,5,24, 1,2,
          1,1,1,2,2,3,1,5, 3, 1,1, 2,7,
          1,1,1,2,2,3,1,5, 2, 1,1, 5,3, 1,
          1,1,1,2,2,3,1,5, 2, 2,1, 3,1,16,
          1,1,1,2,2,3,1,5, 2,15,1, 6,2
          1,1,1,2,2,3,1,5, 2, 9,5, 1,2,
          1,1,1,2,2,3,1,5, 2,13,1, 1,1, 6,  1, 2, 2,
          1,1,1,2,2,3,1,5, 2,17,2, 7,8,
          1,1,1,2,2,3,1,5, 2,19,1,49,2, 1,
          1,1,1,2,2,3,1,5, 2,22,4, 8,3, 4,  1,
          1,1,1,2,2,3,1,5, 2,22,2, 1,3, 1,  3, 8,
          1,1,1,2,2,3,1,5, 2,22,1, 6,3, 1,  1, 3, 4,  2,
          1,1,1,2,2,3,1,5, 2,23,2, 1,1, 2,  1,12,17,
          1,1,1,2,2,3,1,5, 2,23,3, 2,2, 2,  2, 1, 3,  2,
          1,1,1,2,2,3,1,5, 2,23,2, 1,7, 2,  2,14, 1,  1, 6,
\end{verbatim}
\caption{}\label{table3}
\end{table}

\end{example}
In fact $\log_2{3}=[1,1,1,2,2,3,1,5,2,23,2,\ldots]$.


\section{A heuristic algorithm}
We can replace the $\floor{x}$ function in equation (\ref{eq:floor})
 by $\lceil{x}\rceil$, the least integer exceeding $x$. 

This produces an algorithm with similar properties to algorithm 1, with integer
 sequences $\{A'_{i,c}\},\,i=0,\ldots,l'(c)$ and $\{m'_{j,c}\},\,j=0,\ldots,l'(c)-2$. Here $A_{0,c}=A'_{0,c}=a_0\cdot c$, $A_{1,c}=A'_{1,c}=a_1\cdot c$ and $m_{0,c}=m'_{0,c}=n_0$.
Then if $i\geq 1$ and $A'_{i-1,c}>A'_{i,c}>c$, we define $m'_{i-1,c}$ and 
$A'_{i+1,c}$ by means of an intermediate sequence $\{B'_{i,r,c}\}$, defined 
for $r\geq 0$, by $B'_{i,0,c}=A'_{i-1,c}$ and

\begin{equation}
 B'_{i,r+1,c}=\Lc\frac{cB'_{i,r,c}}{A'_{i,c}}\Rc, r\geq 0.\label{eq:ceiling}
\end{equation}

Then $c\leq B'_{i,r+1,c}<B'_{i,r,c}$, if $B'_{i,r,c}\geq A'_{i,c}>c$.  

For 
\[
 B'_{i,r+1,c}\leq\frac{cB'_{i,r,c}}{A'_{i,c}}+1
\]
and
\begin{eqnarray*}
\frac{cB'_{i,r,c}}{A'_{i,c}}+1\leq B'_{i,r,c}&\Leftrightarrow&cB'_{i,r,c}+A'_{i,c}\leq A'_{i,c}B'_{i,r,c}\\
&\Leftrightarrow& \frac{A'_{i,c}}{A'_{i,c}-c}\leq  B'_{i,r,c}.
\end{eqnarray*}

The last inequality is certainly true if $B'_{i,r,c}\geq A'_{i,c}>c$.

Hence there is a unique integer $m'=m'_{i-1,c}\geq 1$ such that
\[
 B'_{i,m',c} < A'_{i,c} \leq B'_{i,m'-1,c}.
\]
Then we define $A'_{i+1,c}=B'_{i,m',c}$. Hence $A'_{i+1,c}\geq c$ and 
the sequence $\{A'_{i,c}\}$ decreases strictly until $A'_{l'(c),c}=c$. 

If we perform the two computations simultaneously, the common initial elements of the sequences $\{m_{j,c}\}$ and $\{m'_{k,c}\}$ are likely to be partial quotients of $\log_b(a)$.  With $c=10^r$ we expect roughly $r$ partial quotients to be produced. 

If $l(c)=l'(c)$ and $A_{j,c}=A'_{j,c}$ and $m_{j,c}=m'_{j,c}$ for $j=0,\ldots,l(c)-2$, then $\log_b{a}$ is likely to be rational.

In practice, to get a feeling of certainty regarding the output when $c=10^r$, we also run the algorithm for $c=10^t, r-5\leq t\leq r+5$.

\begin{example} Table \ref{table4} lists the common values of
 $m_{i,c}$ and $m'_{i,c}$, when $a=3, b=2$ and $c=2^{r}, 1\leq r\leq 31$.
 It seems likely that only partial quotients are produced for all $r\geq 1$.
\end{example}
\newpage

\begin{table}[H]
%\caption{}\label{table4}
\begin{verbatim}
                               1: 1
                               2: 1
                               3: 1,1,1
                               4: 1,1,1
                               5: 1,1,1,2
                               6: 1,1,1,2
                               7: 1,1,1,2,2
                               8: 1,1,1,2,2
                               9: 1,1,1,2,2
                              10: 1,1,1,2,2
                              11: 1,1,1,2,2
                              12: 1,1,1,2,2
                              13: 1,1,1,2,2,3,1
                              14: 1,1,1,2,2,3,1
                              15: 1,1,1,2,2,3,1
                              16: 1,1,1,2,2,3,1,5
                              17: 1,1,1,2,2,3,1,5
                              18: 1,1,1,2,2,3,1,5
                              19: 1,1,1,2,2,3,1,5,2
                              20: 1,1,1,2,2,3,1,5
                              21: 1,1,1,2,2,3,1,5,2
                              22: 1,1,1,2,2,3,1,5,2
                              23: 1,1,1,2,2,3,1,5,2
                              24: 1,1,1,2,2,3,1,5,2
                              25: 1,1,1,2,2,3,1,5,2
                              26: 1,1,1,2,2,3,1,5,2
                              27: 1,1,1,2,2,3,1,5,2
                              28: 1,1,1,2,2,3,1,5,2,23
                              29: 1,1,1,2,2,3,1,5,2,23
                              30: 1,1,1,2,2,3,1,5,2,23,2
                              31: 1,1,1,2,2,3,1,5,2,23,2

\end{verbatim}
\caption{$a=3, b=2, c=2^{r}, 1\leq r\leq 31$.}\label{table4}
\end{table}

\begin{example} Table \ref{table5} lists the common values of
 $m_{i,c}$ and $m'_{i,c}$, when $a=34, b=2$ and $c=10^r, 1\leq r\leq 20$.
 Partial quotients are not always produced, as is seen from lines 9,14 and 17.
\end{example}
\newpage

\begin{table}[H]
%\caption{}\label{table5}
\begin{verbatim}
                     1: 1,2,2
                     2: 1,2,2,1,1
                     3: 1,2,2,1,1,2
                     4: 1,2,2,1,1,2
                     5: 1,2,2,1,1,2,3,1
                     6: 1,2,2,1,1,2,3,1,8,1
                     7: 1,2,2,1,1,2,3,1,8,1,1
                     8: 1,2,2,1,1,2,3,1,8,1,1,2
                     9: 1,2,2,1,1,2,3,1,8,1,1,2,2,1,13,3,2,32,7
                     10:1,2,2,1,1,2,3,1,8,1,1,2,2,1
                     11:1,2,2,1,1,2,3,1,8,1,1,2,2,1,12,1
                     12:1,2,2,1,1,2,3,1,8,1,1,2,2,1,12,1
                     13:1,2,2,1,1,2,3,1,8,1,1,2,2,1,12,1,13
                     14:1,2,2,1,1,2,3,1,8,1,1,2,2,1,12,1,13,3,3
                     15:1,2,2,1,1,2,3,1,8,1,1,2,2,1,12,1,13,3,2
                     16:1,2,2,1,1,2,3,1,8,1,1,2,2,1,12,1,13,3,2,2
                     17:1,2,2,1,1,2,3,1,8,1,1,2,2,1,12,1,13,3,2,2,18,1,1,1,1,1
                     18:1,2,2,1,1,2,3,1,8,1,1,2,2,1,12,1,13,3,2,2,17,1
                     19:1,2,2,1,1,2,3,1,8,1,1,2,2,1,12,1,13,3,2,2,17,1
                     20:1,2,2,1,1,2,3,1,8,1,1,2,2,1,12,1,13,3,2,2,17,1
\end{verbatim}
\bigskip
\caption{$a=34, b=12, c=10^r, r=1,\ldots,20$.}\label{table5}
\end{table}

\section{Acknowledgement}
The second author is grateful for the hospitality provided by the School of Mathematical Sciences, ANU, where research for part of this paper was carried out.

\bibliographystyle{amsplain}
\begin{thebibliography}{10}
\bibitem {shanks} D. Shanks, A logarithm algorithm, {\it Math.\ Tables and 
Other Aids to Computation} {\bf 8} (1954), 60--64.
\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: 11D09.\ \

\noindent \emph{Keywords:  Shanks' algorithm, continued fraction, log, heuristic algorithm }

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence \seqnum{A028507}.)


\vspace*{+.1in}
\noindent
Received November 19, 2002;
revised version received  December 6, 2002.
Published in {\it Journal of Integer Sequences} December 10, 2002.
\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}.

\end{document}