Find the simplest rational number between two given rational numbers

Question

I found a problem related to rational numbers.

Two rational numbers are given and the task is to find the simplest rational number between them.

For this problem, the simplicity of a rational number could be defined as the rational number with the smallest numerator, although I am open to other suggestions for this metric, e.g. similar question to Math stack exchange, if it makes the solution easier.

The sample inputs and output might be:

Inputs: 1110/416 and 1110/417, Output: 8/3
Inputs: 500/166 and 500/167, Output: 3/1

Any ideas or at least an advice on how to approach this problem? I'm struggling.

Thanks

EDIT:

Additional observations:

• Although there are infinitely many rational numbers between two given rational numbers, there are indeed finitely many rational numbers that are simpler than the two.
• The trivial solution could be just to try all combinations of numerator/denominator (ranging from 1 to the highest numerator or denominator respectively), reduce them, and see if the number is in between. I'm not sure what would be the O complexity of it, but I'd guess something like n².

Vieira

Are you including the two endpoints? So if one of them were the simplest, you'd pick it? – Kakaaba

It doesn't matter really, for simplicity the endpoints can be included. – Schottische

I’d think that smallest denominator would be the simplest... – Melaniamelanic

@RBarryYoung: It turns out that "smallest denominator" and "smallest numerator" end up being pretty much equivalent criteria. More precisely, "smallest denominator, using the absolute value of the numerator to break ties" and "smallest absolute value of numerator, using the denominator to break ties" both determine the same fraction in any given interval. There's a unique simplest fraction in any interval (at least, any interval that contains at least one fraction), and no other fraction in that interval will have numerator or denominator smaller than the simplest one. – Hectare

... so even metrics like abs(numerator) + denominator or numerator^2 + denominator^2 all end up producing the same fraction for a given interval. A related analysis is here: math.stackexchange.com/a/115656/117283 – Hectare

A simple and efficient approach to this is en.wikipedia.org/wiki/Euclidean_algorithm – Debenture

Answer 1

The relevant math is described in the Wikipedia article on continued fractions. In a nutshell, you compute the two continued fractions for the lower and upper endpoints and then try four combinations where the continued fraction is truncated after the common endpoint.

Here's a Python implementation.

import fractions


F = fractions.Fraction


def to_continued_fractions(x):
    a = []
    while True:
        q, r = divmod(x.numerator, x.denominator)
        a.append(q)
        if r == 0:
            break
        x = F(x.denominator, r)
    return (a, a[:-1] + [a[-1] - 1, 1])


def combine(a, b):
    i = 0
    while i < len(a) and i < len(b):
        if a[i] != b[i]:
            return a[:i] + [min(a[i], b[i]) + 1]
        i += 1
    if i < len(a):
        return a[:i] + [a[i] + 1]
    if i < len(b):
        return a[:i] + [b[i] + 1]
    assert False


def from_continued_fraction(a):
    x = fractions.Fraction(a[-1])
    for i in range(len(a) - 2, -1, -1):
        x = a[i] + 1 / x
    return x


def between(x, y):
    def predicate(z):
        return x < z < y or y < z < x

    return predicate


def simplicity(x):
    return x.numerator


def simplest_between(x, y):
    return min(filter(between(x, y), (from_continued_fraction(combine(a, b)) for a in to_continued_fractions(x) for b in to_continued_fractions(y))), key=simplicity)


print(simplest_between(F(1110, 416), F(1110, 417)))
print(simplest_between(F(500, 166), F(500, 167)))

Chancemedley

What's the worst case running time of to_continued_fractions? Does taking the numerator as the size of the input make sense for this? – Kakaaba

@DaveGalvin O(log numerator) divisions. – Chancemedley

@DavidEisenstat: Could you expand a bit more on why to try four combinations? It's not completely clear for me. I tried and studied the continued fractions math and came up with a following algorithm: Simultaneously expand both fractions to two sequences of continued fractions coefficients. On the first coefficient that they differ, take the lower coefficient of the two + 1. Then compute the resulting fraction from this sequence of continued fraction coefficients. Any ideas on this approach? – Schottische

@TomPažourek If you apply this to (say) the interval (3, 4), then you get 4, which isn't strictly between 3 and 4. You need to combine [3] -> 3 with [3;1] -> 4 to get the proper answer [3;2] -> 7/2. If you don't care about endpoint treatment, then that probably works. – Chancemedley

@DavidEisenstat: I see, thanks for the clarification. But if I included the endpoints so that the interval would be rather [3,4] than (3,4), it would be correct, wouldn't it? – Schottische

@TomPažourek No, because that routine returns 4, which is less simple than 3. – Chancemedley

@DavidEisenstat: You're right. Thanks for your help. – Schottische

Answer 2

Here's a variation on David Eisenstat's excellent answer above. Secretly, it's based on exactly the same principle of finding the common initial part of the continued fraction expansions of the interval endpoints, but that's not obvious from the way it's coded up, and it's straightforward to give a proof of correctness without needing to reference the theory of continued fractions. A sketch of that proof is given further below.

