How to detect when continued fractions period terminates I'm doing continued fractions arithmetic. Is there a method to detect when a continued fractions period terminates?
Let me give you an example:
$\sqrt{2} = [1; \overline{2}]$, $\sqrt{7} = [2; \overline{1, 1, 1, 4}]$ and $\sqrt{14} = [3; \overline{1, 2, 1, 6}]$.
Now clearly $\sqrt{2} \times \sqrt{7} = \sqrt{14}$, but if we do continued fractions arithmetic we get: $[1; \overline{2}] \times [2; \overline{1, 1, 1, 4}] = 3, 1, 2, 1, 6, 1, 2, 1, 6, 1, 2, 1, 6, \dots$. Obviously this sequence never ends, since the continued fraction can always input a term from either $\sqrt{2}$ or $\sqrt{7}$ (as they are infinite).  

So my question is: is there a mathematical method to detect when the period ends (during addition, subtraction, multiplication and division), rather than guessing and checking?
Maybe using the $z$ object (this "thing")? For example, after it emits the first $1$ it is:
$\left \langle \begin{matrix}13 &amp; 31 &amp; 28 &amp; 67\\ 
 11 &amp; 27 2&amp; 8 &amp; 20
\end{matrix}\right \rangle$

and when the period starts again:
$\left \langle \begin{matrix} 549 &amp; 1317 &amp; 2226 &amp; 5335\\ 95 &amp; 239 &amp; 814 &amp; 2010 \end{matrix} \right \rangle$
and again: $\left \langle \begin{matrix} 92029 &amp; 222405 &amp; 122610 &amp;  296283\\ 41317 &amp; 99487 &amp; 37841 &amp; 91039 \end{matrix} \right \rangle$.  

Is there some kind of a pattern? I've noted none.  

Thank you,
rubik
This is more for J.M... it is not necessary to use cycle-detection algorithms if you stick with reduced quadratic forms, http://www.numbertheory.org/php/reduce.html for one description.

As I wrote in https://mathoverflow.net/questions/22811/upper-bound-of-period-length-of-continued-fraction-representation-of-very-composi/23014#23014 
  if you are looking at only reduced forms $$ \langle a,b,c \rangle \approx a x^2 + b x y + c y^2,  $$ with discriminant $\Delta = b^2 - 4 a c$ positive but not a square, with
$$  0 &lt; b &lt; \sqrt \Delta   $$
and
$$  \sqrt \Delta - b &lt; 2 |a| &lt;  \sqrt \Delta + b.   $$ 

Edit, April 2015: THEOREM: a form $ \langle a,b,c \rangle$ with discriminant $\Delta = b^2 - 4 a c$ positive but not a square is REDUCED if and only if 
$$ ac &lt; 0 \; \; \mbox{AND} \; \; \; b &gt; |a+c|.  $$

Then, at any given step, find $\delta$ such that 
$$ \delta c &gt; 0 $$
and
$$  |\delta| = \left\lfloor \left| \frac{b +\sqrt \Delta}{2 c} \right|\right\rfloor $$
Now, the right adjacent form, or right neighbor, is given by 
$$ \langle a,b,c \rangle \rightarrow  \langle c, -b + 2 c \delta, a - b \delta + c \delta^2 \rangle.  $$
Lather, rinse, repeat.

If you begin with a reduced form $\langle a_0,b_0,c_0 \rangle$ then, after a finite number of steps, call it $n$ steps, we get an exact match of all three coefficients,  $$\langle a_n,b_n,c_n \rangle = \langle a_0,b_0,c_0 \rangle$$ 

