Stern–Brocot 樹與 Farey 序列

連分數的樹

有兩種主要方法，可以將所有可能的連分數，合併為有用的樹結構。

Stern–Brocot 樹

定義

Stern–Brocot 樹是一種維護分數的優雅的結構，包含所有不同的正有理數。這個結構由 Moritz Stern 在 1858 年和 Achille Brocot 在 1861 年發現。

解釋

Stern–Borcot 樹從兩個簡單的分數開始：

\[ \frac{0}{1}, \frac{1}{0} \]

這個 \(\frac{1}{0}\) 可能看得你有點懵逼。不過我們不討論這方面的嚴謹性，你只需要把它當作 \(\infty\) 就行了。

每次在相鄰的兩個分數 \(\frac{a}{b},\frac{c}{d}\) 中間插入一個分數 \(\frac{a+c}{b+d}\)，這樣就完成了一次迭代，得到下一個序列。於是它就會變成這樣

\[ \begin{array}{ccccccccc} &&&\dfrac{0}{1}, & \dfrac{1}{1}, & \dfrac{1}{0} &&&\\\\ &&\dfrac{0}{1}, & \dfrac{1}{2}, & \dfrac{1}{1}, & \dfrac{2}{1}, & \dfrac{1}{0} &&\\\\ \dfrac{0}{1}, & \dfrac{1}{3}, & \dfrac{1}{2}, & \dfrac{2}{3}, & \dfrac{1}{1}, & \dfrac{3}{2}, & \dfrac{2}{1}, & \dfrac{3}{1}, & \dfrac{1}{0} \end{array} \]

既然稱它為 Stern–Brocot 樹，那麼它總得有一個樹的樣子。來一張圖：

可以把第 \(i\) 層的序列當作是深度為 \(i-1\) 的 Stern–Brocot 樹的中序遍歷。

性質

接下來討論 Stern–Brocot 樹的性質。

單調性

在每一層的序列中，真分數是單調遞增的。

略證：只需要在 \(\frac{a}{b}\le \frac{c}{d}\) 的情況下證明

\[ \frac{a}{b}\le \frac{a+c}{b+d}\le \frac{c}{d} \]

就行了。這個很容易，直接做一下代數變換即可

\[ \begin{aligned} & \frac{a}{b}\le \frac{c}{d} \\ \implies & ad\le bc \\ \implies & ad+ab\le bc+ab \\ \implies & \frac{a}{b}\le\frac{a+c}{b+d} \end{aligned} \]

另一邊同理可證。

最簡性

序列中的分數（除了 \(\frac{0}{1},\frac{1}{0}\)）都是最簡分數。

略證：為證明最簡性，我們首先證明對於序列中連續的兩個分數 \(\frac{a}{b},\frac{c}{d}\)：

\[ bc-ad=1 \]

顯然，只需要在 \(bc-ad=1\) 的條件下證明 \(\frac{a}{b}, \frac{a+c}{b+d}, \frac{c}{d}\) 的情況成立即可。

\[ a(b+d)-b(a+c)=ad-bc=1 \]

後半部分同理。證明了這個，利用擴展歐幾里德定理，如果上述方程有解，顯然 \(\gcd(a,b)=\gcd(c,d)=1\)。這樣就證完了。

有了上面的證明，可以證明 \(\frac{a}{b}<\frac{c}{d}\)。

有了這兩個性質，就可以把它當成一棵平衡樹來做了。建立和查詢就向平衡樹一樣做就行了。

連分數表示與父子節點

遞推 \(\frac{p_k}{q_k}=\frac{a_k p_{k-1} + p_{k-2}}{a_k q_{k-1} + q_{k-2}}\)，意味着連分數表示對樹中 \(\frac{p_k}{q_k}\) 的路徑進行編碼。要查找 \([a_0; a_1, \dots, a_{k}, 1]\)，必須使 \(a_0\) 向右移動，\(a_1\) 向左移動，\(a_2\) 向右移動等等，直到 \(a_k\)。

連分數節點 \([a_0; a_1, \dots, a_k,1]\) 的父節點是沿最後使用的方向後退一步獲得的分數。

換句話説，當 \(a_k>1\) 時，它是 \([a_0; a_1, \dots, a_k-1,1]\)，而當 \(a_k=1\) 時，則是 \([a_0; a_1, \dots, a_{k-1}, 1]\)。

因此，\([a_0; a_1, \dots, a_k, 1]\) 的子節點是 \([a_0; a_1, \dots, a_k+1, 1]\) 和 \([a_0; a_1, \dots, a_k, 1, 1]\)。

索引

為 Stern Brocot 樹編制索引。根頂點被分配了一個索引 \(1\)。然後，對於頂點 \(v\)，通過將 \(v\) 的前導位從 \(1\) 更改為 \(10\) 來分配其左子節點的索引，對於右子節點，通過將前導位從 \(1\) 更改為 \(11\) 來分配索引：

