farey sequences - How to compute next/previous representable rational number?

An (approximate) non-negative rational number representation is a pair of natural numbers each not greater than some fixed limit M (and of course denominator being non-zero).

With this condition there is finite number of representable rational numbers. This means that for each such number we can name previous and next number in the set (of course except for smallest 0 and largest 1). How to compute them?

In other words lets have a set of numbers

$$R(M)=\{\frac{p}{q} : p,q\in\mathbb{N},q\neq0,p\leq q\leq M\}$$

where $M\in\mathbb{N}_+$

and given number $\frac{p_1}{q_1}\in R(M)$.

I want to find numbers $\frac{p_S}{q_S}\in R(M)$ and $\frac{p_L}{q_L}\in R(M)$ (if they exist) such that

$$\frac{p_S}{q_S}<\frac{p_1}{q_1} \wedge \neg\exists_{\frac{p}{q}\in R(M)}\frac{p_S}{q_S}<\frac{p}{q}<\frac{p_1}{q_1}$$

and smilarly

$$\frac{p_L}{q_L}>\frac{p_1}{q_1} \wedge \neg\exists_{\frac{p}{q}\in R(M)}\frac{p_1}{q_1}<\frac{p}{q}<\frac{p_L}{q_L}$$

Answer

All this needs is a single modular inversion, with complexity $O(\log M \log \log M)$ (or something like that).

We are given $p/q$ in lowest terms, with $p, q \in \mathbb{N}$ and $q > 0$. We want the nearest neighbours of $p/q$, $a/b < p/q < c/d$, subject to $a,b,c,d \in \mathbb{N}$ and $c,d > 0$. Assume for the moment that $p < q$.

Consider $c/d$. It is the element after $p/q$ in the Farey sequence $F_n$, which means that $cq - dp = 1$. In particular, $dp+1 = 0 \pmod q$, i.e. $d = -1/p \pmod q$. So let

$r = 1/p \pmod q$

Now make $d$ as big as possible, subject to (i) $d = -r \pmod q$ and (ii) $d \leq n$. Then just put $c = (dp+1)/q$.

Similarly, to calculate $a/b$, make $b$ as big as possible subject to (i) $b = +r \pmod q$ and (ii) $b \leq n$. Then put $a = (bp-1)/q$.

An example Suppose $p/q = 28/61$ and $n=100$. Then the inverse of $28 \pmod{61}$ is $r=24$. So $d = 37 \pmod{61}$, and we can take $d=98$, with $c=(98.28+1)/61 = 45$. And $b = 24 \pmod{61}$, so we can take $b = 85$, with $a = (85.28-1)/61=39$. So we get:

$39/85 < 28/61 < 45/98$

We only have to modify this slightly to handle the case $p > q$: instead of computing the largest $d \leq n$ that satisfies the modulo requirement, we find the corresponding modulo requirement for $c$, and then look for the largest such $c \leq n$. You can fill in the details for yourself.