8

It is well known that the sequence $\operatorname{frac}(na)$ , where $\operatorname{frac}$ denotes the fractional part and $n$ runs over the positive integers, is dense in $[0,1]$.

Suppose, I have an irrational number $a$ and two rational numbers $s,t$ with $0<s<t<1$. Then, there must be a positive integer $n$ with $s<\operatorname{frac}(na)<t$.

How can I efficiently calculate the smallest positive integer $n$ with the desired property ?

I tried the best approximations related to the continued fraction of $a$, but these only help to find integers $m,n$ , such that $|na-m|$ is very small.

I also thought about the possibility of using the lindep-command of PARI/GP, but the problem is that I need integers with $na-m-u\approx 0$ , where $u$ could, for example be $\frac{s+t}{2}$. But as far as I know, I cannot fix the coefficient belonging to $u$ to be $-1$, in which case I could find possible solutions.

But even if this were possible, the solution might not give the smallest value $n$ doing the job.

Any ideas?

egreg
  • 238,574
Peter
  • 84,454
  • We can probably adapt the continued fraction algorithm, maybe along this line. Wait until $0 < T(a) := {m_0 a} <a$. If we have encountered $(s,t)$, then finish. Otherwise, remember $n_0$ such that $n_0 a \leq s < t \leq (n_0+1) a$. Start again with the rotation $T(a)/a$ and the set $(s/a-n_0, t/a-n_0)$. Find $m_1$ and $n_1$. Iterate. At the end, I guess that the result should look like $n_0+m_0 (n_1+\ldots)$. – D. Thomine Oct 12 '16 at 12:26
  • you can use the continued fraction method until you get some $n$ with $|{n\alpha}| < t-s$, use a suitable multiple $m$ of this $n$ to get ${m\alpha} \in [s ; t]$, and then go backwards from $m$ just like in the second part of http://math.stackexchange.com/questions/366044/finding-near-integers-in-a-range – mercio Oct 12 '16 at 12:38
  • in fact I adressed your generalization in the end of my answer there. – mercio Oct 12 '16 at 12:46

0 Answers0