在這種索引中，連分數表示規定了有理數的 遊程長度編碼（run-length encoding）。

對於 \(\frac{5}{2} = [2;2] = [2;1,1]\)，其索引為 \(1011_2\)，其遊程長度編碼（考慮按升序排列的位）為 \([2;1,1]\)。

另一個例子是 \(\frac{2}{5} = [0;2,2]=[0;2,1,1]\)，其索引為 \(1100_2\)，其遊程編碼實際上為 \([0;2,2]\)。

值得注意的是，Stern–Brocot 樹實際上是一個堆。也就是説，它是 \(\frac{p}{q}\) 的二叉樹，它也是 \(p\) 和 \(q\) 的堆。

實現

構建實現

C++Python

void build(int a = 0, int b = 1, int c = 1, int d = 0, int level = 1) {
  int x = a + c, y = b + d;
  // ... output the current fraction x/y
  // at the current level in the tree
  build(a, b, x, y, level + 1);
  build(x, y, c, d, level + 1);
}

def build(a = 1, b = 1, c = 1, d = 0, level = 1):
    x = a + c; y = b + d
    # ... output the current fraction x/y
    # at the current level in the tree
    build(a, b, x, y, level + 1)
    build(x, y, c, d, level + 1)

查詢實現

C++Python

string find(int x, int y, int a = 0, int b = 1, int c = 1, int d = 0) {
  int m = a + c, n = b + d;
  if (x == m && y == n) return "";
  if (x * n < y * m)
    return 'L' + find(x, y, a, b, m, n);
  else
    return 'R' + find(x, y, m, n, c, d);
}

def find(x, y, a = 0, b = 1, c = 1, d = 0):
    m = a + c; n = b + d
    if x == m and y == n:
        return ""
    if x * n < y * m:
        return 'L' + find(x, y, a, b, m, n)
    else:
        return 'R' + find(x, y, m, n, c, d)

例題

比較連分數的大小

對於 \(A=[a_0; a_1, \dots, a_n]\) 和 \(B=[b_0; b_1, \dots, b_m]\)，哪個分數更小？

解答

假設 \(A\) 和 \(B\) 是無理數，它們的連分數表示是 Stern–Brocot 樹中的無限下降。

正如已經提到的，在這個表示中，\(a_0\) 表示下降中右轉的次數，\(a_1\) 表示隨後左轉的次數，依此類推。因此，當比較 \(a_k\) 和 \(b_k\) 時，如果 \(a_k=b_k\)，應該繼續比較 \(a_{k+1}\) 和 \(b_{k+1}\)。否則，如果在右下降，應該檢查是否 \(a_k<b_k\)；如果在左下降，應檢查 \(a_k>b_k\)，以判斷 \(a<b\)。

換言之，對於無理數 \(A\) 和 \(B\)，當且僅當字典序（lexicographical comparison）有 \((a_0, -a_1, a_2, -a_3, \dots) < (b_0, -b_1, b_2, -b_3, \dots)\) 時，將是 \(A<B\)。

現在，正式使用 \(\infty\) 作為連分數表示的元素，可以模擬無理數 \(A-\varepsilon\) 和 \(A+\varepsilon\)，即比 \(A\) 小（大）但比任何其他實數大（小）的元素。具體而言，對於 \(A=[a_0; a_1, \dots, a_n]\)，這兩個元素中的一個可以模擬 \([a_0; a_1, \dots, a_n, \infty]\)，另一個可以模擬 \([a_0; a_1, \dots, a_n - 1, 1, \infty]\)。

哪一個對應於 \(A-\varepsilon\)，哪一個對應於 \(A+\varepsilon\)，可以通過 \(n\) 的奇偶性或通過將它們作為無理數進行比較來確定。

# check if a < b assuming that a[-1] = b[-1] = infty and a != b
def less(a, b):
    a = [(-1)**i*a[i] for i in range(len(a))]
    b = [(-1)**i*b[i] for i in range(len(b))]
    return a < b

# [a0; a1, ..., ak] -> [a0, a1, ..., ak-1, 1]
def expand(a):
    if a: # empty a = inf
        a[-1] -= 1
        a.append(1)
    return a

# return a-eps, a+eps
def pm_eps(a):
    b = expand(a.copy())
    a.append(float('inf'))
    b.append(float('inf'))
    return (a, b) if less(a, b) else (b, a)

最佳內點

對於 \(\frac{0}{1} \leq \frac{p_0}{q_0} < \frac{p_1}{q_1} \leq \frac{1}{0}\)，找到有理數 \(\frac{p}{q}\) 使得 \((q; p)\) 在字典序最小，並且 \(\frac{p_0}{q_0} < \frac{p}{q} < \frac{p_1}{q_1}\)。

解答

