How to compute next/previous representable rational number?

Check out the next link: http://en.wikipedia.org/wiki/Farey_sequence . In general, Farey sequence is dealing exactly with that type of question.

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.

As I mentioned in a closely related question, this has a very beautiful geometrical interpretation employing Pick's Area Theorem: $\rm\: a/b < c/d\:$ are two adjacent terms in a Farey sequence iff the triangle $\rm T$ with vertices $\rm (0,0), u = (b,a), v = (d,c)$ contains no lattice points except for vertices. By Pick's formula this is true iff $\rm\ area\ T = $ #interior_points $\ +\ 1/2\ $ #boundary_points $\:-\ 1\ =$ $\ 0 + 3/2 - 1 = 1/2\:.$ But by basic analytic geometry $\rm\: area\ T\: =\: |det(u,v)|/2 = |ad-bc|/2\:.\:$ Hence $\rm\:a/b,\:c/d\:$ are meighbors in some Farey sequence iff $\rm\:|ad-bc| = 1\:.\:$

Therefore the problem reduces to solving the linear Diophantine equation $\rm\:ax+by = 1\:.\:$ As is well-known, such equations may be solved by employing the extended Euclidean algorithm, which is conveniently implemented by performing the Euclidean algorithm in parallel on an identity-augmented system of equations. For an example worked-out in detail see my post here.

In fact it deserves to be much better known that Pick originally applied his area formula in a similar way to give a beautiful geometric proof of the Bezout linear representation of the gcd.