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$?



Computing all "suboptimal" rational approximations to $\pi/2$
As noted in the comments (by **Felipe Voloch** and myself), one expects
about $O\_\tau(N^{1/2})$ solutions, because that's the area $|R|$ of the region
$$
R = \{ (m,n) \in {\bf R}^2 \colon 
 1 \leq n \leq N, \ (\alpha m - n)^2 < \tau/n \}
$$
whose intersection with ${\bf Z}^2$ we want to list. (In the comment
I got the dependence on $\tau$ wrong: it's $(\tau N)^{1/2}$, not $\tau N^{1/2}$, because
the upper bound on $|\alpha m - n|$ is $\sqrt{\tau/n}$, not $\tau\,/\sqrt n$
as I misread; so for $(N,\tau) = (10^{16},78)$ we expect about $10^9$
pairs $(m,n)$, not $10^{10}$.) 


To list $R \cap {\bf Z}^2$ in $\,\tilde{\!O}(|R|)$ time:


i) Partition $R$ into about $\log\_2 N$ parts $R\_1,R\_2,\ldots R\_k$
where $R\_j = \{(m,n) \in R \colon 2^{-j} N \leq n < 2^{1-j} N$.
The $R\_j$ are all equivalent under affine transformations
(except for $R\_k$ [unless $N$ is exactly a power of $2$],
but $R\_k$ is negligible anyway). Then do the remaining steps for each $j$.


ii) Inscribe $R\_j$ in an ellipse $E\_j$ whose area is $O(|R\_j|)$.
For example $E\_j$ might be
$$
\{ (x,y) \in {\bf R}^2 \colon 
\frac{4^{j+1}}{N^2}\Bigl(x - \frac32 2^{-j} N\Bigr)^2
+ \frac {2^{j-1}\tau}{N} (\alpha x - y)^2 \leq 2 \}
$$
if I did the algebra right.


iii) Choose an affine transformation $T\_j$ that takes $E\_j$ to the
unit circle $D\_1: X^2 + Y^2 \leq 1$.


iv) Apply $2$-dimensional lattice basis reduction 
(a.k.a.\ the Euclidean algorithm) to $T\_j {\bf Z}^2 - T\_j (0,0)$.
Use the reduced basis to efficiently list $D\_1 \cap T\_j {\bf Z}^2$, 
and thus $E\_j \cap {\bf Z}^2$.


v) Check whether each of the resulting integer vectors $(m,n)$ 
is actually in $R\_j$, and output those that pass this test
(which should be roughly the constant fraction $|R\_j| \, / \, |E\_j|$),
**QEF**.


