Stern-Brocot 트리와 Farey 수열¶
Stern-Brocot 트리¶
Stern-Brocot 트리는 모든 양의 분수의 집합을 표현하는 우아한 구성입니다. 이 트리는 1858년 독일의 수학자 Moritz Stern과 1861년 프랑스의 시계 제작자 Achille Brocot이 각각 독립적으로 발견했습니다. 그러나 일부 문헌에서는 이 발견을 고대 그리스 수학자 에라토스테네스의 업적으로 봅니다.
구성은 0번째 반복에서 다음 두 분수로 시작합니다.
여기서 두 번째 값은 엄밀히 말해 분수가 아니지만, 무한대를 나타내는 기약분수로 해석할 수 있다는 점에 유의해야 합니다.
이후의 모든 반복에서는 인접한 모든 분수 $\frac{a}{b}$와 $\frac{c}{d}$를 살펴보고, 그 사이에 두 분수의 중간수 $\frac{a+c}{b+d}$를 삽입합니다.
처음 몇 번의 반복은 다음과 같습니다.
이 과정을 무한대까지 계속하면 모든 양의 분수를 얻습니다. 또한 모든 분수는 유일하며 기약분수입니다. 마지막으로, 분수들은 오름차순으로 나타납니다.
이러한 성질을 증명하기 전에, 목록 형태 대신 Stern-Brocot 트리를 실제로 시각화하여 보여 드리겠습니다. 트리의 모든 분수는 두 개의 자식을 가집니다. 각 자식은 왼쪽에서 가장 가까운 조상과 오른쪽에서 가장 가까운 조상의 중간수입니다.
증명¶
순서. 순서를 증명하는 것은 간단합니다. 두 분수의 중간수는 항상 두 분수 사이에 있다는 점에 주목합니다.
단, 다음이 성립한다고 가정합니다.
두 부등식은 분수들을 공통 분모로 다시 써 보면 쉽게 보일 수 있습니다.
0번째 반복에서 순서가 오름차순이므로, 이후의 모든 반복에서도 이 순서가 유지됩니다.
기약성. 이를 증명하기 위해, 인접한 임의의 두 분수 $\frac{a}{b}$와 $\frac{c}{d}$에 대해 다음이 성립함을 보이겠습니다.
두 변수에 대한 디오판토스 방정식 $ax+by=c$는 $c$가 $\gcd(a,b)$의 배수일 때, 그리고 그때에만 해를 가진다는 사실을 떠올려 보십시오. 우리의 경우 이는 $\gcd(a,b) = \gcd(c,d) = 1$임을 의미하며, 이것이 바로 우리가 보이고자 하는 것입니다.
0번째 반복에서 $bc - ad = 1$임은 자명합니다. 남은 것은 중간수가 이 성질을 유지한다는 것을 보이는 것입니다.
인접한 두 분수가 $bc - ad = 1$을 만족한다고 가정합시다. 중간수를 목록에 추가하면 다음과 같이 됩니다.
새로운 식은 다음과 같습니다.
이는 $bc-ad=1$임을 이용하면 쉽게 참임을 보일 수 있습니다.
이로부터 이 성질이 항상 유지됨을 알 수 있으며, 따라서 모든 분수는 기약분수입니다.
모든 분수의 존재성. 이 증명은 Stern-Brocot 트리에서 분수의 위치를 찾는 과정과 밀접하게 관련되어 있습니다. 순서 성질에 의해 어떤 분수의 왼쪽 서브트리에는 부모 분수보다 작은 분수만 있고, 오른쪽 서브트리에는 부모 분수보다 큰 분수만 있습니다. 따라서 루트에서부터 트리를 순회하면서 목표가 현재 분수보다 작으면 왼쪽으로, 크면 오른쪽으로 이동하는 방식으로 분수를 탐색할 수 있습니다.
임의의 양의 목표 분수 $\frac{x}{y}$를 고릅시다. 이 분수는 당연히 $\frac{0}{1}$과 $\frac{1}{0}$ 사이에 있으므로, 이 분수가 트리에 없는 유일한 경우는 그 분수에 도달하는 데 무한히 많은 단계가 필요한 경우입니다.
그렇다면 모든 반복에서 다음이 성립합니다.
이는 (정수에 대해 $z \gt 0 \iff z \ge 1$이라는 사실을 이용하면) 다음과 같이 다시 쓸 수 있습니다.
이제 첫 번째 부등식에 $c+d$를, 두 번째 부등식에 $a+b$를 곱한 뒤 두 식을 더하면 다음을 얻습니다.
이를 전개하고 앞에서 보인 성질 $bc-ad=1$을 이용하면 다음을 얻습니다.
그리고 매 반복마다 $a,b,c,d$ 중 적어도 하나는 증가하므로, 분수 탐색 과정은 최대 $x+y$번의 반복만 거칩니다. 이는 $\frac{x}{y}$까지의 경로가 무한하다는 가정에 모순되므로, $\frac{x}{y}$는 반드시 트리에 포함되어야 합니다.
트리 구축 알고리즘¶
Stern-Brocot 트리의 임의의 서브트리를 구축하려면 왼쪽 조상과 오른쪽 조상만 알면 충분합니다. 첫 번째 레벨에서 왼쪽 조상과 오른쪽 조상은 각각 $\frac{0}{1}$과 $\frac{1}{0}$입니다. 이들을 이용해 중간수(mediant)를 계산하고 한 레벨 더 깊이 내려가는데, 왼쪽 서브트리에서는 중간수가 오른쪽 조상을 대체하고, 오른쪽 서브트리에서는 그 반대입니다.
다음 의사 코드는 무한한 트리 전체를 구축하려고 시도합니다.
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);
}
분수 탐색 알고리즘¶
탐색 알고리즘은 모든 분수가 트리에 나타난다는 증명에서 이미 설명했지만, 여기서 다시 설명하겠습니다. 이 알고리즘은 이진 탐색 알고리즘입니다. 처음에는 트리의 루트에서 시작하여 목표를 현재 분수와 비교합니다. 두 값이 같으면 탐색을 마치고 과정을 멈춥니다. 목표가 더 작으면 왼쪽 자식으로 이동하고, 그렇지 않으면 오른쪽 자식으로 이동합니다.
단순 탐색¶
다음은 주어진 분수 $\frac{p}{q}$까지의 경로를 'L'과 'R' 문자의 수열로 반환하는 구현이며, 두 문자는 각각 왼쪽 자식과 오른쪽 자식으로의 이동을 의미합니다. 이 문자 수열은 모든 양의 분수를 유일하게 정의하며, Stern-Brocot 기수법이라고 부릅니다.
string find(int p, int q) {
int pL = 0, qL = 1;
int pR = 1, qR = 0;
int pM = 1, qM = 1;
string res;
while(pM != p || qM != q) {
if(p * qM < pM * q) {
res += 'L';
tie(pR, qR) = {pM, qM};
} else {
res += 'R';
tie(pL, qL) = {pM, qM};
}
tie(pM, qM) = pair{pL + pR, qL + qR};
}
return res;
}
Stern-Brocot 기수법에서 무리수는 무한한 문자 수열에 대응합니다. 무리수를 향한 끝없는 경로를 따라가면서 알고리즘은 분모가 점점 커지는 기약분수들을 찾게 되며, 이들은 무리수에 대해 점점 더 나은 근삿값을 제공합니다. 따라서 무한 수열의 접두사를 취하면 원하는 정밀도의 근삿값을 얻을 수 있습니다. 이 응용은 시계 제작에서 중요하며, 이 트리가 그 분야에서 발견된 이유도 여기에 있습니다.
분수 $\frac{p}{q}$에 대해 결과 수열의 길이는 최대 $O(p+q)$까지 커질 수 있다는 점에 유의하십시오. 예를 들어 분수가 $\frac{p}{1}$ 꼴인 경우가 그렇습니다. 즉, 위 알고리즘은 이 복잡도가 허용되는 경우가 아니라면 사용해서는 안 됩니다!
로그 시간 탐색¶
다행히 위 알고리즘을 개선하여 $O(\log (p+q))$ 복잡도를 보장할 수 있습니다. 이를 위해 현재 경계 분수가 $\frac{p_L}{q_L}$과 $\frac{p_R}{q_R}$일 때, 오른쪽으로 $a$번 이동하면 분수 $\frac{p_L + a p_R}{q_L + a q_R}$로 가고, 왼쪽으로 $a$번 이동하면 분수 $\frac{a p_L + p_R}{a q_L + q_R}$로 간다는 점에 주목해야 합니다.
따라서 L 또는 R 이동을 하나씩 수행하는 대신, 같은 방향으로 $k$번의 이동을 한꺼번에 수행한 뒤 다른 방향으로 전환하는 식으로 진행할 수 있습니다. 이렇게 하면 분수 $\frac{p}{q}$까지의 경로를 런 렝스 인코딩(run-length encoding) 형태로 구할 수 있습니다.
이와 같이 방향이 번갈아 바뀌므로, 어느 방향으로 가야 하는지 항상 알 수 있습니다. 그러므로 편의상 분수 $\frac{p}{q}$까지의 경로를 다음과 같은 분수의 수열로 나타낼 수 있습니다.
여기서 $\frac{p_{k-1}}{q_{k-1}}$과 $\frac{p_k}{q_k}$는 $k$번째 단계에서 탐색 구간의 경계이며, $\frac{p_0}{q_0} = \frac{0}{1}$과 $\frac{p_1}{q_1} = \frac{1}{0}$에서 시작합니다. 그러면 $k$번째 단계 이후에는 다음 분수로 이동합니다.
여기서 $a_k$는 양의 정수입니다. 연분수에 익숙하다면, 수열 $\frac{p_i}{q_i}$가 $\frac{p}{q}$의 근사분수(convergent)의 수열이고 수열 $[a_1; a_2, \dots, a_{n}, 1]$이 $\frac{p}{q}$의 연분수를 나타낸다는 것을 알아차릴 수 있을 것입니다.
이를 통해 분수 $\frac{p}{q}$의 연분수 표현을 계산하는 알고리즘을 따르는 방식으로 $\frac{p}{q}$까지의 경로의 런 렝스 인코딩을 구할 수 있습니다:
auto find(int p, int q) {
bool right = true;
vector<pair<int, char>> res;
while(q) {
res.emplace_back(p / q, right ? 'R' : 'L');
tie(p, q) = pair{q, p % q};
right ^= 1;
}
res.back().first--;
return res;
}
그러나 이 접근법은 $\frac{p}{q}$를 이미 알고 있고 Stern-Brocot 트리에서 그 위치를 찾으려는 경우에만 그대로 적용됩니다.
실제로는 $\frac{p}{q}$를 미리 알 수 없지만, 특정한 $\frac{x}{y}$에 대해 $\frac{x}{y} < \frac{p}{q}$인지 확인할 수 있는 경우가 많습니다.
이를 알면 현재 경계 $\frac{p_{k-1}}{q_{k-1}}$과 $\frac{p_k}{q_k}$를 유지하고 각 $a_k$를 이진 탐색으로 찾음으로써 Stern-Brocot 트리에서의 탐색을 모방할 수 있습니다. 이 경우 알고리즘은 조금 더 까다롭지만, 여전히 $O(\log (p+q))$ 복잡도가 보장됩니다. 최악의 경우 항의 개수만 해도 이미 $\Theta(\log (p+q))$이므로, 일반적으로 이보다 개선할 수는 없습니다.
이 상한을 얻으려면 각 $a_k$를 찾을 때 먼저 후보 값을 목표를 넘어설 때까지 두 배씩 늘리고, 그다음에야 마지막 구간 안에서 이진 탐색을 수행해야 합니다. 이 과정에는 $O(\log a_k)$번의 비교가 필요합니다. 대신 각 $a_k$를 고정된 범위에서 이진 탐색하면 항마다 $O(\log (p+q))$가 들어, 전체적으로 더 약한 $O(\log^2 (p+q))$ 상한이 됩니다.
그러면 전체 비용은 $O\left(\sum_k \left(1 + \log a_k\right)\right)$이며, 두 부분 모두 $O(\log (p+q))$입니다. $p_k$와 $q_k$는 적어도 피보나치 수만큼 빠르게 증가하므로 항의 개수는 $O(\log (p+q))$이며, 이 피보나치 수의 증가가 가장 느린 경우로서 모든 $a_k$가 $1$일 때 나타납니다. 그리고 위의 두 점화식을 더하면 $p_{k+1} + q_{k+1} = (p_{k-1} + q_{k-1}) + a_k (p_k + q_k) \geq a_k (p_k + q_k)$를 얻으므로 $p + q \geq \prod_k a_k$이고, 따라서 $\sum_k \log a_k \leq \log (p+q)$입니다.
Farey 수열¶
$n$차 Farey 수열은 $0$과 $1$ 사이에 있으면서 분모가 $n$을 넘지 않는 분수들을 정렬한 수열입니다.
이 수열의 이름은 영국의 지질학자 John Farey에서 유래했으며, 그는 1816년에 Farey 수열의 모든 분수가 이웃한 두 분수의 중간수(mediant)라고 추측했습니다. 이는 얼마 후 Cauchy가 증명했지만, 이 두 사람과는 독립적으로 수학자 Haros가 1802년에 이미 거의 같은 결론에 도달했습니다.
Farey 수열은 그 자체로도 흥미로운 성질을 많이 가지고 있지만, Stern-Brocot 트리와의 연관성이 가장 두드러집니다. 실제로 Farey 수열은 트리에서 가지를 잘라 내어 얻을 수 있습니다.
Stern-Brocot 트리를 구성하는 알고리즘으로부터 Farey 수열을 구하는 알고리즘을 얻을 수 있습니다. 분수 목록 $\frac{0}{1}, \frac{1}{0}$에서 시작합니다. 이후 매 반복마다 분모가 $n$을 넘지 않는 경우에만 중간수를 삽입합니다. 어느 시점이 되면 목록이 더 이상 바뀌지 않으며, 그때 원하는 Farey 수열을 얻게 됩니다.
패리 수열의 길이¶
차수 $n$인 패리 수열은 차수 $n-1$인 패리 수열의 모든 원소와 분모가 $n$인 모든 기약분수를 포함하는데, 후자의 개수는 바로 오일러 피 함수 값 $\varphi(n)$입니다. 따라서 차수 $n$인 패리 수열의 길이 $L_n$은 다음과 같습니다.
또는 이와 동치로, 재귀를 풀어 쓰면 다음을 얻습니다.