Дерево Штерна–Броко та послідовності Фарея

Дерево Штерна–Броко

Дерево Штерна–Броко — це елегантна конструкція для представлення множини всіх додатних дробів. Воно було незалежно відкрите німецьким математиком Моріцом Штерном у 1858 році та французьким годинникарем Ашилем Броко у 1861 році. Утім, деякі джерела приписують це відкриття давньогрецькому математику Ератосфену.

Коли підходить цей алгоритм?

• Чи працюєш із дробами ($\frac{p}{q}$) та потрібен їх упорядкований нескоротний перелік або пошук?
• Чи задачу можна звести до бінарного пошуку дробу за предикатом «$\frac{x}{y} < \frac{p}{q}$»? (якщо потрібне саме розкладання дробу — див. ланцюгові дроби)
• Чи допустима логарифмічна глибина спуску — або потрібен крок run-length, щоб уникнути $O(p+q)$?

Конструкція починається на нульовій ітерації з двох дробів

$$\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}$ відповідно. Використовуючи їх, ми обчислюємо медіанту і спускаємося на один рівень глибше, причому медіанта замінює правого предка в лівому піддереві, і навпаки.

Цей псевдокод намагається побудувати все нескінченне дерево:

C++

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

Python

def build(a=0, b=1, c=1, d=0, level=1):
    x, y = a + c, b + d

    ...  # вивести поточний дріб x/y на поточному рівні дерева

    build(a, b, x, y, level + 1)
    build(x, y, c, d, level + 1)

TypeScript

function build(a = 0, b = 1, c = 1, d = 0, level = 1): void {
  const x = a + c, y = b + d;

  // ... вивести поточний дріб x/y на поточному рівні дерева

  build(a, b, x, y, level + 1);
  build(x, y, c, d, level + 1);
}

Go

func build(a, b, c, d, level int) {
    x, y := a+c, b+d

    _ = x // ... вивести поточний дріб x/y на поточному рівні дерева
    _ = y

    build(a, b, x, y, level+1)
    build(x, y, c, d, level+1)
}
// Виклик: build(0, 1, 1, 0, 1)

Алгоритм пошуку дробу

Алгоритм пошуку вже описано у доведенні того, що всі дроби з'являються в дереві, але ми повторимо його тут. Цей алгоритм є алгоритмом бінарного пошуку. Спочатку ми стоїмо в корені дерева і порівнюємо нашу ціль з поточним дробом. Якщо вони однакові, ми завершили роботу і зупиняємо процес. Якщо наша ціль менша, ми переходимо до лівого нащадка, інакше переходимо до правого нащадка.

Наївний пошук

Ось реалізація, яка повертає шлях до заданого дробу $\frac{p}{q}$ у вигляді послідовності символів 'L' і 'R', що означають перехід до лівого і правого нащадка відповідно. Ця послідовність символів однозначно визначає всі додатні дроби і називається системою числення Штерна–Броко.

C++

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

Python

def find(p, q):
    pL, qL = 0, 1
    pR, qR = 1, 0
    pM, qM = 1, 1
    res = []
    while pM != p or qM != q:
        if p * qM < pM * q:
            res.append('L')
            pR, qR = pM, qM
        else:
            res.append('R')
            pL, qL = pM, qM
        pM, qM = pL + pR, qL + qR
    return "".join(res)

TypeScript

function find(p: number, q: number): string {
  let pL = 0, qL = 1;
  let pR = 1, qR = 0;
  let pM = 1, qM = 1;
  let res = "";
  while (pM !== p || qM !== q) {
    if (p * qM < pM * q) {
      res += "L";
      [pR, qR] = [pM, qM];
    } else {
      res += "R";
      [pL, qL] = [pM, qM];
    }
    [pM, qM] = [pL + pR, qL + qR];
  }
  return res;
}

Go

