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 & 31 & 28 & 67\\ 11 & 27 2& 8 & 20 \end{matrix}\right \rangle$

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

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

Thank you,
rubik

Solution 1:

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 < b < \sqrt \Delta $$ and $$ \sqrt \Delta - b < 2 |a| < \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 < 0 \; \; \mbox{AND} \; \; \; b > |a+c|. $$

Then, at any given step, find $\delta$ such that $$ \delta c > 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

Solution 2:

In the case of $\sqrt n$, it is extremely easy to tell when you've reached the end of the period; it's when you get a partial quotient twice the integer part. Look at your examples for $n=2,7,14$; the integer parts are $1,2,3$, respectively, and the periods end with $2,4,6$, respectively.

But if you don't know you're working with $\sqrt n$; if, say, you have the continued fractions for $\sqrt2/\pi$ and $\pi$, but you don't know it, I don't see how you'll ever know for sure that the product is periodic. But surely the same question arises if you have the decimal expansions of $\pi$ and $1/\pi$ and you don't know it; how can you ever know for sure that the product is $1$?

Solution 3:

A continuous fraction ends its period when $a_i = 2 * a_0$ example : $\sqrt{23} = [4;1,3,1,8]$ => $8 = 2* 4$

Or am I misunderstanding the question ?