스턴브로코트나무

i = 1, 2, 3, 4에 대한 순서 i의 스턴-브로코트 나무와 스턴-브로코트 시퀀스.

수론에서, 스턴-브로코트 트리는 정점이 양의 유리수에 1 대 1로 대응하고, 탐색 트리에서와 같이 값이 왼쪽에서 오른쪽으로 정렬되는 무한 완전 이진수이다.

Stern-Brocot 나무는 Moritz Stern(1858)과 Achille Brocot(1861)에 의해 독립적으로 도입되었다.스턴은 독일의 숫자 이론가였고, 브로코는 스턴-브로코 트리를 사용하여 기어비가 원하는 값에 가까운 기어 시스템을 설계한 프랑스의 시계 제조사였습니다.

Stern-Brocot 나무의 뿌리는 숫자 1에 해당합니다.Stern-Brocot 트리의 숫자 사이의 부모-자녀 관계는 연속 분수 또는 매개자의 관점에서 정의될 수 있으며, 루트로부터 다른 숫자 q까지의 경로는 q보다 작은 분모로 q에 대한 일련의 근사치를 제공한다. 트리가 각 양의 유리수를 정확히 한 번, 너비 먼저 포함하기 때문이다.트리의 검색은 Farey 시퀀스와 밀접하게 관련된 모든 양의 합리성을 나열하는 방법을 제공합니다.범위의 유리수(0,1)를 포함하는 스턴-브로코트 트리의 왼쪽 하위 트리를 파레이 트리라고 한다.

연속 분수 나무

모든 양의 유리수 q는 형식의 연속분수로 표현될 수 있다.

{\displaystyle q={0}+{\displayac {1}{a_{2}+{\displayac {1}+{\dots +{\displayac {1}{\dots +{\displayac {1}}}}=[a_0}_{1}+{1}}}}}}}}{\displaystac {\capac {{a_{a}}}}}}}}}}}}}}}}}}}}.

여기서 k와₀ a는 음이 아닌 정수이고, 각 후속 계수_i a는 양의 정수입니다.이 표현은 고유하지 않습니다. 왜냐하면,