就 Stern–Brocot 樹而言，這意味着需要找到 \(\frac{p_0}{q_0}\) 和 \(\frac{p_1}{q_1}\) 的 LCA。由於 Stern–Brocot 樹和連分數之間的聯繫，該 LCA 將大致對應於 \(\frac{p_0}{q_0}\) 和 \(\frac{p_1}{q_1}\) 的連分數表示的最大公共前綴。

因此，如果 \(\frac{p_0}{q_0} = [a_0; a_1, \dots, a_{k-1}, a_k, \dots]\) 和 \(\frac{p_1}{q_1} = [a_0; a_1, \dots, a_{k-1}, b_k, \dots]\) 是無理數，則 LCA 為 \([a_0; a_1, \dots, \min(a_k, b_k)+1]\)。

對於有理數 \(r_0\) 和 \(r_1\)，其中之一可能是 LCA 本身，這需要對其進行討論。為了簡化有理數 \(r_0\) 和 \(r_1\) 的解決方案，可以使用前面問題中導出的 \(r_0 + \varepsilon\) 和 \(r_1 - \varepsilon\) 的連分數表示。

# finds lexicographically smallest (q, p)
# such that p0/q0 < p/q < p1/q1
def middle(p0, q0, p1, q1):
    a0 = pm_eps(fraction(p0, q0))[1]
    a1 = pm_eps(fraction(p1, q1))[0]
    a = []
    for i in range(min(len(a0), len(a1))):
        a.append(min(a0[i], a1[i]))
        if a0[i] != a1[i]:
            break
    a[-1] += 1
    p, q = convergents(a)
    return p[-1], q[-1]

GCJ 2019, Round 2 - New Elements: Part 2

您得到 \(N\) 個正整數對 \((C_i, J_i)\)。您需要找到一個正整數對 \((x, y)\)，這樣 \(C_i x + J_i y\) 就是一個嚴格遞增的序列。

在這類配對中，找到詞典中最小的一對。

解答

重新表述語句，\(A_i x + B_i y\) 對於所有 \(i\) 都必須為正，其中 \(A_i = C_i - C_{i-1}\)，\(B_i = J_i - J_{i-1}\)。

在這些方程中，對於 \(A_i x + B_i y > 0\)，有四個情況：

1. \(A_i, B_i > 0\) 可以忽略，因為正在查找 \(x, y > 0\)。
2. \(A_i, B_i \leq 0\) 將提供「IMPOSSIBLE」作為答案。
3. \(A_i > 0\),\(B_i \leq 0\)。這樣的約束相當於 \(\frac{y}{x} < \frac{A_i}{-B_i}\)。
4. \(A_i \leq 0\),\(B_i > 0\)。這樣的約束相當於 \(\frac{y}{x} > \frac{-A_i}{B_i}\)。

讓 \(\frac{p_0}{q_0}\) 是第四組中最大的 \(\frac{-A_i}{B_i}\)，而 \(\frac{p_1}{q_1}\) 則是第三組中最小的 \(\frac{A_i}{-B_i}\)。

現在的問題是，給定 \(\frac{p_0}{q_0} < \frac{p_1}{q_1}\)，找到一個分數 \(\frac{p}{q}\) 使得 \((q;p)\) 在字典上最小，並且 \(\frac{p_0}{q_0} < \frac{p}{q} < \frac{p_1}{q_1}\)。

    def solve():
    n = int(input())
    C = [0] * n
    J = [0] * n
    # p0/q0 < y/x < p1/q1
    p0, q0 = 0, 1
    p1, q1 = 1, 0
    fail = False
    for i in range(n):
        C[i], J[i] = map(int, input().split())
        if i > 0:
            A = C[i] - C[i-1]
            B = J[i] - J[i-1]
            if A <= 0 and B <= 0:
                fail = True
            elif B > 0 and A < 0: # y/x > (-A)/B if B > 0
                if (-A)*q0 > p0*B:
                    p0, q0 = -A, B
            elif B < 0 and A > 0: # y/x < A/(-B) if B < 0
                if A*q1 < p1*(-B):
                    p1, q1 = A, -B
    if p0*q1 >= p1*q0 or fail:
        return 'IMPOSSIBLE'

    p, q = middle(p0, q0, p1, q1)
    return str(q) + ' ' + str(p)

Calkin–Wilf 樹

定義

在二叉樹中組織連分數的一種更簡單的方法是 Calkin–Wilf 樹。

通常如下所示：

樹的根節點為 \(\frac{1}{1}\)。然後，對於數字為 \(\frac{p}{q}\) 的頂點，其子節點為 \(\frac{p}{p+q}\) 和 \(\frac{p+q}{q}\)。

性質

與 Stern–Brocot 樹不同，Calkin–Wilf 樹不是二叉搜索樹，因此不能用於執行有理二叉搜索。