An indefinite binary quadratic form, with integer coefficients, corresponds to one of two quadratic irrationals given by the quadratic formula, where we are solving for either $x/y$ or $y/x$ according to taste. As the discriminant is positive and not a square, the roots are real numbers. It turns out that the number defined by the continued fraction (take the absolute values of the $\delta$'s) is not just positive but is larger than 1. Just one of those things.

I noticed in your code for $\sqrt N$ you had it terminate when the first coefficient returned to $\pm 1.$ Thts is not going to work if the reduced form you start with is $\langle 7,3,-7 \rangle$ where the exact method I describe is giving the continued fraction for 
$$  \frac{3 + \sqrt{205}}{14}  $$  

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./indefCycle
Input three coefficients a b c for indef f(x,y)= a x^2 + b x y + c y^2 
7  3  -7

0  form   7 3 -7   delta  -1
1  form   -7 11 3   delta  4
2  form   3 13 -3   delta  -4
3  form   -3 11 7   delta  1
4  form   7 3 -7
minimum was   3rep -1 -1 disc   205 dSqrt 14.317821063  M_Ratio  4.183673
Automorph, written on right of Gram matrix:  
17  21
21  26
 Trace:  43   gcd(a21, a22 - a11, a12) : 3
=========================================
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$


To repeat, reduced indefinite integral quadratic form correspond to quadratic irrationals with purely periodic continued fractions. The cycle is complete if and only if the initial reduced form has been repeated. No other cycle detection is required.

The one caution is that, because we are taking the absolute values of the $\delta$'s, it is possible for the continued fraction period to be exactly half the period of the quadratic form. For example, 

=========================================
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./Pell
Input n for Pell 
61

0  form   1 14 -12   delta  -1
1  form   -12 10 3   delta  4
2  form   3 14 -4   delta  -3
3  form   -4 10 9   delta  1
4  form   9 8 -5   delta  -2
5  form   -5 12 5   delta  2
6  form   5 8 -9   delta  -1
7  form   -9 10 4   delta  3
8  form   4 14 -3   delta  -4
9  form   -3 10 12   delta  1
10  form   12 14 -1   delta  -14
11  form   -1 14 12   delta  1
12  form   12 10 -3   delta  -4
13  form   -3 14 4   delta  3
14  form   4 10 -9   delta  -1
15  form   -9 8 5   delta  2
16  form   5 12 -5   delta  -2
17  form   -5 8 9   delta  1
18  form   9 10 -4   delta  -3
19  form   -4 14 3   delta  4
20  form   3 10 -12   delta  -1
21  form   -12 14 1   delta  14
22  form   1 14 -12

 disc   244
Automorph, written on right of Gram matrix:  
-183241189  1581119536
-226153980  945570387


 Pell automorph 
-1766319049  -910490892
-226153980  -1766319049

Pell unit 
1766319049^2 - 61 * 226153980^2 = 1 

=========================================
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$


The above is giving the continued fraction for 
$$  \frac{7 + \sqrt{61}}{12},$$
So I think we are always getting the largest value of $x/y$ rather than $y/x.$   For your purpose, this is just right, you are putting a 7 in front, which uses the reciprocal of the above, to get
$$  7 + \; \;  \frac{12}{ \sqrt{61} + 7}    $$
which works out to $\sqrt 61$ when you rationalize the denominator.

Please, read chapter 3, pages 21-48, in Binary Quadratic Forms by Duncan A. Buell,  AMAZON
It may sound a bit trivial, but actually, the important qustion would be: When has a fraction a period, i.e., when is there repetitive bahvior in the digits. It is known that irrational numbers are non-terminating, non-periodic decimal fractions. Using simple set-theory, i.e., taking the complement of the set of irrational numbers in the set of real numbers, we find, that either the rational numbers are terminating decimal fractions or periodic fractions. In either case, by the construction of the rational numbers, it is possible to find an expression like this: $q=\dfrac{n}{m}, n\in\mathbb{Z}, m\in\mathbb{N}$. Note that this expression needn't be unique!. Hence, after having added $m$ times the number $q$ we're done. So far about the theory.
My experience has told me that these questions are the practical ones, i.e., those of little mathematical interest (b.t.w.: I am a pure mathematician working in global analysis, differntial topology and differential geometry &lt;---- Purest mathematics apart from logic). I think that numerically one could find the answer to your problem, but in general, you will have to stick to guessing and checking. But perhaps when you learn abstract algebra and number theory combined with logic, you come across some solution (I have heard abstract algebra in the shortened version for geometers :D)