({displaystyle [a_{0};a_{1},a_{2},\ldots,a_{k-1},1]=[a_{0};a_{1},\ldots,a_{k-1}+1)

계수의₀ 모든 시퀀스 a, ..., a_k−1. 전자의 형태에 대한 표현을 후자의 형태로 다시 쓰기 위해 이 동일성을 사용하여 최종 계수가 (k = 0, 이 경우 1 1을 구하지₀ 않는 한) ( 2를_k 만족한다는 것을 얻을 수 있다. 이 추가 요건으로 표현은 고유해진다.q = 1이 아닌 한, 숫자 q는 연속 분수식으로 주어진 Stern-Brocot 트리에서 모수를 갖는다.

({displaystyle [a_{0};a_{1},a_{2},\ldots,a_{k}-1],}

a = 2인 경우_k [ $[a_{0};a_{1},a_{2},\ldots ,a_{k-1}+1]$ 0 $[a_{0};a_{1},a_{2},\ldots ,a_{k-1}+1]$ $[a_{0};a_{1},a_{2},\ldots ,a_{k-1}+1]$ 1, $[a_{0};a_{1},a_{2},\ldots ,a_{k-1}+1]$ , $[a_{0};a_{1},a_{2},\ldots ,a_{k-1}+1]$ … $[a_{0};a_{1},a_{2},\ldots ,a_{k-1}+1]$ , $[a_{0};a_{1},a_{2},\ldots ,a_{k-1}+1]$ - $[a_{0};a_{1},a_{2},\ldots ,a_{k-1}+1]$ + $[a_{0};a_{1},a_{2},\ldots ,a_{k-1}+1]$ ]({ $displaystyle [a_{0};a_{1},a_{2},\ldots,a_{k-1}+1$ )로 $[a_{0};a_{1},a_{2},\ldots ,a_{k-1}+1]$ 다시 쓸 수 있습니다 $[a_{0};a_{1},a_{2},\ldots ,a_{k-1}+1]$ 예를 들어, 유리수는23/16은 연속 분수 표현이다.

{23}{16}=1+{\displayac {1}{2+{\displayac {1}{2}}}}=[1;2,3,2}

그래서 스턴-브로코트 나무에서 그것의 부모가 숫자이다.

[1;2,3,1]=[1;2,4]=1+{\displayac {1}{2+{\frac {1}{4}}=displayfrac {13}{9}.

$이$ 모수는 연속된 분수의 가장 안쪽 항에 있는 분모를 1만큼 줄이고, ${\tfrac {1}{1}}$ 가 $1$ 이 되면 이전 항과 $수축$ 하여 형성됩니다 ${\tfrac {1}{1}}$

반대로 Stern-Brocot 트리의 각 숫자 q에는 정확히 두 개의 자녀가 있다.

\displaystyle = [a_{0}; a_{1}, a_{2},\ldots,a_{k}=[a_{0};a_{1},a_{2},\ldots,a_{k}-1,1]}

그러면 한 아이는 연속된 분수로 표현되는 숫자이다.

\displaystyle \displaystyle [a_{0};a_{1},a_{2},\ldots,a_{k}+1]}

반면 다른 아이는 연속된 분수로 표현된다.

(\displaystyle [a_{0};a_{1},a_{2},\ldots,a_{k}-1,2)}

이들 자녀 중 하나는 q 미만이고 이것은 왼쪽 자녀입니다.다른 하나는 q보다 크고 오른쪽 자녀입니다(실제로 전자의 표현은 k가 홀수일 경우 왼쪽 자녀, k가 짝수일 경우 오른쪽 자녀입니다).예를 들어, 13⁄9의 연속 분수 표현은 [1;2,4]이고 두 자녀는 [1;2,5] = 16⁄11(오른쪽 자녀) 및 [1;2,3,2] = 23⁄16(왼쪽 자녀)이다.

각각의 유한 연속 분수 표현에 대해, 사람은 반복적으로 부모로 이동할 수 있고, 최종적인 많은 단계에서 나무의 뿌리 [1;]=1µ1에 도달할 수 있다(a₀ + ...). + a_k - 정확히는 1단계).따라서 모든 양의 유리수는 이 트리에 정확히 한 번 표시됩니다.또한 임의의 숫자의 왼쪽 자식의 모든 후손이 q 미만이고, 오른쪽 자식의 모든 후손이 q 이상이다.트리의 깊이 d에 있는 숫자는 연속 분수 계수의 합계가 d + 1인 숫자입니다.

중개자 및 이진 검색

Stern-Brocot ^[1]^[2]나무는 유리수의 일반적인 순서와 관련하여 무한 이항 탐색 트리를 형성한다.노드 q에서 내려오는 유리수 집합은 열린 간격(L_q,H)에_q 의해 정의됩니다. 여기서_q L은 q보다 작고 트리에서 가장 가까운 q의 조상(또는_q q가 더 작은 조상 없으면 L = 0)인 반면_q H는 q보다 크고 트리에서 가장 가까운 q의 조상(또는_q H = +12)입니다.

Stern-Brocot 트리의 루트 1에서 숫자 q까지의 경로는 이진 검색 알고리즘에 의해 찾을 수 있으며, 이는 매개체를 사용하여 간단한 방법으로 표현될 수 있습니다.정의상 다른 모든 유리수보다 큰 1/0(+θ를 나타냄) 값을 포함하도록 음수가 아닌 유리수를 증가시킵니다.바이너리 검색 알고리즘은 다음과 같이 진행됩니다.

2개의 값 L과 H를 각각 0/1과 1/0으로 초기화한다.
q 가 검출될 때까지, 다음의 순서를 반복합니다.
- L = a/b 및 H = c/d로 하고, 중위수 M = (a + c)/(b + d)를 계산합니다.
- M이 q보다 작을 경우 q는 오픈 간격(M,H)입니다.L을 M으로 대체하고 속행합니다.
- M이 q보다 클 경우 q는 오픈인터벌(L,M)입니다H를 M으로 대체하고 속행합니다.
- 나머지 경우 q = M, 검색 알고리즘을 종료합니다.

이 검색에 의해 계산된 값 M의 시퀀스는 정확히 Stern-Brocot 트리의 루트에서 q까지의 경로에 있는 값의 시퀀스이다.검색의 어느 단계에서 발생하는 각 열린 간격(L,H)은 중간체 M의 자손을 나타내는 간격(L_M,H_M)이다.Stern-Brocot 나무에서 q의 모체는 q와 같지 않은 것으로 발견된 마지막 중간물질이다.

이 이진 검색 절차를 사용하여 부동 소수점 숫자를 유리수로 변환할 수 있습니다.원하는 정밀도에 도달하면 정지함으로써 부동소수점수를 임의의 ^[3]정밀도로 근사할 수 있다.만약 실수 x가 위의 알고리즘에 의해 발견된 매개체의 배열에 속하지 않는 유리수 a/b에 의해 근사된다면, 매개체의 배열은 최대 b와 같은 분모를 갖는 x에 더 가까운 근사치를 포함한다.이러한 점에서 이들 매개체는 x에 대한 최선의 유리 근사치를 형성한다.

Stern-Brocot 나무는 그 자체로 매개체로 직접 정의될 수 있다. 임의의 숫자의 q의 왼쪽 아이는 가장 작은 조상을 가진 q의 매개체이고, q의 오른쪽 아이는 가장 큰 조상을 가진 q의 오른쪽 아이는 가장 가까운 큰 조상을 가진 q의 매개체이다.이 공식에서 q와 그 조상은 둘 다 가장 낮은 단위로 구해야 하며, 더 작거나 더 큰 조상이 없으면 각각 0/1 또는 1/0을 사용해야 합니다.7/5를 예로 들면, 가장 가까운 작은 조상은 4/3이므로 왼쪽 조상은 (4+7)/(3+5) = 11/8이고, 가장 가까운 큰 조상은 3/2이므로 오른쪽 조상은 (7+3)/(5+2) = 10/7이다.

Farey 시퀀스와의 관계

순서 n의 Farey 수열은 닫힌 구간 [0,1]에서 분모가 n보다 작거나 같은 분수의 정렬된 수열이다.Stern-Brocot 트리를 생성하기 위한 이진 검색 기법과 같이, Farey 시퀀스는 매개체를 사용하여 구성할 수 있다. 순서 n + 1의 Farey 시퀀스는 순서 n의 Farey 시퀀스에서 각각 두 개의 연속된 값의 매개체를 계산하여 구성되며, 분모가 있는 매개체의 서브셋을 유지한다.n + 1과 정확히 같으며, 이들 매개체를 계산한 두 값 사이에 배치합니다.

다른 간격 끝점 쌍[0/1,1/0]에서 시작하는 유사한 중간 삽입 과정도 Stern-Brocot 나무의 각 수준에서 정점의 구성을 설명하는 것을 볼 수 있다.순서 0의 스턴-브로코트는 순서 [0/1,1/0]이고, 순서 i의 스턴-브로코트는 순서 i - 1의 스턴-브로코트의 연속된 값 쌍 사이에 중간체를 삽입하여 형성된 순서이다.순서 i의 Stern-Brocot 순서는 숫자 순서대로 경계 값 0/1 및 1/0과 함께 Stern-Brocot 나무의 첫 번째 i 수준의 모든 값으로 구성된다.

따라서 Stern-Brocot 시퀀스는 Farey 시퀀스와 두 가지 면에서 다르다. 즉, 최종적으로 구간 [0,1] 내의 유리뿐만 아니라 모든 양의 유리도 포함되며, n번째 단계에서는 분모가 n인 것뿐만 아니라 모든 매개자도 포함된다.순서 n의 Farey 시퀀스는 분모가 n보다 큰 숫자에 도달할 때마다 역추적하는 Stern-Brocot 트리의 왼쪽 하위 트리를 순서대로 트래버스로 찾을 수 있습니다.

기타 속성

${{\frac {p_{1}}{q_{1}}},{\frac {p_{2}}{q_{2}}},\dots ,{\frac {p_{n}}{q_{n}}}}$ ${{\frac {p_{1}}{q_{1}}},{\frac {p_{2}}{q_{2}}},\dots ,{\frac {p_{n}}{q_{n}}}}$ 1, ${{\frac {p_{1}}{q_{1}}},{\frac {p_{2}}{q_{2}}},\dots ,{\frac {p_{n}}{q_{n}}}}$ ${{\frac {p_{1}}{q_{1}}},{\frac {p_{2}}{q_{2}}},\dots ,{\frac {p_{n}}{q_{n}}}}$ 2, ${{\frac {p_{1}}{q_{1}}},{\frac {p_{2}}{q_{2}}},\dots ,{\frac {p_{n}}{q_{n}}}}$ ${{\frac {p_{1}}{q_{1}}},{\frac {p_{2}}{q_{2}}},\dots ,{\frac {p_{n}}{q_{n}}}}$ ${{\frac {p_{1}}{q_{1}}},{\frac {p_{2}}{q_{2}}},\dots ,{\frac {p_{n}}{q_{n}}}}$ ${{\frac {p_{1}}{q_{1}}},{\frac {p_{2}}{q_{2}}},\dots ,{\frac {p_{n}}{q_{n}}}}$ n {{\ $displaystyle {\frac {p_{1}}$ { $q_{1}},$ {\ $frac {p_{2}},$ \ $dots,$ {\ $frac {p_{n}}$ { $q_{n}}}}}},$ \dots, {\frac {\frac {pac {p_{p_{p_{n}}}}}}}, {q_{q_{q_{n}}}}}}}}}}}}}}}}}}이 ${{\frac {p_{1}}{q_{1}}},{\frac {p_{2}}{q_{2}}},\dots ,{\frac {p_{n}}{q_{n}}}}$ 모두