在 Calkin–Wilf 樹中，當 \(p>q\) 時，分數 \(\frac{p}{q}\) 的直接父節點為 \(\frac{p-q}{q}\)；當 \(p<q\) 時，為 \(\frac{p}{q-p}\)。

在 Stern–Brocot 樹中使用了收斂的遞歸。為了得出連分數和 Calkin–Wilf 樹之間的聯繫，應該使用完整商（complete quotients）的遞歸。如果 \(s_k = \frac{p}{q}\)，則 \(s_{k+1} = \frac{q}{p \mod q} = \frac{q}{p-\lfloor p/q \rfloor \cdot q}\)。

另一方面，當 \(p>q\) 時，在 Calkin–Wilf 樹中重複從 \(s_k = \frac{p}{q}\) 到它的父節點，那麼將以 \(\frac{p \mod q}{q} = \frac{1}{s_{k+1}}\) 結尾。如果繼續這樣做，將以 \(s_{k+2}\)，然後 \(\frac{1}{s_{k+3}}\) 等結尾。由此可以推斷：

1. 當 \(a_0>0\) 時，Calkin–Wilf 樹中 \([a_0; a_1, \dots, a_k]\) 的直接父節點為 \(\frac{p-q}{q}=[a_0 - 1; a_1, \dots, a_k]\)。
2. 當 \(a_0=0\) 且 \(a_1>1\) 時，其直接父節點為 \(\frac{p}{q-p} = [0; a_1 - 1, a_2, \dots, a_k]\)。
3. 當 \(a_0=0\) 且 \(a_1=1\) 時，其直接父節點為 \(\frac{p}{q-p} = [a_2; a_3, \dots, a_k]\)。

相應地，\(\frac{p}{q} = [a_0; a_1, \dots, a_k]\) 的子節點為

1. \(\frac{p+q}{q}=1+\frac{p}{q}\)，即 \([a_0+1; a_1, \dots, a_k]\)。
2. \(\frac{p}{p+q} = \frac{1}{1+\frac{q}{p}}\)，對於 \(a_0>0\)，它是 \([0, 1, a_0, a_1, \dots, a_k]\)；對於 \(a_0=0\)，則是 \([0, a_1+1, a_2, \dots, a_k]\)。

值得注意的是，如果以廣度優先搜索順序枚舉 Calkin–Wilf 樹的頂點（即，根有一個數字 \(1\)，而頂點 \(v\) 的子節點有相應的索引 \(2v\) 和 \(2v+1\)），Calkin–Welf 樹中有理數的索引將與 Stern–Brocot 樹中的索引相同。

因此，Stern–Brocot 樹和 Calkin–Wilf 樹的相同級別上的數字是相同的，但它們的排序通過 位反轉排列（bit-reversal permutation）而不同。

Farey 序列

定義

Stern–Brocot 樹與 Farey 序列有着極其相似的特徵。第 \(i\) 個 Farey 序列記作 \(F_i\)，表示把分母小於等於 \(i\) 的所有最簡真分數按大小順序排列形成的序列。

\[ \begin{array}{lllllllllllll} F_1=\bigg\{&\dfrac{0}{1},&&&&&&&&&&\dfrac{1}{1}&\bigg\}\\\\ F_2=\bigg\{&\dfrac{0}{1},&&&&&\dfrac{1}{2},&&&&&\dfrac{1}{1}&\bigg\}\\\\ F_3=\bigg\{&\dfrac{0}{1},&&&\dfrac{1}{3},&&\dfrac{1}{2},&&\dfrac{2}{3},&&&\dfrac{1}{1}&\bigg\}\\\\ F_4=\bigg\{&\dfrac{0}{1},&&\dfrac{1}{4},&\dfrac{1}{3},&&\dfrac{1}{2},&&\dfrac{2}{3},&\dfrac{3}{4},&&\dfrac{1}{1}&\bigg\}\\\\ F_5=\bigg\{&\dfrac{0}{1},&\dfrac{1}{5},&\dfrac{1}{4},&\dfrac{1}{3},&\dfrac{2}{5},&\dfrac{1}{2},&\dfrac{3}{5},&\dfrac{2}{3},&\dfrac{3}{4},&\dfrac{4}{5},&\dfrac{1}{1}&\bigg\} \end{array} \]

顯然，上述構建 Stern–Brocot 樹的算法同樣適用於構建 Farey 序列。因為 Stern–Brocot 樹中的數是最簡分數，因此在邊界條件（分母）稍微修改一下就可以形成構造 Farey 序列的代碼。可以認為 Farey 序列 \(F_i\) 是 Stern–Brocot 第 \(i-1\) 次迭代後得到的序列的子序列。

Farey 序列同樣滿足最簡性和單調性，並且滿足一個與 Stern–Brocot 樹相似的性質：對於序列中連續的三個數 \(\dfrac ab,\dfrac xy,\dfrac cd\)，有 \(x=a+c,y=b+d\)。這個可以輕鬆證明，不再贅述。

