3
$\begingroup$

After playing around on paper for a bit, I came up with a short python generator to find the continued fraction expansion of $\sqrt n$. I understand why it gets the right answer when it gets an answer. But I don't understand why that last divmod always has no remainder. (In other words, why is the coefficient in front of the $\sqrt n$ always 1 in the intermediate terms of the expansion)

from math import sqrt

def contfracsqrt(n):
    k = int(sqrt(n))
    x = 0
    d = 1
    while True:
        a,x=divmod(x+k,d)
        yield a
        x=k-x
        d,t=divmod(n-x**2,d)
        assert t==0

Clarification: I'm not doing anything fancy. I'm finding the continued fraction the simplest way I know of. Suppose we want to find the continued fraction for $\sqrt{n}$. Now let k=$\lfloor\sqrt(n)\rfloor$. We have an expression of the form

$\frac{\sqrt{n}+x_i}{d_i}$

where x and d are integers. (Note that this is just $\sqrt{n}$ when $x_0=0$ and $d_0=1$)

The integer part is

$a_i=\lfloor{\frac{k+x_i}{d_i}}\rfloor$

Now let $r_i=((k+x_i)\bmod{d_i})$ (the other part of the divmod)

Then the fractional part is

$\frac{\sqrt{n} - (k-r_i)}{d_i}$

which can be re-written as 1 over its reciporical to get an expression whose integer part is the next term:

$=\frac{1}{\frac{d_i}{\sqrt{n}-(k-r_i)}}=\frac{1}{\frac{\sqrt{n}+(k-r_i)}{\frac{n-(k-r_i)^2}{d_i}}}$

So that the next term has

$x_{i+1}=k-r_i$

$d_{i+1}=\frac{n-(k-r_i)^2}{d_i}$

This works, because $d_{i+1}$ always seems to be an integer. My question is why?

$\endgroup$
2
  • 3
    $\begingroup$ Ahah! This is a nice question, and I had the same some time ago (and more or less the same program, also in Python!). The debvelopment of $\sqrt{n}$ is very peculiar. For example, it's "symmetric" (you can reverse the terms of the first period). I found explanations in a french book, but sadly I have no other reference on this in textbook form. I found this, that may help you. There is also this. $\endgroup$ – Jean-Claude Arbaut Dec 9 '13 at 20:23
  • $\begingroup$ @dspyz - please write out the equations you are asking about. $\endgroup$ – nbubis Dec 9 '13 at 20:27
1
$\begingroup$

Ok,

So I found a simple inductive proof which relies on strengthening the inductive hypothesis (and hence the result).

Proof that $\forall i, d_i\in\mathbb{Z}$ and $d_i|n-x_i^2$

Base case:

$d_0=1$ so it's $\in\mathbb{Z}$ and it divides any integer expression

Inductive case:

Given some $i$, assume $d_i\in\mathbb{Z}$ and $d_i|n-x_i^2$

Now because $a_i$ and $r_i$ are the div and mod of $k+x_i$ with $d_i$ (see the notation used in the question) we can say

$d_i|x_i+k-r_i$

We can multiply the right-hand expression by $x_i-(k-r_i)$ to get

$d_i|x_i^2-(k-r_i)^2$

Adding this to the expression in our inductive hypothesis gives

$d_i|n-(k-r_i)^2$

So $d_{i+1}\in\mathbb{Z}$

Additionally, if we look at the other expression we need to prove, substituting in the expressions for $d_{i+1}$ and $x_{i+1}$ we get:

$\frac{n-(k-r_i)^2}{d_i}|n-(k-r_i)^2=d_{i+1}|n-x_{i+1}^2$

which follows trivially from the fact that $d_i\in\mathbb{Z}$

QED

$\endgroup$
0
$\begingroup$

I don't understand. The continued fraction for $\sqrt {41}$ is $\langle 6; 2,2,12 \rangle.$

Here is output from my C++ program doing Lagrange's method of "reduced forms," which are the triples of integers in the middle of each line in the cycle. It is in precisely this situation, by the way, that Lagrange's method gives double the cyclic part in the continued fraction method.

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

0  form   1 12 -5   delta  -2
1  form   -5 8 5   delta  2
2  form   5 12 -1   delta  -12
3  form   -1 12 5   delta  2
4  form   5 8 -5   delta  -2
5  form   -5 12 1   delta  12
6  form   1 12 -5

 disc   164
Automorph, written on right of Gram matrix:  
-129  -1600
-320  -3969


 Pell automorph 
-2049  -13120
-320  -2049

Pell unit 
-2049^2 - 41 * -320^2 = 1 

=========================================

Pell NEGATIVE 
-32^2 - 41 * -5^2 = -1 

=========================================

41       41

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

$\endgroup$
1
  • $\begingroup$ What don't you understand? $\endgroup$ – Jean-Claude Arbaut Dec 10 '13 at 8:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.