func find(p, q int) string {
    pL, qL := 0, 1
    pR, qR := 1, 0
    pM, qM := 1, 1
    var res []byte
    for pM != p || qM != q {
        if p*qM < pM*q {
            res = append(res, 'L')
            pR, qR = pM, qM
        } else {
            res = append(res, 'R')
            pL, qL = pM, qM
        }
        pM, qM = pL+pR, qL+qR
    }
    return string(res)
}

Ірраціональним числам у системі числення Штерна–Броко відповідають нескінченні послідовності символів. Уздовж нескінченного шляху до ірраціонального числа алгоритм знаходитиме скоротні дроби з поступово зростаючими знаменниками, які дають дедалі кращі наближення ірраціонального числа. Тож, узявши префікс цієї нескінченної послідовності, можна досягти наближень із будь-якою бажаною точністю. Це застосування є важливим у годинникарстві, що й пояснює, чому дерево було відкрите саме в цій галузі.

Зауважте, що для дробу $\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}$ у вигляді ланцюгового дробу:

C++

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

Python

def find(p, q):
    right = True
    res = []  # пари (довжина серії, напрямок)
    while q:
        res.append((p // q, 'R' if right else 'L'))
        p, q = q, p % q
        right = not right
    # остання серія коротша на один крок
    res[-1] = (res[-1][0] - 1, res[-1][1])
    return res

TypeScript

function find(p: number, q: number): [number, string][] {
  let right = true;
  const res: [number, string][] = []; // пари [довжина серії, напрямок]
  while (q) {
    res.push([Math.floor(p / q), right ? "R" : "L"]);
    [p, q] = [q, p % q];
    right = !right;
  }
  // остання серія коротша на один крок
  res[res.length - 1][0]--;
  return res;
}

Go

type run struct {
    length int
    dir    byte
}

func find(p, q int) []run {
    right := true
    var res []run // пари (довжина серії, напрямок)
    for q != 0 {
        dir := byte('L')
        if right {
            dir = 'R'
        }
        res = append(res, run{p / q, dir})
        p, q = q, p%q
        right = !right
    }
    // остання серія коротша на один крок
    res[len(res)-1].length--
    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$ за допомогою бінарного пошуку. Тоді алгоритм стає трохи технічнішим і потенційно має складність $O(\log^2(x+y))$, якщо тільки формулювання задачі не дозволяє знайти $a_k$ швидше (наприклад, використовуючи floor від якогось відомого виразу).

Послідовність Фарея

Послідовність Фарея порядку $n$ — це відсортована послідовність дробів між $0$ і $1$, знаменники яких не перевищують $n$.

Ці послідовності названо на честь англійського геолога Джона Фарея, який у 1816 році висунув припущення, що будь-який дріб у послідовності Фарея є медіантою своїх сусідів. Це було доведено дещо пізніше Коші, але незалежно від обох математик Арос дійшов майже того самого висновку ще у 1802 році.

Послідовності Фарея мають багато цікавих властивостей самі по собі, але зв'язок із деревом Штерна–Броко є найочевиднішим. Насправді послідовності Фарея можна отримати, обрізаючи гілки дерева.

З алгоритму побудови дерева Штерна–Броко ми отримуємо алгоритм для послідовностей Фарея. Починаємо зі списку дробів $\frac{0}{1}, \frac{1}{0}$. На кожній наступній ітерації вставляємо медіанту лише тоді, коли знаменник не перевищує $n$. У певний момент список перестане змінюватися, і шукану послідовність Фарея буде знайдено.

Довжина послідовності Фарея

Послідовність Фарея порядку $n$ містить усі елементи послідовності Фарея порядку $n-1$, а також усі нескоротні дроби зі знаменником $n$, але останнє — це просто функція Ейлера $\varphi(n)$. Тож довжина $L_n$ послідовності Фарея порядку $n$ дорівнює

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

або, що еквівалентно, розгорнувши рекурсію, ми отримуємо

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

Відеоматеріали