Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If I want to find the continued fraction of $\sqrt{n}$ how do I know which number to use for $a_0$? Is there a way to do it without using a calculator or anything like that? What's the general algorithm for computing it? I tried to read the wiki article but was overwhelmed and lost. I tried Googling but couldn't find a website that actually explained this question.

If anyone has a good site that answers these questions either, please let me know. Thanks!

share|improve this question

4 Answers 4

up vote 3 down vote accepted

Let's just do an example. Let's find the continued fraction for $\def\sf{\sqrt 5}\sf$. $\sf\approx 2.23$ or something, and $a_0$ is the integer part of this, which is 2.

Then we subtract $a_0$ from $\sf$ and take the reciprocal. That is, we calculate ${1\over \sf-2}$. If you're using a calculator, this comes out to 4.23 or so. Then $a_1$ is the integer part of this, which is 4. So: $$\sf=2+\cfrac{1}{4+\cfrac1{\vdots}}$$

Where we haven't figured out the $\vdots$ part yet. To get that, we take our $4.23$, subtract $a_1$, and take the reciprocal; that is, we calculate ${1\over 4.23 - 4} \approx 4.23$. This is just the same as we had before, so $a_2$ is 4 again, and continuing in the same way, $a_3 = a_4 = \ldots = 4$: $$\sf=2+\cfrac{1}{4+\cfrac1{4+\cfrac1{4+\cfrac1\vdots}}}$$


This procedure will work for any number whatever, but for $\sf$ we can use a little algebraic cleverness to see that the fours really do repeat. When we get to the ${1\over \sf-2}$ stage, we apply algebra to convert this to ${1\over \sf-2}\cdot{\sf+2\over\sf+2} = \sf+2$. So we could say that: $$\begin{align} \sf & = 2 + \cfrac 1{2+\sf}\\ 2 + \sf & = 4 + \cfrac 1{2+\sf}. \end{align}$$

If we substitute the right-hand side of the last equation expression into itself in place of $ 2+ \sf$, we get:

$$ \begin{align} 2+ \sf & = 4 + \cfrac 1{4 + \cfrac 1{2+\sf}} \\ & = 4 + \cfrac 1{4 + \cfrac 1{4 + \cfrac 1{2+\sf}}} \\ & = 4 + \cfrac 1{4 + \cfrac 1{4 + \cfrac 1{4 + \cfrac 1{2+\sf}}}} \\ & = \cdots \end{align} $$

and it's evident that the fours will repeat forever.

share|improve this answer
    
I always thought they were in the form a0 + 1/(a1 + 1/ (a2 + 1/( ... –  user51819 Dec 27 '12 at 2:01
    
@user51819 Quite so (although $a_0$ could be 0.) I had the typesetting wrong, and have corrected it. –  MJD Dec 27 '12 at 2:03
    
Sorry, one last question; how do we know, in the general sense, when we've hit the point where it's periodic? When you encounter an $a_k$ you've seen before? Or when a reciprocal equals a reciprocal you've seen before? I am guessing the latter? –  user51819 Dec 27 '12 at 2:09
    
When the reciprocal is one you have seen before. It couldn't be when you reach an $a_k$ you've seen before or else you couldn't have a repeating sequence like $1,1,2,1,1,2,1,1,2,\ldots$. –  MJD Dec 27 '12 at 2:15

$a_0$ is simply the largest integer such that $a^2 \le n$ . You can determine the continued fraction for a square root by performing the $\frac1{\sqrt n - a_0}$ step and then using the conjugate to remove the square root from the denominator, and repeating.

I recommend Ron Knott's site: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/cfINTRO.html . Good Luck.

share|improve this answer

$a_0$ is the largest integer that is smaller than or equal to $\sqrt n$. Or put another way, you want $a_0^2$ to be smaller than or equal to $n$, and $(a_0+1)^2$ to be bigger than $n$.

If you really have no idea what integer to use, then you find it by guessing an integer $g$. Then you calculate $g^2$. If $g^2$ is bigger than $n$, your guess $g$ was too big, and you try a smaller guess. If $g^2$ is much smaller than $n$, your guess $g$ was too small, and you try a bigger guess. You keep doing this until you find a guess $g$ where $g^2 \le n$ and $(g+1)^2 > n$, and then $a_0 = g$.

share|improve this answer

Confirm the algebraic identity: $$\sqrt n=a+\frac{n-a^2}{a+\sqrt n}$$ Then chose whatever value of 'a' you want, and just keep on pluging in $\sqrt n$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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