I have an irrational number $\alpha$ ($\alpha=\frac\pi2$), and I would like to determine all integers $n\in[1,N]$ ($N=10^{16}$) that satisfy $$ n \epsilon(n)^2 \leq \tau $$ where $\tau$ is a known real number ($\tau=78$), and $\epsilon(n)$ is the distance between $n$ and the closest multiple of $\alpha$: $$ n = m \alpha + \epsilon(n), \qquad |\epsilon(n)| < \tfrac12\alpha. $$

I know that if I approximate $\alpha$ by a rational number $A/B$, then the problem can be solved with extended Euclid's algorithm applied to $$ Bn-Am = B\epsilon, $$ where $B\epsilon$ is an integer, with an upper bound derived from $n\epsilon^2<\tau$, $B\epsilon<B\sqrt{\tau}$. For each value of $B\epsilon$ I can compute corresponding solutions $n\in[1,N]$.

The problem is that if $A/B$ is a sufficiently accurate rational approximation to $\alpha$ (i.e., $B\sim N$ ensures that $n\epsilon^2$ is approximated accurately), then the bound $B\epsilon < B\sqrt\tau$ (e.g., $B\sqrt\tau=10^{17}$) leads me to consider prohibitively many different $n$.

The standard theory of rational approximations tells me how to compute the *best* rational approximations with continued fractions, but I need to compute *all* rational approximations $n/m$ that are good enough in the above sense. If I write
$$ \alpha = \frac nm-\frac \epsilon m = \frac nm+\delta, $$
the equivalent problem is to compute all $(n,m)$ with
$$ \big|\alpha - \frac nm\big| < \frac{\sqrt\tau}{m \sqrt{n}} \sim \frac{\sqrt{\tau/\alpha}}{m^{3/2}}, $$
but the right-hand side here is quite different from $1/m^2$ (or $1/m^\mu$ where $\mu\geq2$ is the irrationality measure of $\alpha$). Since $\tfrac32\leq\mu$, that tells me there are infinitely many solutions, but I don't know how to actually compute them.

Is there an efficient algorithm for computing $n$ with $n\epsilon^2<\tau$?

Felipe Volochcommented while I was writing this] there will be about $\tau N^{1/2}$ of them, which for $(N,\tau) = (10^{16},78)$ is almost $10^{10}$ $-$ is that really what you want? $\endgroup$ – Noam D. Elkies Oct 11 '14 at 16:441more comment