\sum _{k=1}^{n}{\frac {1}{p_{k}q_{k}}}=1

∑

\sum _{k=1}^{n}{\frac {1}{p_{k}q_{k}}}=1

=

\sum _{k=1}^{n}{\frac {1}{p_{k}q_{k}}}=1

\sum _{k=1}^{n}{\frac {1}{p_{k}q_{k}}}=1

1

\sum _{k=1}^{n}{\frac {1}{p_{k}q_{k}}}=1

\sum _{k=1}^{n}{\frac {1}{p_{k}q_{k}}}=1

k

=

1 { \

displaystyle \sum

_ { k

\sum _{k=1}^{n}{\frac {1}{p_{k}q_{k}}}=1

=

\sum _{k=1}^{n}{\frac {1}{p_{k}q_{k}}}=1

1

}^{n}{\frac

{

1}{p_{k}q_

{k

}} =

1

\sum _{k=1}^{n}{\frac {1}{p_{k}q_{k}}}=1

。

${{\frac {p}{q}}<{\frac {p'}{q'}}}$ p ${{\frac {p}{q}}<{\frac {p'}{q'}}}$ q < $qq {\$ { { \ $frac$ { p } { $q$ } } < \ $frac$ { ${{\frac {p}{q}}<{\frac {p'}{q'}}}$ p ' } { q ' ${{\frac {p}{q}}<{\frac {p'}{q'}}}$ }}}}} 이 ${{\frac {p}{q}}<{\frac {p'}{q'}}}$ 트리의 특정 수준 이상의 연속된 2개의 ${{\frac {p}{q}}<{\frac {p'}{q'}}}$ 일 경우(이들 사이의 모든 분수는 트리의 하위 수준이어야 함),

