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!
 A: $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.
A: 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).
A: 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.  
A: 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.
A: 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$
A: $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$.
A: 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

