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?