It turns out that the converse theorems to the ones I stated before

about convergents and semiconvergents are

a/M a convergent to b/N ==> |a/M - b/N| < 1/M^2

a/M a semiconvergent to b/N ==> |a/M - b/N| < 2/M^2

From this we can get

(EZ converse)

If b/N is a generator for a MOS with M scale steps out of an N-rt,

then there exists an a/b such that

|a/b - M/N| < 2/(bM)

Proof: Multiply both sides of

|a/M - b/N| < 2/M^2

by M/b.

If b<M/2, we can replace the above condition by

|a/b - M/N| < 1/b^2

and so we need look only at semiconvergents to M/N. If b<M/4 then we

can replace the above condition by

|a/b - M/N| < 1/2b^2

and we only need the convergents to M/N.

However, we have a nice, general algorithm:

(EZ integers) If b/N is a generator for an M-in-N system, then

|aN - bM| < 2N/M.

Proof: Multiply both sides of

|a/M - b/N| < 2/M^2

by MN.

We then need only check a finite list of values of e up to

+-floor(2N/M) in the equation aN - bM = e. This equation is easily

solved, since modulo N it reduces to b = -e/M (mod N) and mod M it

reduces to a = e/N (mod M), where the congruences are solvable since

M and N are relatively prime. The usual way of solving such

congruences is again via the Euclidean algorithm/continued fractions,

the inverse up to sign can be found from |pN - qM| = 1, where p/q is

the penultimate convergent to M/N. This means that if you want find

all the MOS where M and N are both very large it's actually not that

hard so long as N is not a great deal larger than M. (What's hard is

figuring out the practical utility of doing so.)