Optimizing continued fraction of square root

Question

From this question, I learned that the square root of a number $n$ can be written as a continued fraction of the form:

$$\sqrt n=a+\frac{n-a^2}{a+\sqrt n}$$

where $a$ can have any value. By jumping to conclusions and testing, I believe that the optimal value for $a$ for a rapid convergence is the largest integer such that $a^2 < n$, but I haven't even been able to start trying to prove this.

Any insight would be helpful. Thanks!

Answer 1

There are two basic methods. The one usually called continued fractions starts with $a^2 < n,$ and continues with all $+$ signs. The other side would be the fairly modern method of Zagier, which uses all minus signs, and is discussed at length in his book on zeta functions, see also

https://oeis.org/A257161

The usual method is due, as far as I can tell, to Lagrange and Gauss; I admit that it is possible that continued fractions existed before the right-neighbor method. Here are some examples.

This one says that the CF for $\sqrt 7$ is $\langle 2; 1,1,1,4 \rangle,$ where the $1,1,1,4$ keeps repeating.

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./Pell 7


0  form   1 4 -3   delta  -1
1  form   -3 2 2   delta  1
2  form   2 2 -3   delta  -1
3  form   -3 4 1   delta  4
4  form   1 4 -3

---

This one says that the CF for $\sqrt {29}$ is $\langle 5;2,1,1,2,10 \rangle,$ where the $2,1,1,2,10$ keeps repeating. In this case that part is repeated in the Lagrange cycle, which happens because there is a solution to $u^2 - 29 v^2 = -1$ in integers.

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./Pell 29


0  form   1 10 -4   delta  -2
1  form   -4 6 5   delta  1
2  form   5 4 -5   delta  -1
3  form   -5 6 4   delta  2
4  form   4 10 -1   delta  -10
5  form   -1 10 4   delta  2
6  form   4 6 -5   delta  -1
7  form   -5 4 5   delta  1
8  form   5 6 -4   delta  -2
9  form   -4 10 1   delta  10
10  form   1 10 -4

Answer 2

\begin{align*} \frac{p_{n}}{q_{n}} &= \sqrt{n}+e_{n} \\ &= a+\frac{n-a^2}{a+\frac{p_{n-1}}{q_{n-1}}} \\ &= \frac{a\left(a+\frac{p_{n-1}}{q_{n-1}} \right)+n-a^2} {a+\frac{p_{n-1}}{q_{n-1}}} \\ &= \frac{a \frac{p_{n-1}}{q_{n-1}}+n}{\frac{p_{n-1}}{q_{n-1}}+a} \\ &= \frac{a (\sqrt{n}+e_{n-1})+n}{\sqrt{n}+e_{n-1}+a} \\ &= \frac{\sqrt{n}(\sqrt{n} \color{red}{+e_{n-1}}+a)+ (a \color{red}{-\sqrt{n}})e_{n-1}} {\sqrt{n}+e_{n-1}+a} \\ &= \sqrt{n}+\frac{(a-\sqrt{n})e_{n-1}}{a+\sqrt{n}+e_{n-1}} \\ \frac{p_{n}}{q_{n}}-\sqrt{n} &= \frac{(a-\sqrt{n})e_{n-1}}{a+\sqrt{n}+e_{n-1}} \\ e_{n} &= \frac{(a-\sqrt{n})e_{n-1}}{a+\sqrt{n}+e_{n-1}} \\ \frac{e_{n}}{e_{n-1}} & \approx \frac{a-\sqrt{n}}{a+\sqrt{n}} \\ \end{align*}

In usual practice, we take $a=\lfloor \sqrt{n} \rfloor \implies a-\sqrt{n}<0 $,

so that

$$\frac{p_n}{q_n} \lessgtr \sqrt{n} \lessgtr \frac{p_{n+1}}{q_{n+1}}$$