在两个给定的有理数之间找到最简单的有理数

Question

我发现了一个与有理数相关的问题。

给定两个有理数，任务是找出它们之间最简单的有理数。

对于这个问题，有理数的简单性可以定义为分子最小的有理数，尽管我对这个指标的其他建议持开放态度，例如similar question to Math stack exchange，如果它使解决方案更容易。

示例输入和输出可能是：

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

关于如何解决这个问题有任何想法或至少是建议吗？我在挣扎。

谢谢

编辑：

补充观察：

虽然给定的两个有理数之间有无穷多个有理数，但比这两个更简单的有理数确实有无穷多个
简单的解决方案可能只是尝试 numerator/denominator 的所有组合（分别从 1 到最高分子或分母），减少它们，看看数字是否介于两者之间。我不确定它的 O 复杂度是多少，但我猜是 n².

Answer 1

您可以尝试以下 O(n^2 log n) 算法：

从一个分子循环到另一个分子
在这个循环中，从一个分母循环到另一个。引理是循环创建的每个分数都在两个结束分数之间。
对于每个分数，通过找到分子和分母的最大公约数来简化它，然后用它除以分子。这应该能让你找到最小的分子。 Euclid 算法 在 O(log n) 中执行此操作。

Answer 2

假设分子是好的，如果有一些分母在您的输入之间产生有理数。

您可以在 O(1) 中检查分子是否合适。假设您要检查分子 n，您的输入是 w,x（对于 w/x）和 y,z（对于 y/z）。

如果 nx/w 和 nz/y 之间有一个整数，那么

n 是好的。

然后，您可以在 O(good numerator) 中通过检查所有分子直到找到一个好的分子来执行此操作。如果端点有效，则最多需要 min(w,y).

Answer 3

continued fractions 上的维基百科文章中描述了相关数学。简而言之，您计算下端点和上限端点的两个连分数，然后尝试四种组合，其中连分数在公共端点之后被截断。

这是一个 Python 实现。

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 4

这是上述 David Eisenstat's excellent 的变体。秘密地，它基于完全相同的原则，即找到区间端点的连分式展开的公共初始部分，但从它的编码方式来看，这并不明显，并且无需引用就可以直接给出正确性证明连分数理论。下面进一步给出了该证明的草图。

提醒一下，目的是在给定区间内找到最简单的分数。这里 simplest 有一个特定的（而且非常强）的含义：我们会说分数 x = s/t 比分数 更简单 =16=] （都是用最低的术语写的）如果 abs(s) <= abs(u) and t <= v and 这两个中的至少一个不平等是严格的。请注意，使用此定义 simpler 不会产生总排序：分数 2/5 或 3/4 都不比另一个更简单；尽管如此，这是一个（不是很明显）定理，即包含至少一个分数的实线的任何子区间都包含一个 最简单的 分数 - 一个比子区间中所有其他分数更简单的分数。

密码

事不宜迟，下面是我们 simplest_between 版本的一些 Python 代码。下面是解释和正确性证明的草图。

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)

说明

代码的第一部分——简化为 0 <= x < y 的情况——应该是不言自明的：如果区间 (x, y) 完全位于负实数，我们使用关于零的对称性并找到最简单的分数在 (-y, -x) 中，然后求反。否则，如果区间 (x, y) 包含零，则 0/1 是 (x, y) 中最简单的分数。否则，(x, y) 位于正实数范围内，我们继续执行代码的第二部分。

第二部分变得更有趣了。在算法的每一步：

s、t、u 和 v 是描述 a 的非负整数正实线的子区间J = (s/t, u/v) (v 可以为零，因此 u/v 表示无限端点）。
a、b、c 和 d 是描述 a 的非负整数线性分数变换 T : z ↦ (az + b) / (cz + d).
T 给出 J 和原始区间 (x, y)
ad-bc = ±1（每次迭代符号交替）

最初，J = (s/t, u/v)是原始区间(x, y)，T是身份转换（由 a = d = 1、b = c = 0 给出）。 while循环将J重复替换为区间1/(J - q)，其中q为J左端点的floor，同时更新a，b, c 和 d 对应地保持双射 T J 和 (x, y).

只要区间 J 包含 1，循环就会退出。终止循环是有保证的：总和 s + t + u + v 是一个正整数，它在每次迭代中都严格递减，但第一次迭代可能是例外（其中 q 可以是 0）。

在循环退出时，(x, y) 中的每个分数对于 J 中的某些分数 p/q（带有 gcd(p, q) = 1）具有 (ap + bq)/(cp + dq) 的形式；此外，表达式 (ap + bq)/(cp + dq) 已经是最低限度的术语：这是从 gcd(p, q) = 1 和 ad - bc = ±1 得出的。由于 a、b、c 和 d 都是非负的，因此 (a+b)/(c+d) 是 (x, y).[=84 中最简单的分数=]

闭区间呢？

与 David 的回答一样，simplest_between 总是在给定的端点之间 严格地 产生一个分数。下一个变体非常相似，但在给定的 closed 间隔内生成最简单的分数 [x, y] 相反。

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)

以下是 OP 输入的示例：

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

闭区间版本产生相同的结果，当然：

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

但是 simplest_between_lax 允许考虑端点：

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

在两个给定的有理数之间找到最简单的有理数

Find the simplest rational number between two given rational numbers

language-agnostic

algorithm

math

rational-numbers

fractions

密码

说明

闭区间呢？