As a reminder, the aim is to find the simplest fraction in a given interval. Here simplest has a specific (and quite strong) meaning: we'll say that a fraction x = s/t is simpler than a fraction y = u/v (both written in lowest terms) if abs(s) <= abs(u) and t <= v and at least one of those two inequalities is strict. Note that with this definition simpler does not give rise to a total ordering: neither of the fractions 2/5 or 3/4 is simpler than the other; nevertheless, it's a (not immediately obvious) theorem that any subinterval of the real line that contains at least one fraction contains a simplest fraction—a fraction that's simpler than all other fractions in the subinterval.

The code

Without further ado, here's some Python code for our version of simplest_between. Explanations and a sketch of proof of correctness follow.

def simplest_between(x: Fraction, y: Fraction) -> Fraction:
    """
    Simplest fraction strictly between fractions x and y.
    """
    if x == y:
        raise ValueError("no fractions between x and y")

    # Reduce to case 0 <= x < y
    x, y = min(x, y), max(x, y)
    if y <= 0:
        return -simplest_between(-y, -x)
    elif x < 0:
        return Fraction(0, 1)

    # Find the simplest fraction in (s/t, u/v)
    s, t, u, v = x.numerator, x.denominator, y.numerator, y.denominator
    a, b, c, d = 1, 0, 0, 1
    while True:
        q = s // t
        s, t, u, v = v, u - q * v, t, s - q * t
        a, b, c, d = b + q * a, a, d + q * c, c
        if t > s:
            return Fraction(a + b, c + d)

Explanation

The first part of the code—the reduction to the case where 0 <= x < y—should be self-explanatory: if the interval (x, y) lies entirely in the negative reals, we use symmetry about zero and find the simplest fraction in (-y, -x), and then negate. Otherwise, if the interval (x, y) contains zero, then 0/1 is the simplest fraction in (x, y). Otherwise, (x, y) lies within the positive reals and we move on to the second part of the code.

The second part is where it gets more interesting. At each step of the algorithm:

• s, t, u and v are nonnegative integers that describe a subinterval J = (s/t, u/v) of the positive real line (v can be zero, so that u/v represents an infinite endpoint).
• a, b, c and d are nonnegative integers that describe a linear fractional transformation T : z ↦ (az + b) / (cz + d).
• T gives a bijection between J and the original interval (x, y)
• ad-bc = ±1 (the sign alternates with each iteration)

Initially, J = (s/t, u/v) is the original interval (x, y) and T is the identity transformation (given by a = d = 1, b = c = 0). The while loop repeatedly replaces J with the interval 1/(J - q), where q is the floor of the left endpoint of J, and simultaneously updates a, b, c and d correspondingly in order to maintain the bijection T between J and (x, y).

The loop exits as soon as the interval J contains 1. Termination of the loop is guaranteed: the sum s + t + u + v is a positive integer which strictly decreases at every iteration, with the possible exception of the first iteration (where q can be 0).

At loop exit, every fraction in (x, y) has the form (ap + bq)/(cp + dq) for some fraction p/q (with gcd(p, q) = 1) in J; moreover, the expression (ap + bq)/(cp + dq) is already in lowest terms: this follows from gcd(p, q) = 1 together with ad - bc = ±1. Since a, b, c and d are all nonnegative, it follows that (a+b)/(c+d) is the simplest fraction in (x, y).

What about closed intervals?

As with David's answer, simplest_between always produces a fraction strictly between the given endpoints. The next variant is very similar, but produces the simplest fraction within a given closed interval [x, y] instead.

def simplest_between_lax(x: Fraction, y: Fraction) -> Fraction:
    """
    Simplest fraction between fractions x and y, inclusive of x and y.
    """
    # Reduce to case 0 < x <= y
    x, y = min(x, y), max(x, y)
    if y < 0:
        return -simplest_between_lax(-y, -x)
    elif x <= 0:
        return fractions.Fraction(0, 1)

    # Find the simplest fraction in [s/t, u/v]
    s, t, u, v = x.numerator, x.denominator, y.numerator, y.denominator
    a, b, c, d = 1, 0, 0, 1
    while True:
        q = (s - 1) // t
        s, t, u, v = v, u - q * v, t, s - q * t
        a, b, c, d = b + q * a, a, d + q * c, c
        if t >= s:
            return fractions.Fraction(a + b, c + d)

Here are the examples for the OP's inputs:

>>> F = fractions.Fraction
>>> simplest_between(F(1110, 416), F(1110, 417))
Fraction(8, 3)
>>> simplest_between(F(500, 166), F(500, 167))
Fraction(3, 1)

The closed-interval version produces the same results, of course:

>>> simplest_between_lax(F(1110, 416), F(1110, 417))
Fraction(8, 3)
>>> simplest_between_lax(F(500, 166), F(500, 167))
Fraction(3, 1)