由 Farey 序列的定義，可以得到 \(F_i\) 的長度 \(L_i\) 公式為：

\[ \begin{aligned} L_i=L_{i-1}+\varphi(i)\\ L_i=1+\sum_{k=1}^i\varphi(k) \end{aligned} \]

中間分數

對於 \(0\leq n\leq a_{k+1}\)，記中間分數為

\[ F_{k,n}=\frac{np_k+p_{k-1}}{nq_k+q_{k-1}} \]

中間分數還包含這樣的分數：

\[ F_{0,n}=\frac{np_0+p_{-1}}{nq_0+q_{-1}}=\frac{na_0+1}{n}=a_0+\frac{1}{n} \]

這些中間分數介於 \(\dfrac{p_{-1}}{q_{-1}}\) 與 \(\dfrac{p_0}{q_0}=a_0\) 之間。

對於給定的 \(k\)，第 \(0\) 箇中間分數 \(F_{k,0}=\dfrac{p_{k-1}}{q_{k-1}}\) 與最後一箇中間分數 \(F_{k,0}=\dfrac{p_{k-1}}{q_{k-1}}\) 是漸進分數。

對比上述表達式與

\[ x=\frac{r_{k+1}p_k+p_{k-1}}{r_{k+1}q_k+q_{k-1}} \]

可以得到 \(F_{k,n}=\left[a_0,\ldots,a_k,n\right]\)。因此，中間分數也是某個連分數展開的漸進分數，中間分數表達式的分子分母也一定互素。

兩個相鄰中間分數的差為

\[ F_{k,n+1}-F_{k,n}=\frac{(p_{k-1}q_k-p_kq_{k-1})n+(p_kq_{k-1}-p_{k-1}q_k)(n+1)}{((n+1)q_k+q_{k-1})(nq_k+q_{k-1})}=\frac{(-1)^{k-1}}{((n+1)q_k+q_{k-1})(nq_k+q_{k-1})} \]

對於確定的 \(k\)，中間分數隨着 \(n\) 的增加遞增或遞減。

定理：對實數 \(x\) 與漸進分數 \(\dfrac{p_k}{q_k}\)，有

\[ \frac{1}{q_k(q_k+q_{k+1})}<\left|x-\frac{p_k}{q_k}\right|<\frac{1}{q_kq_{k+1}} \]

證明

一種證法可以定量計算。根據連分數中的定理有

\[ \left|x-\frac{p_k}{q_k}\right|=\frac{1}{q_k(r_{k+1}q_k+q_{k-1})} \]

由於

\[ a_{k+1}<\lfloor r_{k+1}\rfloor<a_{k+1}+1 \]

因此

\[ q_{k+1}=a_{k+1}q_k+q_{k-1}<r_{k+1}q_k+q_{k-1}<a_{k+1}q_k+q_k+q_{k-1}=q_k+q_{k+1} \]

取倒數即證畢。

另一種證法使用中間分數。首先，兩個相鄰漸進分數之間的距離有

\[ \left|\frac{p_{k+1}}{q_{k+1}}-\frac{p_k}{q_k}\right|=\frac{1}{q_{k+1}q_k} \]

由於 \(x\) 本身介於兩個相鄰漸進分數之間，到其中一個漸進分數的距離 \(\left|x-\frac{p_k}{q_k}\right|\) 一定小於 \(\frac{1}{q_{k+1}q_k}\)。不等式右邊即證畢。

對於不等式左邊，由於對於固定的 \(k\)，兩頭的中間分數就是漸進分數，因此有位置關係

\[ \frac{p_{k-1}}{q_{k-1}}=F_{k,0}~F{k,1}~\frac{p_{k+1}}{q_{k+1}}~x~\frac{p_k}{q_k} \]

因此有距離關係

\[ \left|x-\frac{p_{k-1}}{q_{k-1}}\right|>|F_{k,0}-F_{k,1}|=\frac{1}{q_{k-1}(q_k+q_{k+1})} \]

更換下標，不等式左邊即證畢。

在使用中這個定理經常放縮一下。由於 \(q_k\leq q_{k+1}\)，有

\[ \frac{1}{2{q_{k+1}}^2}<\frac{1}{q_k(q_k+q_{k+1})}<\left|x-\frac{p_k}{q_k}\right|<\frac{1}{q_kq_{k+1}}<\frac{1}{{q_k}^2} \]

右半部分 \(\left|x-\frac{p_k}{q_k}\right|<\frac{1}{{q_k}^2}\) 無需計算更高階的漸進分數，很常用，即下文 Dirichlet 逼近定理的連分數證法。

Dirichlet 逼近定理

Dirichlet 逼近定理是説，對於任意的一個無理數 \(\theta\)，均能找到無窮個有理數逼近它，滿足不等式：

\(\left|\frac{p}{q}-\theta\right|\leqslant\frac{1}{q^2}\)

