Efficient computation of the least fraction with square denominator greater than the square root of 2. The least rational number greater than $\sqrt{2}$ that can be written as a ratio of integers $x/y$ with $y\le10^{100}$ can be found in a moment using a little Python program. Can anyone write a program that finds, in hours rather than centuries, the least rational greater than $\sqrt{2}$ of the form $x/y^2$ with $y^2\le 10^{100}$? 
More generally, my question is whether the following computation is known to be feasible or not feasible:
Given $N$, find  the least rational greater than $\sqrt{2}$ of the form $x/y^2$,
 with $x$ and $y$ integers and $y^2\le N$. For definiteness, let's say that the output should be the required rational written in lowest form.
By a feasible computation I mean one that can be done in $O((\log N)^k)$ bit operations for some constant $k$. 
Of course the square root of 2 is not essential here. Any irrational would do, as long as comparisons with rationals are feasible. I don't know of any such irrational for which I can answer the question I've posed.
 A: The following "aglorithm" gives not necessarily the best solution but yields
fairly "good" solutions. 
Start with a $n$ "bad" rational approximations $x_1/y_1,\dots,x_n/y_n$ of $2^{1/4}$
(obtained eg. by considering a few convergents of $2^{1/4}$) such that $y_1 \dots y_n < N$ and consider a linear 
combination $\sum_{i=1}^n a_i(x_i/y_i)^2=x/(y_1\cdots y_n)^2$ with $a_i\in \mathbb Z,\sum_{i=1}^na_i=1$ which is slightly larger than $\sqrt 2$. One way to get coefficients
$a_1,\dots,a_n\in \mathbb Z$ with $\sum a_i(x_i/y_i)^2$ close to $\sqrt{2}$
is by using the LLL-algorithm: Consider the $(n+1)-$dimensional sublattice $\Lambda$
of $\mathbb R^{n+2}$ spanned by 
$f_1=(1,0,0,\dots,0,A(x_1/y_1)^2)$, $f_2=(0,1,0,\dots,0,A(x_2/y)^2),\dots$,
$f_n=(0,0,\dots,1,0,A(x_n/y_n)^2)$, $f_{n+1}=(0,\dots,0,1,A\sqrt 2)$ where $A$ is some huge real number
(one can also work with an integral lattice by rounding off the last coordinate to the nearest integer for a fixed large real number $A$). A short vector of the form $(a_1,\dots,a_n,1)$ in $\Lambda$ yields a good rational approximation $\sum_{i=1}^n a_i(x_i/y_i)^2$ of $\sqrt 2$ . About half of the time, such an approximation should have the correct sign. A few LLL runs for various large constant values of $A$ (which should be larger than $\max (y_i^2)$, perhaps $A\sim \sqrt{N}$ is interesting) and various 
finite sets $x_1,\dots,x_n$ (with $n$ also varying) should give interesting approximations.
A: You should try the algorithms in Elkies' paper (from 2000) "Rational points near curves ..." http://arxiv.org/abs/math/0005139 .  His idea is to cover the curve with a bunch of small rectangles, and use lattice basis reduction within each such region.  He proves a result which either says that there are small number of solutions or all the solutions lie on a line.
