پرش به محتویات

درخت Stern-Brocot و دنباله‌های Farey

درخت Stern-Brocot

درخت Stern-Brocot یک ساختار زیبا برای نمایش مجموعه‌ی تمام کسرهای مثبت است. این درخت به طور مستقل توسط ریاضیدان آلمانی Moritz Stern در سال ۱۸۵۸ و ساعت‌ساز فرانسوی Achille Brocot در سال ۱۸۶۱ کشف شد. با این حال، برخی منابع این کشف را به ریاضیدان یونان باستان، Eratosthenes، نسبت می‌دهند.

این ساختار در تکرار صفرم با دو کسر زیر آغاز می‌شود:

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

باید توجه داشت که عبارت دوم دقیقاً یک کسر نیست، اما می‌توان آن را به عنوان یک کسر ساده‌نشدنی که نماینده بی‌نهایت است، در نظر گرفت.

در هر تکرار بعدی، تمام کسرهای مجاور $\frac{a}{b}$ و $\frac{c}{d}$ را در نظر گرفته و میانجی (mediant) آن‌ها، یعنی $\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} $$

با ادامه این فرآیند تا بی‌نهایت، این ساختار تمام کسرهای مثبت را پوشش می‌دهد. علاوه بر این، تمام کسرها یکتا و ساده‌نشدنی خواهند بود. در نهایت، کسرها به ترتیب صعودی نیز ظاهر خواهند شد.

قبل از اثبات این ویژگی‌ها، بیایید به جای نمایش لیستی، یک تصویر از درخت Stern-Brocot را نشان دهیم. هر کسر در درخت دو فرزند دارد. هر فرزند، میانجیِ نزدیک‌ترین جد در سمت چپ و نزدیک‌ترین جد در سمت راست است.

درخت Stern-Brocot

اثبات‌ها

ترتیب. اثبات مرتب بودن ساده است. می‌بینیم که میانجی دو کسر همیشه بین آن دو کسر قرار می‌گیرد:

$$ \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$ به راحتی می‌توان نشان داد که درست هستند.

از این رو، می‌بینیم که این ویژگی همیشه حفظ می‌شود و بنابراین تمام کسرها ساده‌نشدنی هستند.

وجود تمام کسرها. این اثبات ارتباط نزدیکی با پیدا کردن یک کسر در درخت Stern-Brocot دارد. بر اساس ویژگی ترتیب، می‌دانیم که زیردرخت چپ یک کسر فقط شامل کسرهایی کوچکتر از کسر والد است و زیردرخت راست فقط شامل کسرهایی بزرگتر از کسر والد است. این بدان معناست که می‌توانیم با پیمایش درخت از ریشه، یک کسر را جستجو کنیم: اگر کسر هدف کوچکتر از کسر فعلی باشد به چپ می‌رویم و اگر بزرگتر باشد به راست می‌رویم.

یک کسر مثبت دلخواه $\frac{x}{y}$ را به عنوان هدف انتخاب کنید. واضح است که این کسر بین $\frac{0}{1}$ و $\frac{1}{0}$ قرار دارد، بنابراین تنها راهی که این کسر در درخت نباشد این است که رسیدن به آن به تعداد بی‌نهایت مرحله نیاز داشته باشد.

اگر چنین باشد، در تمام تکرارها خواهیم داشت:

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

که (با استفاده از این واقعیت که برای یک عدد صحیح $z > 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}$ باید بخشی از درخت باشد.

الگوریتم ساخت درخت

برای ساختن هر زیردرخت از درخت Stern-Brocot، کافی است که جد چپ و راست آن را بدانیم. در سطح اول، اجداد چپ و راست به ترتیب $\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;

    // ... کسر فعلی x/y را در سطح فعلی درخت خروجی دهید

    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_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}$ را بدانیم و بخواهیم جایگاه آن را در درخت Stern-Brocot پیدا کنیم.

در عمل، اغلب پیش می‌آید که $\frac{p}{q}$ از قبل مشخص نیست، اما ما قادر به بررسی این هستیم که آیا برای یک $\frac{x}{y}$ مشخص، $\frac{x}{y} < \frac{p}{q}$ برقرار است یا خیر.

با دانستن این موضوع، می‌توانیم جستجو در درخت Stern-Brocot را با نگهداری مرزهای فعلی $\frac{p_{k-1}}{q_{k-1}}$ و $\frac{p_k}{q_k}$ و یافتن هر $a_k$ از طریق جستجوی دودویی شبیه‌سازی کنیم. در این صورت، الگوریتم کمی فنی‌تر می‌شود و به طور بالقوه پیچیدگی $O(\log^2(x+y))$ خواهد داشت، مگر اینکه صورت مسئله به شما اجازه دهد $a_k$ را سریع‌تر پیدا کنید (مثلاً با استفاده از floor یک عبارت مشخص).

دنباله Farey

دنباله Farey از مرتبه $n$ دنباله‌ای مرتب‌شده از کسرهای بین $۰$ و $۱$ است که مخرج آن‌ها از $n$ بیشتر نباشد.

این دنباله‌ها به نام زمین‌شناس انگلیسی، John Farey، نام‌گذاری شده‌اند که در سال ۱۸۱۶ حدس زد هر کسر در دنباله Farey، میانجی همسایگان خود است. این حدس مدتی بعد توسط کوشی (Cauchy) اثبات شد، اما مستقل از هر دوی آنها، ریاضیدانی به نام Haros تقریباً به همین نتیجه در سال ۱۸۰۲ رسیده بود.

دنباله‌های Farey به خودی خود ویژگی‌های جالب بسیاری دارند، اما ارتباط آنها با درخت Stern-Brocot از همه واضح‌تر است. در واقع، دنباله‌های Farey را می‌توان با هرس کردن شاخه‌های درخت به دست آورد.

از الگوریتم ساخت درخت Stern-Brocot، الگوریتمی برای ساخت دنباله‌های Farey به دست می‌آوریم. با لیست کسرهای $\frac{0}{1}, \frac{1}{0}$ شروع کنید. در هر تکرار بعدی، میانجی را تنها در صورتی درج کنید که مخرج آن از $n$ بیشتر نباشد. در نقطه‌ای، لیست دیگر تغییر نخواهد کرد و دنباله Farey مورد نظر به دست آمده است.

طول یک دنباله Farey

یک دنباله Farey از مرتبه $n$ شامل تمام عناصر دنباله Farey از مرتبه $n-1$ و همچنین تمام کسرهای ساده‌نشدنی با مخرج $n$ است. تعداد این کسرهای جدید برابر با تابع فی اویلر، $\varphi(n)$، است. بنابراین طول $L_n$ دنباله Farey از مرتبه $n$ برابر است با:

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

یا به طور معادل، با باز کردن رابطه بازگشتی به دست می‌آوریم:

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