But simplest_between_lax allows the endpoints to be considered:

>>> simplest_between(3, 4)
Fraction(7, 2)
>>> simplest_between_lax(3, 4)
Fraction(3, 1)
>>> simplest_between(F(7, 6), F(6, 5))
Fraction(13, 11)
>>> simplest_between_lax(F(7, 6), F(6, 5))
Fraction(6, 5)

Hectare

This is a neat solution. I'm trying to understand is how this solution avoids the need to try the four possibilities (arising from each endpoint having two continued-fraction representations) that David Eisenstat mentioned. – Tass

@Tass With careful bookkeeping, that need doesn't really exist; part of the reason that I wrote this answer is that the "try all four variations" part of the Wikipedia article seemed unnecessarily sloppy. The bookkeeping simply consists of keeping track of whether endpoints are open or closed, and perfoming divisions accordingly. In the case of open intervals it's mostly hidden. You can see the general case here (note the w and t values). – Hectare

Disclaimer: just in case it wasn't clear, that link in the previous comment is to my own code, so should not be seen as any kind of independent corroboration. – Hectare

Answer 3

Let's say a numerator is good if there is some denominator that results in a rational number between your inputs.

You can check if a numerator is good in O(1). Say you want to check a numerator n, and your inputs are w,x (for w/x) and y,z (for y/z).

n is good if there is an integer between nx/w, and nz/y.

Then, you can do this in O(good numerator) by checking all numerators until you find one that's good. If the endpoints are valid, this takes at most min(w,y).

Kakaaba

In your example, when you check 8 you'd see that 8*416/1110=2.9981... and 8*417/1110=3.0054... – Kakaaba

You can also check potential denominators in order since the lowest denominator will go with the lowest numerator. If your inputs are generally >1 this will be faster. – Kakaaba

There may be a sublinear approach involving continued fractions (e.g. calculating out to the first difference), but I'm at work... will think on it tonight. – Kakaaba

Thanks for the insights. Definitely some interesting ideas here. I'm at work as well and will need to think it through to understand it properly. – Schottische

You say that it takes at most min(w,y). Don't I need to check all "good numerators" to see which one of them is the simplest of those (i.e. minimal)? There is a possibility of having multiple "good" numerators between the endpoints, isn't it? – Schottische

Also, could you expand a little bit more on the idea n is good if there is an integer between nx/w, and nz/y.? I know that it might be something trivial I'm missing, but I still cannot get it completely -- how does the existence of integer between nx/w and nz/y imply that there's a denominator m so that n/m is between x/w and y/z? – Schottische

@TomPažourek: If you test possible numerators in increasing order, you can stop as soon as you hit one that turns out to be "good", since this will by definition be the smallest "good" numerator. If the endpoints (namely, w/x and y/z) are themselves allowed as answers, then it takes at most min(w, y) because w and y are both "good" numerators (since if we choose w as the numerator, we can choose x as the denominator to get w/x, and similarly if we choose y as the numerator then we can choose z as the denominator to get y/z). So we only need to test numerators below min(w, y) for goodness. – Guarneri

@TomPažourek: Regarding n is good if there is an integer between nx/w, and nz/y: Assume that there is an integer i between nx/w and nz/y, i.e. for some integer i, i <= nx/w and i >= nz/y both hold. For the first inequality, i <= nx/w, notice that it can be rearranged to w/x <= n/i by multiplying both sides by w/(xi). Likewise the second can be rearranged to y/z >= n/i by multiplying both sides by y/(zi). I.e. there is some integer i such that x/w <= n/i and n/i <= y/z both hold. These are exactly the conditions needed to conclude that n is a good denominator. – Guarneri

@TomPažourek: In the other direction, assume that n is a good denominator. Then we know that there is an integer i such that x/w <= n/i and n/i <= y/z both hold. Doing the same steps as before, but in reverse (i.e., dividing both sides of the first inequality by w/(xi), and both sides of the second by y/(zi)), we conclude that there is an integer i such that i <= nx/w and i >= nz/y both hold. Since we've established that "n is a good numerator" implies "there is an integer between nx/w, and nz/y" and vice versa for all n, the two statements are equivalent. – Guarneri

Thanks for a thorough explanation, it's perfectly clear now. I'll write some code and try it out in practice. – Schottische

Answer 4

You could try the following O(n^2 log n) algorithm:

• Loop from one numerator to the other
• Inside this loop, loop from one denominator to the other. The lemma is that each fraction created by the loop is between the two end fractions.
• For each fraction, simplify it by finding the greatest common divisor of the numerator and denominator, and divide the numerator by it. That should enable you to find the smallest numerator. Euclid's algorithm does this in O(log n).

Joe

I tried to perform the algorithm in my head for inputs 1110/416 and 1110/417, however I didn't find the expected output 8/3. I think the issue is when trying to find fractions between the two inputs. How would you do the loop? There are infinitely many rational numbers between two rational numbers. – Schottische