由於任一實數 \(qx\) 到最近的整數距離不超過 \(\dfrac{1}{2}\)，顯然存在整數 \(p\) 和 \(q\) 使得

\[ |qx-p|\leq\frac{1}{2} \]

\[ \left|x-\frac{p}{q}\right|\leq\frac{1}{2q} \]

Dirichlet 逼近定理將右側優化到了 \(\dfrac{1}{q^2}\)。等價的寫法，\(|qx-p|<\dfrac{1}{q}\) 總有解。

當 \(x\) 是無理數的時候，可以讓漸進分數的分母任意大，\(|qx-p|\) 任意小。

另外還有瓦倫定理：實數 \(x\) 連續兩個漸進分數至少有一個滿足 \(\left|x-\dfrac{p}{q}\right|<\dfrac{1}{2q^2}\)，由瓦倫（Vahlen）在 1895 年證明。

另外還有伯雷爾定理：實數 \(x\) 連續兩個漸進分數至少有一個滿足 \(\left|x-\dfrac{p}{q}\right|<\dfrac{1}{\sqrt{5}q^2}\)，由伯雷爾（Borel）在 1903 年證明。

這個 \(\sqrt{5}\) 是最優的，在無理數為例如黃金分割 \(\dfrac{1+\sqrt{5}}{2}=\left[1,1,1,\ldots\right]\) 等連分數展開自某位起均為 \(1\) 的時候取等。這些後續的定理也同樣表明，在 Dirichlet 逼近定理中的小於等於號事實上也可以是小於號。

另外還有定理：實數 \(x\) 連分數展開無窮項不小於 \(n\)，則存在無窮多漸進分數滿足 \(\left|x-\dfrac{p}{q}\right|<\dfrac{1}{\sqrt{n^2+4}q^2}\)。這種條件的極端情形例如 \(\dfrac{n+\sqrt{n^2+4}}{2}=\left[n,n,n,\ldots\right]\)。

其他的，還有 Kronecker 逼近定理：

如果 \(\theta\) 為無理數，\(\alpha\) 為實數，則對任意正數 \(\varepsilon\), 存在整數 \(n\) 和整數 \(m\)，使得：

\(\left|n\theta−m−\alpha\right|<\varepsilon\)

Dirichlet 逼近定理和 Kronecker 逼近定理，都可以用抽屜原理來解決。事實上，正是 Dirichlet 為了解決 Pell 方程，研究有理數逼近條件，抽屜原理才在歷史上被第一次正式提出。

當然，採用抽屜原理的證明可以發現，下文中提到的最佳逼近有理數列，每項滿足定理中右邊改成分母為一次式的不等式。

進一步有結論，漸進有理數列中，每一項均滿足 Dirichlet 逼近定理的不等式。

最佳有理逼近

討論如何用有理數「最佳地」逼近無理數，不妨假設無理數落入 \((0,1)\) 區間。

「最佳」一詞的概念：選定的有理數必須保證，比它與無理數的距離更近的有理數，分母都比它大。不存在分母比它小的有理數，到給定無理數的距離更近。

最佳有理數：在 Farey 數列的某一行中，與給定無理數距離最近的那個有理數。

這個有理數可能在下面幾行依舊與無理數「距離最近」，但一定有某一行，會找到一個新的有理數，與無理數距離更近。因此去重複後可以得到 最佳逼近有理數列，分母嚴格遞增，距離遞減。

更加嚴謹的敍述為：

對實數 \(x\) 和有理數 \(\dfrac{p}{q}\)，如果對於任意的整數 \(a\) 和整數 \(0<b\leq q\)，\(\dfrac{a}{b}\neq\dfrac{p}{q}\)，均有

\[ \left|x-\frac{a}{b}\right|>\left|x-\frac{p}{q}\right| \]

則稱 \(\dfrac{p}{q}\) 是 \(x\) 的一個最佳有理逼近。

比無理數大的稱為上逼近，否則為下逼近。由於無理數和有理數之間一定有有理數，最佳逼近有理數列必然為若干個上逼近，之後若干個下逼近，交替進行的形式。

有結論：

漸進分數必然為最佳有理逼近。

偶項漸進分數全都是下逼近，奇項漸進分數全都是上逼近。漸進分數列是下上交錯的逼近。

在最佳逼近有理數列中，漸進分數是下上關係改變之前的倒數第一個數。如果將最佳逼近有理數列都寫成有限簡單連分數，那麼在漸進分數之後（下上關係改變之後），連分數長度加一。

例如，\([0,2,4,2]\) 是 \(\sqrt{6}\) 減去 \(2\) 的一個漸進分數。

那麼它的漸進分數列是：

\[ [0,2]=\frac{1}{2},[0,2,4]=\frac{4}{9},[0,2,4,2]=\frac{9}{20}\ldots \]

它的最佳逼近有理數列是：

