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.

1more comment