슈테른-브로코 트리는 음이 아닌 모든 분수의 집합을 구성할 수 있게 해 주는 우아한 구조입니다. 이 구조는 1858년 독일의 수학자 모리츠 슈테른(Moritz Stern)과 1861년 프랑스의 시계공 아실 브로코(Achille Brocot)가 각자 독립적으로 발견했습니다. 다만 일부 자료에 따르면 이 구조는 이미 고대 그리스의 학자 에라토스테네스(Eratosthenes)가 발견했다고 합니다.
0번째 반복에서는 두 개의 분수가 있습니다:
\frac{0}{1}, \frac{1}{0}
(두 번째 값은 엄밀히 말하면 분수가 아닙니다. 이것은 무한대를 나타내는 기약분수로 이해할 수 있습니다) 이후 각 반복에서는 이 분수 목록을 가져와 이웃한 두 분수 \frac{a}{b}와 \frac{c}{d} 사이마다 그 둘의 중간수(mediant), 즉 분수 \frac{a+c}{b+d}를 삽입합니다.
예를 들어, 첫 번째 반복에서 현재 집합은 다음과 같습니다:
\frac{0}{1}, \frac{1}{1}, \frac{1}{0}
두 번째 단계에서는 다음과 같습니다:
\frac{0}{1}, \frac{1}{2}, \frac{1}{1}, \frac{2}{1[…]
세 번째 단계에서는 다음과 같습니다:
\frac{0}{1}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3[…]
이 과정을 무한히 계속하면 음이 아닌 모든 분수의 집합을 얻을 수 있다고 주장할 수 있습니다. 더 나아가, 얻어지는 모든 분수는 서로 다르며(즉, 현재 집합에서 각 분수는 최대 한 번만 나타납니다), 기약분수입니다(분자와 분모가 서로소로 얻어집니다). 마지막으로, 모든 분수는 자동으로 오름차순으로 정렬됩니다. 슈테른-브로코 트리의 이 모든 놀라운 성질에 대한 증명은 바로 아래에서 제시하겠습니다.
이제 남은 것은 슈테른-브로코 트리 자체의 그림을 제시하는 것뿐입니다(지금까지는 변화하는 집합을 이용해 이 트리를 설명했습니다). 이 무한한 트리의 루트에는 분수 \frac{1}{1}이 있고, 트리의 왼쪽과 오른쪽에는 분수 \frac{0}{1}과 \frac{1}{0}이 있습니다. 트리의 모든 정점은 두 자식을 가지며, 각 자식은 자신의 왼쪽 조상과 오른쪽 조상의 중간분수(mediant)로 얻어집니다:
증명 순서성. 이는 매우 간단하게 증명됩니다. 두 분수의 중간수(mediant)는 항상 두 분수 사이에 있다는 점에 주목합시다. 즉, 다음과 같습니다:
\frac{a}{b} \le \frac{a+c}{b+d} \le \frac{c}{d}
이는 \frac{a}{b} \le \frac{c}{d}라는 조건에서 성립합니다.
이는 세 분수를 통분하기만 하면 간단히 증명됩니다. 0번째 반복에서 순서가 성립했으므로, 이후의 모든 새 반복에서도 순서가 유지됩니다.
기약성. 이를 위해, 임의의 반복 단계에서 목록에 인접한 임의의 두 분수 \frac{a}{b}와 \frac{c}{d}에 대해 다음이 성립함을 보이겠습니다:
bc-ad=1
실제로, 두 미지수에 대한 디오판토스 방정식(ax+by=c)을 떠올려 보면, 이 명제로부터 {\rm gcd}(a,b) = {\rm gcd}(c,d) = 1임을 얻으며, 이것이 바로 우리에게 필요한 것입니다. 따라서 임의의 반복에서 bc-ad=1이라는 명제가 참임을 증명해야 합니다. 이 역시 귀납법으로 증명합시다. 0번째 반복에서는 이 성질이 성립했습니다(이는 쉽게 확인할 수 있습니다). 이제 이전 반복에서 이 성질이 성립했다고 가정하고, 현재 반복에서도 성립함을 보입시다. 이를 위해 새 목록에서 이웃한 분수 세 개를 살펴보아야 합니다:
\frac{a}{b}, \frac{a+c}{b+d}, \frac{c}{d}
이 분수들에 대해 조건은 다음과 같은 형태가 됩니다: b(a+c) - a(b+d) = 1, c(b+d) - d(a+c) = 1
그러나 bc-ad=1이 참이라는 조건하에서 이 조건들이 참이라는 것은 자명합니다. 따라서 실제로 이 성질은 현재 반복에서도 성립하며, 이로써 증명이 완료됩니다. 모든 분수의 존재. 이 성질의 증명은 슈테른-브로코 트리에서 분수를 찾는 알고리즘과 밀접하게 관련되어 있습니다. 슈테른-브로코 트리에서 모든 분수가 정렬되어 있다는 점을 고려하면, 트리의 임의의 정점에 대해 그 왼쪽 서브트리에는 그 정점보다 작은 분수들이, 오른쪽 서브트리에는 그 정점보다 큰 분수들이 위치한다는 것을 알 수 있습니다. 이로부터 슈테른-브로코 트리에서 어떤 분수를 찾는 자명한 알고리즘도 얻을 수 있습니다. 처음에 우리는 루트에 있습니다. 우리의 분수를 현재 정점에 적힌 분수와 비교합니다. 우리의 분수가 더 작으면 왼쪽 서브트리로 이동하고, 우리의 분수가 더 크면 오른쪽 서브트리로 이동하며, 일치하면 분수를 찾은 것이므로 탐색이 종료됩니다.
무한 슈테른-브로코 트리가 모든 분수를 포함한다는 것을 증명하려면, 주어진 임의의 분수에 대해 이 분수 탐색 알고리즘이 유한한 단계 안에 종료된다는 것을 보이는 것으로 충분합니다. 이 알고리즘은 다음과 같이 이해할 수 있습니다. 우리에게는 현재 구간 \left[ \frac{a}{b}; \frac{c}{d} \right]가 있고, 이 구간에서 우리가 찾는 분수 \frac{x}{y}를 탐색합니다. 처음에는 \frac{a}{b}=\frac{0}{1}, \frac{c}{d}=\frac{1}{0}입니다. 각 단계에서 분수 \frac{x}{y}를 구간 양 끝의 중간수, 즉 \frac{a+c}{b+d}와 비교하고, 그 결과에 따라 탐색을 멈추거나 구간의 왼쪽 또는 오른쪽 부분으로 이동합니다. 만약 분수 탐색 알고리즘이 무한히 계속 실행된다면, 매 반복마다 다음 조건들이 성립할 것입니다.
\frac{a}{b} < \frac{x}{y} < \frac{c}{d}
그러나 이들은 다음과 같은 형태로 다시 쓸 수 있습니다: bx-ay \ge 1, cy-dx \ge 1
(여기서는 이들이 정수라는 점을 이용했으므로 >0이면 \ge 1이 성립합니다) 그러면 첫 번째 부등식에 c+d를, 두 번째 부등식에 a+b를 곱한 뒤 둘을 더하면 다음을 얻습니다:
(c+d)(bx-ay) + (a+b)(cy-dx) \ge a+b+c+d
좌변의 괄호를 전개하고 bc-ad=1임을 고려하면(이전 성질의 증명 참조), 최종적으로 다음을 얻습니다: x+y \ge a+b+c+d
그리고 각 반복마다 변수 a, b, c, d 중 적어도 하나는 순증가하므로, 분수 \frac{x}{y}를 찾는 과정은 최대 x+y번의 반복으로 이루어지며, 이로써 증명이 완료됩니다. 트리 구성 알고리즘 슈테른-브로코 트리의 임의의 부분 트리를 구성하려면 왼쪽 조상과 오른쪽 조상만 알면 충분합니다. 처음 첫 번째 레벨에서 왼쪽 조상은 \frac{0}{1}이고, 오른쪽 조상은 \frac{1}{0}입니다. 이 둘을 이용해 현재 정점의 분수를 계산한 다음, 왼쪽 자식과 오른쪽 자식에서 재귀적으로 실행할 수 있습니다(왼쪽 자식에게는 자신을 오른쪽 조상으로, 오른쪽 자식에게는 자신을 왼쪽 조상으로 전달합니다).
무한한 트리 전체를 구성하려고 시도하는 이 절차의 의사 코드는 다음과 같습니다:
void build (int a = 0, int b = 1, int c = 1, int d = 0, int level = 1) { int x = a+c, y = b+d; … 트리의 level 수준에서 현재 분수 x/y 출력 build (a, b, x, y, level + 1); build (x, y, c, d, level + 1); } 분수 탐색 알고리즘 분수 탐색 알고리즘은 슈테른-브로코 트리가 모든 분수를 포함한다는 것을 증명할 때 이미 설명하였으나, 여기서 다시 한번 설명하겠습니다. 이 알고리즘은 사실상 이진 탐색 알고리즘, 즉 이진 탐색 트리에서 주어진 값을 찾는 알고리즘입니다. 처음에 우리는 트리의 루트에 있습니다. 현재 정점에 있을 때, 우리는 찾는 분수를 현재 정점의 분수와 비교합니다. 두 분수가 일치하면 과정을 멈춥니다. 트리에서 분수를 찾은 것입니다. 그렇지 않은 경우, 찾는 분수가 현재 정점의 분수보다 작으면 왼쪽 자식으로 이동하고, 그렇지 않으면 오른쪽 자식으로 이동합니다.
슈테른-브로코 트리가 모든 음이 아닌 분수를 포함한다는 성질에서 증명했듯이, 분수 \frac{x}{y}를 찾을 때 알고리즘은 최대 x+y번 반복합니다.
주어진 분수 \frac{x}{y}를 포함하는 정점까지의 경로를 ‘L’/‘R’ 문자의 나열 형태로 반환하는 구현을 제시합니다. 현재 문자가 ‘L’이면 트리에서 왼쪽 자식으로 이동한다는 뜻이고, 그렇지 않으면 오른쪽 자식으로 이동한다는 뜻입니다(처음에는 트리의 루트, 즉 분수 \frac{1}{1}을 가진 정점에 있습니다). 사실 모든 음이 아닌 분수에 대해 존재하며 그 분수를 유일하게 결정하는 이러한 문자의 나열을 슈테른-브로코 기수법이라고 합니다.
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); } 슈테른-브로코 기수법에서 무리수에는 무한한 문자 시퀀스가 대응합니다. 미리 정해진 정밀도가 주어져 있다면, 이 무한 시퀀스의 어떤 접두사만으로 충분합니다. 슈테른-브로코 트리에서 무리수를 찾는 이 무한한 탐색 과정에서 알고리즘은 매번 (분모가 점차 커지는) 기약분수를 찾게 되며, 이 분수는 해당 무리수에 대한 최선의 근사를 제공합니다(바로 이 응용이 시계 제작 기술에서 중요하며, 아실 브로코가 이 트리를 발견한 것도 이와 관련이 있습니다).
페리 수열 차수 n의 페리 수열이란 0과 1 사이에 있으며 분모가 n을 넘지 않는 모든 기약 분수의 집합을 말하며, 이때 분수들은 오름차순으로 정렬되어 있습니다.
이 수열은 영국의 지질학자 존 페리(John Farey)의 이름을 따서 붙여졌으며, 그는 1816년에 페리 수열에서 모든 분수가 이웃한 두 분수의 중간수(mediant)임을 증명하려고 시도했습니다. 알려진 바에 따르면 그의 증명은 잘못되었으며, 올바른 증명은 조금 뒤에 코시(Cauchy)가 제시했습니다. 하지만 이미 1802년에 수학자 아로(Haros)가 자신의 한 논문에서 사실상 같은 결과에 도달했습니다.
페리 수열은 그 자체로도 흥미로운 성질을 많이 가지고 있지만, 가장 두드러지는 것은 슈테른-브로코 트리와의 관계입니다. 실제로 페리 수열은 트리에서 일부 가지를 제거하여 얻어집니다. 또는 페리 수열을 얻으려면 슈테른-브로코 트리를 무한 번 반복하여 구성할 때 얻어지는 분수의 집합을 취한 뒤, 이 집합에서 분모가 n을 넘지 않고 분자가 분모를 넘지 않는 분수만 남기면 된다고 말할 수도 있습니다.
슈테른-브로코 트리를 구성하는 알고리즘으로부터 페리 수열에 대한 비슷한 알고리즘도 얻을 수 있습니다. 0번째 반복에서는 집합에 분수 \frac{0}{1}과 \frac{1}{1}만 포함합니다. 그 이후의 각 반복에서는 이웃한 두 분수 사이마다 그 중간분수(mediant)를 삽입하되, 그 분모가 n을 넘지 않는 경우에만 삽입합니다. 언젠가는 집합에 더 이상 아무런 변화도 일어나지 않게 되며, 그때 과정을 멈추면 됩니다. 이로써 우리가 찾던 페리 수열을 얻었습니다.
페리 수열의 길이를 계산해 봅시다. n차 페리 수열은 n-1차 페리 수열의 모든 원소와 함께 분모가 n인 모든 기약 분수를 포함하는데, 잘 알려져 있듯이 그 개수는 \phi(n)입니다. 따라서 n차 페리 수열의 길이 L_n은 다음 공식으로 나타낼 수 있습니다:
L_n = L_{n-1} + \phi(n)
또는 재귀를 풀어 쓰면 다음과 같습니다: L_n = 1 + \sum_{k=1}^n \phi(k)