确定 n 次 Farey 序列的最有效方法是什么？

Question

我将实现一个 Farey 分数近似，将有限精度的用户输入转换为可能重复的有理数。
http://mathworld.wolfram.com/FareySequence.html

我可以轻松找到最接近的 Farey 分数在一个序列中，我可以通过构建 Stern-Brocot 树递归搜索中位数分数来找到 Fn。
http://mathworld.wolfram.com/Stern-BrocotTree.html

但是，该方法我想出了在序列 Fn 中查找分数的方法似乎效率很低：
（伪）

For int i = 0 to fractions.count -2
{
    if fractions[i].denominator + fractions[i+1].denominator < n
    {    
        insert new fraction(
            numerator = fractions[i].numerator + fractions[i+1].numerator
            ,denominator = fractions[i].denominator + fractions[i+1].denominator)
            //note that fraction will reduce itself
        addedAnElement = true
    }
}
if addedAnElement 
    repeat

我几乎总是定义序列 Fn 其中 n = 10^m 其中 m > 1

所以也许最好一次构建序列并缓存它......但它似乎仍然存在应该是更好的导出方式。

编辑：
这篇论文有一个很有前途的算法：
http://www.math.harvard.edu/~corina/publications/farey .pdf

我会尝试实现。
问题在于他们的“最有效”算法需要知道前两个元素。我知道任何序列的第一个元素都是 1/n 但找到第二个元素似乎是一个挑战...

EDIT2:
我不知道我是如何忽略这一点的：
给定 F0 = 1/n
如果x＞ 2 然后
F1 = 1/(n-1)

因此对于所有 n > 1 2、前两个分数总是
1/n，1/(n-1)，我可以实现 Patrascu 的解决方案。

所以现在，我们这个问题的答案应该证明这个解决方案是或不是使用基准测试的最佳解决方案。

Answer 1

为什么你需要 Farey 系列？使用连分数将为您提供相同的在线近似值，而无需预先计算级数。

Answer 2

Farey 序列中的相邻分数在第 2 节中进行了描述。 Farey 子序列中的 3 个相邻分数，http://arxiv.org/abs/0801.1981 。