# Continued fraction of a square root

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!

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.

• 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
• Incredible, really. – Meitar Jun 13 '15 at 12:19

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$

• With this you end up with generalized continuous fraction. I mean $n-a^2$ not necessarily $1$. – Yola Oct 24 '16 at 17:59
• This is a sad case of changing the question to get a simpler answer (and that is assuming the question was how to find the continued fraction of $\sqrt n$; in fact it was rather uninterestingly just about its first term, the integer part of $\sqrt n$). – Marc van Leeuwen May 29 '18 at 10:50
• -1 As @Yola points out, this doesn’t (necessarily) give you a continued fraction – HelloGoodbye Aug 30 '18 at 22:55
• @HelloGoodbye OP changed his question, I answered what he originally asked. – Ethan Sep 1 '18 at 1:06
• Okay. If so, shouldn't it be possible to see that here? – HelloGoodbye Sep 1 '18 at 23:39

$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$.

• This is probably the most helpful answer to the original question. – LarsH Mar 14 '19 at 13:17

$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.

Here the easiest method to generate continued fraction for any square (or more) root. Lets take $$\sqrt{5}$$:

$$\sqrt{5} \approx 2,2360679775...$$ $$\sqrt{5} = 2 + 0,2360679775$$

So $$2=\left \lfloor \sqrt{5} \right \rfloor$$

$$\sqrt{5} =2 + x$$ with $$x=0,2360679775$$

$$\sqrt{5}^{2} = (x + 2)^{2} \Rightarrow 5= x^2 + 4x + 4$$ $$1= x^2 + 4x$$ $$\frac{1}{x}= x + 4 \Rightarrow x = \frac{1}{4+x}$$ So $$x = \frac{1}{4+\frac{1}{4+\frac{1}{4+\frac{1}{4+\ddots}}}}$$

Finally, we got: $$\sqrt{5} = 2 + \frac{1}{4+\frac{1}{4+\frac{1}{4+\frac{1}{4+\ddots}}}}$$.

So for any $$x$$, $$\sqrt{x} = \left \lfloor \sqrt{x} \right \rfloor + \frac{x-\left \lfloor \sqrt{x} \right \rfloor^{2}}{2\left \lfloor \sqrt{x} \right \rfloor+\frac{x-\left \lfloor \sqrt{x} \right \rfloor^{2}}{2\left \lfloor \sqrt{x} \right \rfloor+\frac{x-\left \lfloor \sqrt{x} \right \rfloor^{2}}{2\left \lfloor \sqrt{x} \right \rfloor + \ddots}}}$$

So to answer, $$a_0 =\left \lfloor \sqrt{x} \right \rfloor$$ (because any periodic continued fraction is smaller than 1).

• I am getting better at mentally doing square roots... generally to slide rule accuracy. But your answer mentions other roots, Could you amplify this a bit for cube roots? – richard1941 Apr 29 '18 at 0:57
• How does this even work for say $\sqrt 7$? In a continued fraction the numerators have to be $1$, which you don't get by this method. – Marc van Leeuwen May 29 '18 at 10:48
• @MarcvanLeeuwen see math.stackexchange.com/q/3075250/432081 – CopyPasteIt Jan 16 '19 at 2:49