Estimation on the accuracy of the convergents of $\sqrt{n}$

246 Views Asked by At

I have noticed that the accuracy of the best rational approximations to $\sqrt{n}$ given by his continued fraction expansion, when the numerator and deniminator are large numbers, is approximately given by the sum of the digits in both the numerator and denominators, For example, for $\sqrt{2}$, the convergent

$ 1,023,286,908,188,737 / 723,573,111,879,672 $ is correct to 29 places. The digits in the numerator are $16$ and in the denominator are $ 15 $, and their sum is equal to $ 31$. So, the accuracy $ p$ is approximately equal to the sum of the digits of the denominator $d_1$ and the numerator $d_2$

$p \approx d_1+d_2$

The next convergent is $ 2,470,433,131,948,081 / 1,746,860,020,068,409 $, and is correc to 31 places. The digits on both numerator and denominator is equal to 16, so their sum is 32. Again we see that

$p \approx d_1+d_2$

You can check more examples with following list

http://www.zyvra.org/laforth/sqr2.htm

How to prove that, for "large numbers" in both numerator and denominator, the accuracy is aporoximately equal to the sum of their digits?

1

There are 1 best solutions below

0
On

I think this theorem is discussed in Hardy and Wright. Also Shockley had a very nice discussion, if I recall correctly. The central idea which can be proved fairly readily by mathematical induction, is that if $$\frac{p_n}{q_n}$$ is the $n^{th}$ convergent to the continued fraction of $\sqrt D$, they satisfy a Pell-type equation $$p_n^2-Dq_n^2=(-1)^ns_{n+1}$$ And since $s_ns_{n+1}=D-r_{n+1}^2$, $s_n,\,s_{n+1},\,r_{n+1}\in\mathbb{Z}^+$ we get $$\frac{p_n^2}{q_n^2}-D=\frac{(-1)^ns_{n+1}}{q_n^2}$$ Or $$\frac{p_n}{q_n}-\sqrt D=\frac{(-1)^ns_{n+1}}{q_n^2\left(\frac{p_n}{q_n}+\sqrt D\right)}$$ For big $n$, the denominator is very close to $2\sqrt Dq_n^2$ and the numerator is bounded above in absolute value by $D$, so the error is less than about $\frac{\sqrt D}{2q_n^2}$ but always at least about $\frac1{2q_n^2\sqrt D}$.