Best Approximations

Let $x$ be a real number.
A best approximation to $x$ for the denominator bound $d$ is a rational number $\frac r s $ in reduced form, with $s \le d$, such that any rational number which is closer to $x$ than $\frac r s$ has a denominator larger than $d$:
$|\frac p q -x | < |\frac r s -x| \Rightarrow q > d$

For example, the best approximation to $\sqrt {13}$ for the denominator bound 20 is $\frac {18} 5$ and the best approximation to $\sqrt {13}$ for the denominator bound 30 is $\frac {101}{28}$.
Find the sum of all denominators of the best approximations to $\sqrt n$ for the denominator bound $10^{12}$, where $n$ is not a perfect square and $ 1 < n \le 100000$.

This problem is rather complicated – it involves understanding the theory of continued fractions and their link to rational approximations of real numbers.

Approximating square roots is a classic use case for continued fractions. This is based on the fact that for any irrational number, the sequence of best rational approximations are given by the convergents of its continued fraction expansion.

Firstly, each square root can be expressed as a continued fraction using a standard method – for $\sqrt{n}$, it is always $[a_0; (\overline{a_1, a_2, …, a_2, a_1, a_0*2})]$, where $a_i$ are integers. The overline notation means the sequence repeats infinitely.

However, you cannot simply get the approximation of square root by taking a certain number of terms in the continued fraction. You need to cut the fraction at some point (before the denominator exceeds $10^{12}$) and simplify it into a ratio of two integers.

You need to generate fractions for $\sqrt n$ for $1 < n \leq 100000$, which is not a perfect square, and take the one where the denominator is as large as possible but still below a trillion. This will involve a mix of some programming and using mathematical packages or libraries that can handle continued fractions, since manually doing this for $n$ up to 100000 will be quite labour-intensive. The result - a list of rational numbers - will be the best approximations within the bound. Finally, the sum of the denominators can found by summing up all the denominators of these fractions. Please note, this task requires good understanding of number theory and programming skills to implement the above steps. The methods used to generate and deal with continued fractions can be quite complex. Without specific software or a programming tool to handle this automatically, it would be an enormous task to calculate the answer manually.

More Answers: