Штерн-Брокотын мод ба Фарейн дараалал¶

Штерн-Брокотын мод¶

Штерн-Брокотын мод нь бүх эерэг бутархайн олонлогийг илэрхийлэх дэгжин байгууламж юм. Үүнийг Германы математикч Мориц Штерн 1858 онд, Францын цаг үйлдвэрлэгч Ашиль Брокот 1861 онд бие даан нээсэн. Гэвч зарим эх сурвалж нээлтийг эртний Грекийн математикч Эратосфенд холбодог.

Байгууламж нь тэг дэх итерацид дараах хоёр бутархайгаас эхэлнэ

$$ \frac{0}{1}, \frac{1}{0} $$

энд хоёр дахь хэмжигдэхүүн нь чанд утгаараа бутархай биш боловч түүнийг хязгааргүйг илэрхийлэх үл хураагдах бутархай гэж тайлбарлаж болохыг тэмдэглэх нь зүйтэй.

Дараагийн итерац бүрд бүх зэргэлдээ $\frac{a}{b}$ ба $\frac{c}{d}$ бутархайг авч үзэж, тэдгээрийн хооронд медиант $\frac{a+c}{b+d}$-г оруулна.

Эхний хэдэн итерац дараах байдалтай харагдана:

$$ \begin{array}{c} \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} $$

Энэ процессыг хязгааргүй үргэлжлүүлбэл энэ нь бүх эерэг бутархайг хамарна. Түүнчлэн бүх бутархай цор ганц бөгөөд үл хураагдах байна. Эцэст нь бутархайнууд мөн өсөх дарааллаар гарч ирнэ.

Эдгээр шинж чанарыг батлахаас өмнө жагсаалтан илэрхийллийн оронд Штерн-Брокотын модны дүрслэлийг үзүүлье. Мод дахь бутархай бүр хоёр хүүхэдтэй. Хүүхэд бүр нь зүүн талын хамгийн ойрын өвөг ба баруун талын хамгийн ойрын өвгийн медиант юм.

Баталгаанууд¶

Эрэмбэлэлт. Эрэмбэлэлтийг батлах нь энгийн. Хоёр бутархайн медиант нь үргэлж тэдгээр бутархайн хооронд байдгийг тэмдэглэе

$$ \frac{a}{b} \le \frac{a+c}{b+d} \le \frac{c}{d} $$

тэгэхдээ

$$ \frac{a}{b} \le \frac{c}{d}. $$

байх нөхцөлд. Энэ хоёр тэнцэтгэл бишийг бутархайг нийтлэг хуваарьтай дахин бичих замаар амархан харуулж болно.

Тэг дэх итерацид эрэмбэлэлт өсөх байдалтай байгаа тул дараагийн итерац бүрд хадгалагдана.

Үл хураагдах чанар. Үүнийг батлахын тулд дурын хоёр зэргэлдээ $\frac{a}{b}$ ба $\frac{c}{d}$ бутархайн хувьд

$$ bc - ad = 1. $$

байхыг харуулна. $ax+by=c$ хоёр хувьсагчтай Диофантын тэгшитгэл нь $c$ нь $\gcd(a,b)$-ийн үржвэр байвал, зөвхөн тэр үед л шийдтэй болохыг эргэн санаарай. Манай тохиолдолд энэ нь $\gcd(a,b) = \gcd(c,d) = 1$ гэсэн үг бөгөөд энэ нь бидний харуулахыг хүсэж буй зүйл юм.

Тэг дэх итерацид $bc - ad = 1$ байх нь тодорхой. Медиантууд энэ шинжийг хадгалдгийг харуулах нь үлдэж байна.

Манай хоёр зэргэлдээ бутархай $bc - ad = 1$-ийг хангаж байна гэж үзье, медиантыг жагсаалтад нэмсний дараа

$$ \frac{a}{b}, \frac{a+c}{b+d}, \frac{c}{d} $$

шинэ илэрхийллүүд

$$\begin{align} b(a+c) - a(b+d) &= 1 \\ c(b+d) - d(a+c) &= 1 \end{align}$$

болох ба $bc-ad=1$-ийг ашиглан үнэн болохыг амархан харуулж болно.

Эндээс бид энэ шинж үргэлж хадгалагддаг, иймээс бүх бутархай үл хураагдах болохыг харна.

Бүх бутархайн оршин байдал. Энэ баталгаа нь Штерн-Брокотын мод дахь бутархайг байрлуулахтай нягт холбоотой. Эрэмбэлэлтийн шинжээс бутархайн зүүн дэд мод нь зөвхөн эцэг бутархайгаас бага бутархайг агуулах ба баруун дэд мод нь зөвхөн эцэг бутархайгаас их бутархайг агуулна гэдгийг бид мэднэ. Энэ нь бид модыг үндэснээс нь туулж, зорилтот бутархай нь одоогийнхоос бага бол зүүн тийш, их бол баруун тийш явж бутархайг хайж болно гэсэн үг.

Дурын эерэг зорилтот $\frac{x}{y}$ бутархайг ав. Энэ нь $\frac{0}{1}$ ба $\frac{1}{0}$-ийн хооронд байх нь тодорхой тул бутархай модонд байхгүй байх цорын ганц арга бол түүнд хүрэхэд хязгааргүй тооны алхам шаардагдах явдал юм.

Хэрэв тийм бол бид бүх итерацид

$$ \frac{a}{b} \lt \frac{x}{y} \lt \frac{c}{d} $$

байх ба үүнийг ($z \gt 0 \iff z \ge 1$ байх бүхэл тоо гэдгийг ашиглан)

$$ \begin{align} bx - ay &\ge 1 \\ cy - dx &\ge 1. \end{align} $$

гэж дахин бичиж болно. Одоо эхний тэнцэтгэл бишийг $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$-ийн дор хаяж нэг нь нэмэгдэх тул бутархай хайх процесс $x+y$-ээс олонгүй итерац агуулна. Энэ нь $\frac{x}{y}$ хүрэх зам хязгааргүй байсан гэсэн таамаглалтай зөрчилдөх тул $\frac{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;

    ... 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' тэмдэгтүүдийн дараалал (харгалзан зүүн ба баруун хүүхэд рүү туулахыг илэрхийлнэ) хэлбэрээр буцаадаг хэрэгжүүлэлт байна. Энэ тэмдэгтүүдийн дараалал нь бүх эерэг бутархайг цор ганцаар тодорхойлдог бөгөөд Штерн-Брокотын тооллын систем гэж нэрлэгддэг.

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;
}

Штерн-Брокотын тооллын систем дэх иррационал тоонууд нь тэмдэгтүүдийн хязгааргүй дараалалд харгалзана. Иррационал тоо руу чиглэсэн төгсгөлгүй замын дагуу алгоритм нь хуваарь нь аажмаар нэмэгддэг, иррационал тооны улам сайн ойролцоололыг өгдөг хураагдсан бутархайнуудыг олно. Тиймээс хязгааргүй дарааллын угтварыг авснаар дурын хүссэн нарийвчлалтай ойролцооллд хүрч болно. Энэ хэрэглээ нь цаг үйлдвэрлэлд чухал бөгөөд яагаад энэ модыг тэр салбарт нээсэнийг тайлбарладаг.

$\frac{p}{q}$ бутархайн хувьд гарсан дарааллын урт нь жишээ нь бутархай $\frac{p}{1}$ хэлбэртэй үед $O(p+q)$ хэр их байж болохыг анхаарна уу. Энэ нь дээрх алгоритмыг энэ нь хүлээн зөвшөөрөгдөх complexity биш л бол ашиглаж болохгүй гэсэн үг!

Логарифм хайлт¶

Аз болоход дээрх алгоритмыг $O(\log (p+q))$ complexity-г баталгаажуулахаар сайжруулж болно. Үүний тулд одоогийн зааг бутархайнууд $\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}$ бутархай хүрэх замыг түүний давталтын урттай кодчилол хэлбэрээр олж болно.

Чиглэлүүд ингэж ээлжлэн солигдох тул бид аль нэгийг сонгохоо үргэлж мэднэ. Тиймээс тав тухтай байлгах үүднээс бид $\frac{p}{q}$ бутархай хүрэх замыг бутархайнуудын дараалал хэлбэрээр илэрхийлж болно

$$ \frac{p_0}{q_0}, \frac{p_1}{q_1}, \frac{p_2}{q_2}, \dots, \frac{p_n}{q_n}, \frac{p_{n+1}}{q_{n+1}} = \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$-р алхмын дараа бид

$$ \frac{p_{k+1}}{q_{k+1}} = \frac{p_{k-1} + a_k p_k}{q_{k-1} + a_k q_k}, $$

бутархай руу шилжинэ, энд $a_k$ нь эерэг бүхэл тоо. Хэрэв та гинжин бутархай-тай танил бол $\frac{p_i}{q_i}$ дараалал нь $\frac{p}{q}$-ийн ойртох бутархайнуудын дараалал бөгөөд $[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}$-г аль хэдийн мэддэг бөгөөд Штерн-Брокотын мод дахь байрлалыг нь олохыг хүсэж байвал л ажиллана.

Практикт $\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$ бүрийг хоёртын хайлтаар олох замаар Штерн-Брокотын мод дээрх хайлтыг дуурайлж болно. Тэгвэл алгоритм арай техникийн шинжтэй болж, бодлогын томьёолол танд $a_k$-г илүү хурдан олох боломж олгохгүй л бол (жишээ нь ямар нэг мэдэгдэж буй илэрхийллийн floor-ыг ашиглан) $O(\log^2(x+y))$ complexity-тэй байж болзошгүй.

Фарейн дараалал¶

$n$ эрэмбийн Фарейн дараалал гэдэг нь хуваарь нь $n$-ээс хэтрэхгүй, $0$ ба $1$-ийн хоорондох бутархайнуудын эрэмбэлэгдсэн дараалал юм.

Дараалуудыг Английн геологич Жон Фарейн нэрээр нэрлэсэн бөгөөд тэрээр 1816 онд Фарейн дараалал дахь дурын бутархай нь хөршүүдийнхээ медиант байдаг гэж таамагласан. Үүнийг хэсэг хугацааны дараа Коши баталсан боловч тэдний хоёулангаас үл хамааран математикч Харос 1802 онд бараг ижил дүгнэлтэд хүрсэн байна.

Фарейн дараалал өөрөө олон сонирхолтой шинж чанартай боловч Штерн-Брокотын модтой холбоо нь хамгийн тодорхой юм. Үнэн хэрэгтээ Фарейн дараалуудыг модноос салаануудыг тайрч авах замаар олж болно.

Штерн-Брокотын мод байгуулах алгоритмаас бид Фарейн дараалуудын алгоритмыг олж авна. $\frac{0}{1}, \frac{1}{0}$ бутархайнуудын жагсаалтаас эхэл. Дараагийн итерац бүрд медиантыг зөвхөн хуваарь нь $n$-ээс хэтрэхгүй бол оруул. Хэзээ нэгэн цагт жагсаалт өөрчлөгдөхөө болих ба хайж буй Фарейн дараалал олдсон байна.

Фарейн дарааллын урт¶

$n$ эрэмбийн Фарейн дараалал нь $n-1$ эрэмбийн Фарейн дарааллын бүх элемент, түүнчлэн хуваарь нь $n$ байх бүх үл хураагдах бутархайг агуулах ба сүүлийнх нь зүгээр л тотиент $\varphi(n)$ юм. Тиймээс $n$ эрэмбийн Фарейн дарааллын урт $L_n$ нь

$$ L_n = L_{n-1} + \varphi(n) $$

эсвэл эквивалентаар рекурсийг задалбал бид

$$ L_n = 1 + \sum_{k=1}^n \varphi(k). $$

-г олж авна.