I have a (transcendental) constant $\alpha$ and a fixed parameter $\varepsilon>0.$ I'd like to find all positive integers $n<\ell$ for which $\|n\alpha\|<\varepsilon,$ where $\|x\|$ is the distance between $x$ and the nearest integer. Is there a good way to do this?
The first natural thought is to use continued fractions but at best this would give me a few good examples rather than all of the numbers in the range.
For concreteness let's say $\ell>10^{10}$ and $\varepsilon\approx\ell/\log\ell$. In short I'm searching a big range for integers which are very close to a multiple of $\alpha.$
If you know how to solve problems of the form "find the least integer $n(\eta) \ge 1$ such that $n\alpha \in [- \eta - \varepsilon; - \eta + \varepsilon] \pmod 1$" where $|\eta| \le \varepsilon$, then you can easily find all those integers one after the other.
Thus, you want to keep a list of the integers $n$ such that $n \alpha$ is closer to $0$ than for any other smaller multiple. You need two lists, one made of the positive records and one of the negative records (those will contain the multiples corresponding to the continued fractions, so they are still relevant to the problem).
Both lists start with $n=1$, corresponding to $+(\alpha-\lfloor \alpha \rfloor)$ and $-(\lceil \alpha \rceil - \alpha)$. To continue the lists, one can prove by induction that the next record is the sum of the two current records. Add it to the list corresponding to its sign, and repeat. Once the difference between the two current records gets smaller than $2\varepsilon$, you can stop, and use the few records smaller than $2\varepsilon$ to compute the piecewise constant function $n(\eta)$ for $|\eta| \le \varepsilon$.
Finally, you obtain the sequence you want recursively by $N_0 = n(0)$ and $N_{k+1} = N_k + n(N_k \alpha \mod 1)$.
For example, suppose you want to find the multiples of $\sqrt 2$ that are less than $10^{-2}$ to an integer. Modulo $1$, you have the following records :
$\begin{matrix}1\sqrt 2 & = + 0.4142 & = -0.5857 \\ 2\sqrt 2 && = -0.1715 \\ 3\sqrt 2 &= +0.2426& \\ 5\sqrt 2 &= +0.0711& \\ 7\sqrt 2 &&= -0.1005 \\ 12\sqrt 2 &&= -0.0294 \\ 17\sqrt 2 &= +0.0416& \\ 29\sqrt 2 &= +0.0122& \\ 41\sqrt 2 &&= -0.0172 \\ 70\sqrt 2 &&= -0.0051\end{matrix} $.
Since $29\sqrt 2 = +0.0122$ and all the previous values are bigger than $0.02$, this shows that $n(\eta) = 29$ for $|\eta + 29\sqrt 2| \le 0.01 \pmod 1$, which means $\eta \in [-0.01 ; -0.0022] = [-0.01 ; -29\sqrt 2 + 41.01]$
Next, we have $n(\eta) = 41$ for the remaining $\eta$ satisfying $|\eta + 41\sqrt 2| \le 0.01 \pmod 1$, which means $\eta \in [+0.0072 ; +0.01] = [-41\sqrt 2 + 57.99 ; +0.01]$.
Finally, we have $n(\eta) = 70$ for the remaining $\eta$ satisfying $|\eta + 70\sqrt 2| \le 0.01 \pmod 1$, which means $\eta \in [-0.0022 ; +0.0072] = [-29\sqrt 2 + 41.01 ; -41\sqrt 2 + 57.99]$.
So if the current multiple falls in $[-0.01 ; -0.0022]$, we add $29\sqrt 2$, if it falls in $[-0.0022 ; +0.0072]$, we add $70\sqrt 2$, if it falls in $[+0.0072 ; +0.01]$, we add $41\sqrt 2$ :
Now we obtain the sequence :
$70\sqrt 2 = -0.0051\\ 99\sqrt 2 = +0.0071 \\ 169\sqrt 2 = +0.0021 \\ 239\sqrt 2 = -0.0030 \\ 268\sqrt 2 = +0.0092 \\ 309\sqrt 2 = -0.0080 \\ \ldots$
If you want to skip ahead and start from $\ell_1$, it's a bit more difficult, because from $\ell_1 \alpha$ you have to to solve a problem of the form "find the smallest $n$ such that $n\alpha$ is in such interval of length $2\varepsilon$", and this interval is unlikely to contain $0$. To find that first integer, you need to enlarge the target interval so that it contains $0$, then use the list of records to solve the problem with the enlarged interval. You will then get a bit closer to the target interval, so the next target interval will be closer to $0$, and repeat.