\[ \left[0,1\right]=1,\left[0,2\right]=\frac{1}{2} \]

\[ \left[0,2,1\right]=\frac{1}{3},\left[0,2,2\right]=\frac{2}{5},\left[0,2,3\right]=\frac{3}{7},\left[0,2,4\right]=\frac{4}{9} \]

\[ \left[0,2,4,1\right]=\frac{5}{11},\left[0,2,4,2\right]=\frac{9}{20},\ldots \]

從每個漸進分數（不包含）開始，到下一個漸進分數（包含）為止，同為上逼近，或同為下逼近。

在最佳逼近列中，每一個最佳分數是上一個最佳分數與再往前一個漸進分數的分子分母對應求和。

性質

定理：最佳有理逼近一定是中間分數。

它的逆定理並不成立，中間分數不一定是最佳有理逼近。

證明

首先，\(a_0\) 與 \(a_0+1\) 中必有一個是 \(x\) 的分母為 \(1\) 的最佳有理逼近。它們分別是 \(F_{1,0}\) 和 \(F_{0,1}\)。其他分母更大的第一類最優逼近肯定介於這兩個數中間。

當然，除非 \(x=n+\frac{1}{2}\) 為半奇數。這時兩邊距離一樣，\(x\) 沒有分母為 \(1\) 的最佳有理逼近，不過這屬於連分數太短的情況。

當 \(n\) 增加時，漸近分數從 \(F_{1,0}\) 和 \(F_{0,1}\) 兩邊向中間排布。由於 \(F_{k,a_{k+1}}=F_{k+2,0}\)，有分佈

\[ F_{1,0}<F_{1,1}\leq F_{1,a_2}=F_{3,0}<\ldots<x<\ldots<F_{2,0}=F_{0,a_1}≤F_{0,1} \]

因為中間分數可以任意接近 \(x\)，從而任何一個不是中間分數的有理數 \(\frac{a}{b}\)，一定介於兩個同階的漸近分數 F*{k,r} 與 F*{k,r+1} 之間。其位置分佈情況為：

\[ F_{k,r}~\frac{a}{b}~F_{k,r+1}~x \]

於是有

\[ \left|F_{k,r}-\frac{a}{b}\right|<|F_{k,r+1}-F_{k,r}|=\frac{1}{((r+1)q_k+q_{k-1})(rq_k+q_{k-1})} \]

另一方面，\(\frac{a}{b}\) 與中間分數 \(F_{k,r}\)，有

\[ \left|F_{k,r}-\frac{a}{b}\right|=\frac{|a(rq_k+q_{k-1})-b(rp_k+p_{k-1})|}{b(rq_k+q_{k-1})}\geq\frac{1}{b(rq_k+q_{k-1})} \]

因此有 \(b>(r+1)q_k+q_{k-1}\)。介於 \(F_{k,r}\) 和 \(F_{k,r+1}\) 之間的有理數，分母一定大於 \(F_{k,r+1}\) 的分母。由位置分佈可以看出

\[ \left|x-\frac{a}{b}\right|>|x-F_{k,r+1}| \]

分母更小的分數 \(F_{k,r+1}\) 到 \(x\) 的距離更近。因此，非中間分數的 \(\frac{a}{b}\) 不可能是最佳有理逼近。證畢。

漸進分數的等價性質

實數 \(x\) 的漸進分數 \(\dfrac{p}{q}\) 等價於這樣的一類分數：

對於任意的整數 \(a\) 和整數 \(0<b\leq q\)，\(\dfrac{a}{b}\neq\dfrac{p}{q}\)，均有

\[ |bx-a|>|qx-p| \]

也就是

\[ \left|x-\frac{a}{b}\right|>\frac{q}{b}\left|x-\frac{p}{q}\right| \]

根據等價性，這可以直接作為漸進分數的另一個定義方法。這個性質比最佳逼近更加嚴格，因此根據這個性質，漸進分數必然為最佳逼近。

證明：

首先有 \(|q_kx-p_k|<\dfrac{1}{q_{k+1}}\)。對於一個非漸近分數的中間分數 \(F_{k,n}=\dfrac{a}{b}\)，有位置分佈

\[ \frac{p_{k-1}}{q_{k-1}}~\frac{a}{b}~\frac{p_{k+1}}{q_{k+1}}~x~\frac{p_k}{q_k} \]

於是有

\[ \left|x-\frac{a}{b}\right|>\left|\frac{p_{k+1}}{q_{k+1}}-\frac{a}{b}\right| \]

即 \(|bx-a|\geq\dfrac{1}{q_{k+1}}\)。由於 \(b=nq_k+q_{k-1}>q_k\)，因此 \(F_{k,n}=\dfrac{a}{b}\) 劣於比它分母更小的 \(\dfrac{p_k}{q_k}\)。

接下來證明，滿足這個條件的都是漸進分數。

