46
$\begingroup$

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!

$\endgroup$
0

8 Answers 8

50
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$
    – user51819
    Dec 27, 2012 at 2:09
  • 1
    $\begingroup$ 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$. $\endgroup$
    – MJD
    Dec 27, 2012 at 2:15
  • $\begingroup$ Incredible, really. $\endgroup$
    – Meitar
    Jun 13, 2015 at 12:19
  • 1
    $\begingroup$ A student of mine asked about the continued fraction of the square root of 22 and I suggested her to apply your solution. She did and failed! In fact, I checked and realized that she did everything as you suggested. Thus, the problem was with the method itself as described here. The problem is that in the case of the square root of 5, the repetition appears very soon, thus the intermediate approximations used do not create any problem. But when we need to go deeper, the number of decimal places used does matter. $\endgroup$ Mar 3, 2016 at 10:41
  • 1
    $\begingroup$ @user51819: You can tell that you've completed the first iteration of the repeating portion when you hit a value that is exactly double a_0. For the square root of n*n+1, this value will be the only element in the repeating portion. $\endgroup$
    – EvilSnack
    May 1, 2023 at 18:56
24
$\begingroup$

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$

$\endgroup$
7
  • 4
    $\begingroup$ With this you end up with generalized continuous fraction. I mean $n-a^2$ not necessarily $1$. $\endgroup$
    – Yola
    Oct 24, 2016 at 17:59
  • 3
    $\begingroup$ 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$). $\endgroup$ May 29, 2018 at 10:50
  • $\begingroup$ -1 As @Yola points out, this doesn’t (necessarily) give you a continued fraction $\endgroup$ Aug 30, 2018 at 22:55
  • 3
    $\begingroup$ Okay. If so, shouldn't it be possible to see that here? $\endgroup$ Sep 1, 2018 at 23:39
  • 1
    $\begingroup$ you can reach continued fraction easily from the equation above; here is an example sqrt(52) = 49 + 3 = 7 + 3/(7 + (7 + 3/7 + ...), just divide off the 3 top and bottom, =7 + 1/(14/3 + 1/(14/3 + ...). In J language, (+%)/ 7, (14 14 14 14 14 14 14) % 3 $\endgroup$
    – Zhe Hu
    Mar 21, 2022 at 18:43
15
$\begingroup$

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

$\endgroup$
1
  • 6
    $\begingroup$ This is probably the most helpful answer to the original question. $\endgroup$
    – LarsH
    Mar 14, 2019 at 13:17
8
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ 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? $\endgroup$ Apr 29, 2018 at 0:57
  • 2
    $\begingroup$ 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. $\endgroup$ May 29, 2018 at 10:48
  • 1
    $\begingroup$ @MarcvanLeeuwen see math.stackexchange.com/q/3075250/432081 $\endgroup$ Jan 16, 2019 at 2:49
5
$\begingroup$

For the record, the continued fraction expansion of a real number $x_0 = x$ is found by computing $a_n = \lfloor x_n \rfloor$ and then $x_{n+1} = 1 / (x_n - a_n)$.

For specific examples and intuition, see the other answers to this post. Here I describe a simple procedure for computing the expansion of $\sqrt{N}$ that involves only integer arithmetic.

The motivation is that we can always write $x_n = (r_n + \sqrt{N}) / s_n$ for integers $r_n$ and $s_n$.

We compute the sequences $a_n$, $r_n$ and $s_n$ inductively:

First, compute $a_0 = \lfloor \sqrt{N} \rfloor$. This is just the largest integer $a_0$ with $a_0^2 \leq N$. Set $r_0 = 0$ and $s_0 = 1$. Then for each $n$, define

$$ a_n = \left \lfloor \frac{r_n + a_0}{s_n} \right \rfloor $$ $$ r_{n+1} = a_ns_n - r_n $$ $$ s_{n+1} = (N - r_{n+1}^2) / s_n. $$

Sidenote: the sequence $s_n$ in fact ends up being all integers.

$\endgroup$
1
$\begingroup$

In Vedic mathematical tradition, pupils are taught an algorithm to take the square root of any number. I learned this algorithm of an Indian business man when I sat next to him on the plane from London to Trondheim.

You take any number you want to find the root of, for example 1234567. You group the number in pairs of digits 1,23,45,67 and you start with the first pair of digits or single digit as in this case. The square root of $1$ is $x=1$. You subtract $1$ and get $0$ and you attach the next two digits $$\begin{array}{r@{\;}r@{\;}r@{\;}c@{\;}l} 1&23&45&67&=&1???\cr -1\cr\hline 0&23 \end{array}$$ You should also make an accumulator that is equal to $Acc = 2\times x=2$. The next digit $d$ in the root is should be largest digit so that $d\times(10Acc+d)$ is smaller than 23. This digit must be $d=1$ because $21\times 1<21$, but $22\times 2>21$. Substract $21$ from $23$ and attach the next two digits $45$ to the bottom line. $$\begin{array}{r@{\;}r@{\;}r@{\;}c@{\;}l} 1&23&45&67&=&11??\cr -1\cr\hline 0&23\cr&-21\cr\hline &2&45 \end{array}$$ You must also update the accumulator by $Acc:=10\times Acc+2d=22$ The next digit $d$ in the root is should be largest digit so that $d\times(10Acc+d)$ is smaller than 245. This digit must be $d=1$ because $221\times 1<245$, but $222\times 2>245$. Substract $221$ from $245$ and attach the last two digits $67$ to the bottom line. $$\begin{array}{r@{\;}r@{\;}r@{\;}c@{\;}l} 1&23&45&67&=&111?\cr -1\cr\hline 0&23\cr&-21\cr\hline &2&45\cr&-2&21\cr\hline &&24&67 \end{array}$$ Update the accumulator by $Acc:=10\times Acc+2d=222$ The next digit $d$ in the root is should be largest digit so that $d\times(10Acc+d)$ is smaller than 2467. This digit must be $d=1$ because $2221\times 1<2467$, but $2222\times 2>2467$. Substract $2221$ from $2467$ and attach the first two digits $00$ after the decimal point to continue the process. $$\begin{array}{r@{\;}r@{\;}r@{\;}c@{\;}l} 1&23&45&67&=&1111.?\cr -1\cr\hline 0&23\cr&-21\cr\hline &2&45\cr&-2&21\cr\hline &&24&67\cr&&-22&21\cr\hline &&2&46&00 \end{array}$$

$\endgroup$
1
$\begingroup$

To find the period of a continued fraction, specifically to solve problem Project Euler #64 I did the following.

ProjectEuler+Project Euler #64: Odd period square roots

ProjectEuler.net #64: Odd period square roots

Start With: $ \sqrt{n} = \lfloor \sqrt{n} \rfloor + \sqrt{n} - \lfloor \sqrt{n} \rfloor $

$ \text{Got }x_1 = \lfloor \sqrt{n} \rfloor $

$ \sqrt{n} = x_1 + \sqrt{n} - x_1 = x_1 + \frac{1}{\frac{1}{\sqrt{n} - x_1}}$

So: $a_0 = (a_0^{int},a_0^{frac})= x_1, {\frac{1}{\sqrt{n} - x_1}} ⇒ a_0^{frac} = {\frac{\sqrt{n} + x_1}{n - x_1^2}}$

For recursion purposes.
$ (k = 1 \space , \space den = n - x_1^2) ⇒ a_0^{frac} = \frac{k(\sqrt{n} + x_1)}{den} $

First iteration:
$ a_1^{int} =\left \lfloor {a_0^{frac}} \right \rfloor = \left \lfloor \frac{k(\sqrt{n} + x_1)}{den} \right \rfloor = c $

$ finv(a_1^{frac}) = \frac{k(\sqrt{n} + x_1)}{den} - c = \frac{(k\sqrt{n} + k \cdot x_1 - c \cdot den)}{den} = \frac{k(\sqrt{n} - (\frac{c \cdot den}{k} - x_1 ))}{den} ⇒\\ a_1^{frac} = \frac{\frac{den}{k}}{(\sqrt{n} - (\frac{c \cdot den}{k} - x_1 ))} ⇒ \text{New values} \space ⇒ (k_2 = \frac{den}{k},x_2 = \frac{c \cdot den}{k} - x_1, den_2 = n - x_2^2)$

The recursion continues until $ a_n^{frac} = a_0^{frac}$ when the period starts and the fractional part values repeat infinitely.

In this idea, I elaborated the following algorithm:

https://github.com/rafaeldjsm/Matematica/blob/main/ProjectEuler_64__square_roots.ipynb

from math import sqrt

def perfarc(n):
    root = int(sqrt(n))
    if root == sqrt(n):
        return 0
    a = 1
    listaint = [root]
    den = n - root**2
    lista_inv_frac = [(sqrt(n)+root)/den]
    per = 0
    while True:
        part_int = int(lista_inv_frac[-1])
        root = (den * part_int)/a - root
        a = den/a
        den = (n-root**2)
        invfrac = a*(sqrt(n)+root)/den
        listaint.append(part_int)
        lista_inv_frac.append(invfrac)
        per+=1
        if invfrac == lista_inv_frac[0]:
            return per

n = int(input())
cntodd = 0
for k in range(2,n+1):
    if perfarc(k)%2 == 1:
        cntodd+=1

cntodd
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .