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².

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)))

Answer 2

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).

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).

Answer 4

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)