首先，越高階的漸近分數越靠近 \(x\)，具有嚴格單調性。如果有 \(s<k\)，就有 \(|q_sx-p_s|>|q_kx-p_k|\)。

這是因為 \(q_{k+1}\geq q_s+q_{s+1}\)，有

\[ |q_sx-p_s|>\frac{1}{q_s+q_{s+1}}\leq\frac{1}{q_{k+1}}>|q_kx-p_k| \]

整理即為上式。

接下來找出分母為 \(q_k\) 的滿足上述性質的數，並指出它是漸進分數。

在給定 \(b\) 的時候，\(\min |bx-a|\leq\dfrac{1}{2}\)，並且取到最小的 \(a\) 最多隻有兩個取值。

當 \(b\) 在範圍 \(0<b\leq q_k\) 遍歷的時候，將上述的最小值繼續比較其中的最小值，並記取到最小值中的最小值的多個 \(b\) 中，最小的 \(b\) 為 \(b_0\)，對應的 \(a\) 為 \(a_0\)。

這裏的 \(a_0\) 至多有兩個，而事實上只有一個，可以證明其唯一性。唯一性的證明補在最後。

從上述選取方式可以看出 \(\dfrac{a_0}{b_0}\) 也滿足定理的條件，因此它是一個漸進分數 \(\dfrac{p_s}{q_s}\)。

又根據嚴格單調性，在 \(s<k\) 時無法取到最小，只能有 \(s=k\)。

至此距離證畢只剩下 \(a_0\) 的唯一性。

如果給定 \(b_0\)，取到 \(|b_0x-a|\) 的 \(a\) 不唯一，而是相鄰的兩個數，只能有 \(|b_0x-a|=\dfrac{1}{2}\)。此時記較小的一個為 \(a_0\)。於是有

\[ x=\frac{2a_0+1}{2b_0} \]

如果它們不互素，記 \(d=\gcd(2a_0+1, 2b_0)\geq 3\)，則有

\[ b_1=\frac{2b_0}{d}<b_0 \]

\[ a_1=\frac{2a_0+1}{d} \]

使得 \(|b_1x-a_1|=|b_0x-a_0|=\dfrac{1}{2}\)。這與上述選取方式中 \(b_0\) 的最小性矛盾。

此時將有理數 \(x\) 做連分數展開，則最後一個漸進分數的分子分母就是

\[ p_N=2a_0+1 \]

\[ q_N=2b_0=a_Nq_{N-1}+q_{N-2} \]

由於 \(a_N\geq 2\)，\(q_{N-2}\geq 1\)，得到 \(q_{N-1}<b_0\)。於是

\[ |q_{N-1}x-p_{N-1}|=\frac{1}{q_N}=\frac{1}{2b_0}\leq\frac{1}{2} \]

此時有更小的 \(q_{N-1}\) 可以取到最小值，仍舊與上述 \(b_0\) 的選取方式矛盾。證畢。

勒讓德判別法

對實數 \(x\) 與分數 \(\dfrac{p}{q}\)，如果有

\[ \left|x−\frac{p}{q}\right|<\frac{1}{2q^2} \]

則 \(\dfrac{p}{q}\) 一定是 \(x\) 的漸近分數。

勒讓德判別法的原始形式更加複雜，由勒讓德（Legendre）於 1797 年發表在他的專著中。

勒讓德判別法的原始表述是一個等價關係，這裏給出的形式相對簡化與寬鬆，是一個漸進分數的充分條件而非必要條件。

證明

假設 \(\dfrac{p}{q}\) 不是漸進分數，則存在 \(0<b\leq q\)，且 \(\dfrac{a}{b}\neq\dfrac{p}{q}\) 使得

\[ |bx-a|\leq|qx-p|<\frac{1}{2q} \]

於是有

\[ \left|x-\frac{a}{b}\right|<\frac{1}{2qb} \]

此時首先兩個分數之間的距離有

\[ \left|\frac{p}{q}-\frac{a}{b}\right|=\frac{|pb-aq|}{qb}\geq\frac{1}{qb} \]

又有絕對值不等式

\[ \left|\frac{p}{q}-\frac{a}{b}\right|=\left|\frac{p}{q}-x+x-\frac{a}{b}\right|\leq\left|\frac{p}{q}-x\right|+\left|x-\frac{a}{b}\right|<\frac{b+q}{2bq^2} \]

連起來有

\[ \frac{1}{qb}\leq\left|\frac{p}{q}-\frac{a}{b}\right|<\frac{b+q}{2bq^2} \]

整理有 \(b>q\)。這與假設矛盾。證畢。

本頁面主要譯自博文 Дерево Штерна-Броко. Ряд Фарея 與其英文翻譯版 The Stern-Brocot Tree and Farey Sequences。其中俄文版版權協議為 Public Domain + Leave a Link；英文版版權協議為 CC-BY-SA 4.0。

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用