Approximations to $\pi$ Is there a way to efficiently solve the following problem besides brute-force calculation?
Fix $n\in\mathbb{N}$ (say $n=100$).  Find the integers $p,q,r,s$ with $0\leq p,q,r,s\leq n$ such that
$$\pm\frac{p}{q}\pm\sqrt{\frac{r}{s}}$$
most closely approximates $\pi$.
Some cases can be handled by finding the continued fraction expansion of $(\pi-\frac{p}{q})^2$ for various $p,q$.  Playing with this method I found the approximation $4-\sqrt{\frac{14}{19}}$, which is really quite good, but may not be best for $n=20$.  Note that the solution will be unique (for a given $n$).
 A: This is not exactly an answer to the stated question, but it's too long for a comment. Rather than the form given in the question, one could represent a number in the form $\frac{a + b \sqrt{d}}{c}$, where $d$ is a squarefree positive integer,
and this form lends itself to finding good approximations to $\pi$ using lattice reduction.
Fix a bound $n$. For each squarefree $d$ with $1 \leq d \leq n$,
choose a constant $X \approx n^{2} \sqrt{d}$ and create the lattice in $\mathbb{R}^{4}$ spanned by
$$ v_{1} = \begin{bmatrix} 1 \\ 0 \\ 0 \\ X \pi \end{bmatrix}, v_{2} = \begin{bmatrix} 0 \\ 1 \\ 0 \\ -X \end{bmatrix}, v_{3} = \begin{bmatrix} 0 \\ 0 \\ 1 \\ -X \sqrt{d} \end{bmatrix}. $$
A short vector in this lattice with respect to the $\ell_{2}$ norm is a linear combination $a v_{1} + bv_{2} + cv_{3}$ and because the fourth coordinate of these vectors are so large, this forces $\frac{a+b \sqrt{d}}{c}$ to be a close approximation to $\pi$.
Finding the shortest vector in a lattice is a hard problem, even in small dimensional lattices. However, one can get within a constant multiple of the true minimum using the LLL-algorithm. With this, the above algorithm would run in time $O(n \log^{3} n)$ and find "some good solutions", but isn't guaranteed to find the optimal representation (even in this modified form).
I ran this with $n = 10^{6}$ and $X = n^{2} \sqrt{d} \log(n)$ and obtained (after about a minute and a half)
$$
\pi \approx \frac{-327031 + 7075 \sqrt{224270}}{962406}.
$$
The approximation differs from the truth by about $8 \cdot 10^{-22}$.