p'q-pq'=1

p'q-pq'=1

-

p'q-pq'=1

q

p'q-pq'=1

p'q-pq'=1

( \

displaystyle

p'q - pq '

=

^[4]1)

위에서 설명한 연속 분수와 매개물 측면에서 정의와 함께, 스턴-브로코트 트리는 분모에 의해 우선 순위를 매긴 유리 숫자에 대한 데카르트 트리로 정의될 수도 있다.즉, 정점 q의 부모가 q보다 작은 분모를 갖는 유리수의 고유한 이진수 검색 트리입니다(또는 q와 그 부모가 모두 q보다 작은 정수인 경우).스턴-브로코트 나무에서 두 숫자 q와 r 중 가장 낮은 공통 조상은 이 간격의 모든 수 중에서 가장 작은 분모를 가진 닫힌 간격의 유리수 [q, r]이다.

Stern-Brocot 나무의 각 레벨의 정점을 비트 역순열로 허용하면 다른 나무인 Calkin-Wilf 나무가 생성된다. 여기서 각 번호 a/(a + b)와 (a + b)/b는 두 개의 숫자 a/(a + b)이다.Stern-Brocot 나무와 마찬가지로, Calkin-Wilf 나무는 각각의 양의 유리수를 정확히 한 번 포함하지만, 이진수 탐색 나무는 아니다.

