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