How to find the fraction of integers with the smallest denominator matching an interval?

Question

I have a real interval $\mathbb{S} \subset ]0; 1[$.

How can I find the smallest $n \in \mathbb{N}$, for which there is a $k \in \mathbb{N}$, for which $\frac{k}{n} \in \mathbb{S}$?

¹_{The important thing is to do this effectively. For example, just trying all the possible denominators $\frac{1}{d-c}$ for the interval $]c, d[$, would work, but it is obviously not effective (like if we would decide the least common multiple of two natural numbers by trying all the natural numbers smaller than their multiple).}

²_{The problem came into my mind as an interesting, l'art pour l'art programming problem, what I formulated also as a codegolf challenge. However, meanwhile I became curious also to the math side, which can be the optimal algorithm, or a nearly optimal one.}

Answer 1

One simple method is to start with $\frac 01<\Bbb S<\frac11$ and repreatedly, given $\frac ab<\Bbb S<\frac cd$, compute the so-called Farey sum $\frac{a+c}{b+d}$ and check if it is $\in \Bbb S$ or should replace either $\frac ab$ or $\frac cd$.

---

This works because we will in each step have $ad-bc=-1$ (because $a(b+d)-b(a+c)=ad-bc=(a+c)d-(b+d)c$) and then $\frac ab<\frac xy<\frac cd$ implies that the numerators of $\frac xy-\frac ab=\frac{bx-ay}{by}$ and of $\frac cd-\frac xy=\frac{cy-dx}{dy}$ are positive integers and therefore $$y = (bc-ad)y= b(cy-dx)+d(bx-ay)\ge b\cdot 1+d\cdot 1=b+d,$$ i.e., there is no rational with denominator $<b+d$ in the interval $]\frac ab,\frac cd[$.