「」를 참조해 주세요.

민코프스키의 물음표 함수는 합리적인 논거에 대한 정의가 스턴-브로코트 나무와 밀접하게 관련되어 있다.
칼킨윌프나무

메모들

^ Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1994), Concrete mathematics (Second ed.), Addison-Wesley, pp. 116–118, ISBN 0-201-55802-5
^ 를 클릭합니다Gibbons, Jeremy; Lester, David; Bird, Richard (2006), "Functional pearl: Enumerating the rationals", Journal of Functional Programming, 16 (3): 281–291, doi:10.1017/S0956796806005880.
^ Sedgewick과 Wayne, Java 프로그래밍 입문이 알고리즘의 Java 실장은 여기서 확인할 수 있습니다.
^ 보고몰리는 이 재산을 캐나다의 음악 이론가인 피에르 라모테의 공으로 돌린다.

레퍼런스

를 클릭합니다Brocot, Achille (1861), "Calcul des rouages par approximation, nouvelle méthode", Revue Chronométrique, 3: 186–194.
Brocot, Achille(표준), "Calcul des roughes par approximation, nouvelle methode", https://gallica.bnf.fr/ark:/12148/bpt6k191912?rk=21459;2
를 클릭합니다Stern, Moritz A. (1858), "Ueber eine zahlentheoretische Funktion", Journal für die reine und angewandte Mathematik, 55: 193–220.
Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009), Combinatorics on words. Christoffel words and repetitions in words, CRM Monograph Series, vol. 27, Providence, RI: American Mathematical Society, ISBN 978-0-8218-4480-9, Zbl 1161.68043

외부 링크

Aiylam, Dhroova, Modified Stern-Brocot Sequences, arXiv:1301.6807, Bibcode:2013arXiv1301.6807A
Austin, David, Trees, Teeth, and Time: The mathematics of clock making, Feature Column from the AMS
를 클릭합니다Bogomolny, Alexander, Stern Brocot-Tree, cut-the-knot, retrieved 2008-09-03.
를 클릭합니다Sloane, N. J. A., The Stern–Brocot or Farey Tree, On-line Encyclopedia of Integer Sequences.
를 클릭합니다Wildberger, Norman, MF96: Fractions and the Stern-Brocot tree.
Weisstein, Eric W., "Stern–Brocot Tree", MathWorld
PlanetMath의 Stern-Brocot 트리.
무한 분수, 숫자 소수
놀라운 그래프 III, 숫자 기호
OEIS 시퀀스 A002487(Stern의 이원자 계열(또는 Stern-Brocot 시퀀스))

[1] Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1994), Concrete mathematics (Second ed.), Addison-Wesley, pp. 116–118, ISBN 0-201-55802-5

[2] 를 클릭합니다Gibbons, Jeremy; Lester, David; Bird, Richard (2006), "Functional pearl: Enumerating the rationals", Journal of Functional Programming, 16 (3): 281–291, doi:10.1017/S0956796806005880.

[3] Sedgewick과 Wayne, Java 프로그래밍 입문이 알고리즘의 Java 실장은 여기서 확인할 수 있습니다.

[4] 보고몰리는 이 재산을 캐나다의 음악 이론가인 피에르 라모테의 공으로 돌린다.

[1]

[2]

[3]

[4]

Search

스턴브로코트나무

네임스페이스

더

목차

연속 분수 나무

중개자 및 이진 검색

Farey 시퀀스와의 관계

기타 속성

「」를 참조해 주세요.

메모들

레퍼런스

외부 링크

Search

스턴브로코트나무

연속 분수 나무

중개자 및 이진 검색

Farey 시퀀스와의 관계

기타 속성

「 」를 참조해 주세요.

메모들

레퍼런스

외부 링크

「」를 참조해 주세요.