ряды фарея близкие дроби

Дерево Штерна — Броко — Википедия

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

Материал из Википедии — свободной энциклопедии

Дерево Штерна — Броко — способ расположения всех неотрицательных несократимых дробей в вершинах упорядоченного бесконечного двоичного .

В каждом узле дерева Штерна — Броко (иногда также называемого ) стоит дробей и , стоящих в ближайших к этому узлу левом и правом верхних узлах. Начальный кусок дерева Штерна — Броко в этом случае выглядит так:

Близким по построению к дереву Штерна — Броко является , в котором дробь является корнем, а все прочие узлы заполняются по следующему алгоритму: каждая вершина имеет двух потомков: левого и правого .

В книге Р. Грэхема, Д. Кнута, О. Паташника Конкретная математика открытие «дерева Штерна — Броко» связывается с именами Морица Штерна (1858) и Ахилла Броко (1860). Однако аналогичное построение в форме «дерева Калкина-Уилфа» было известно ещё древнегреческим математикам. Оно описано под именем «порождения всех отношений из отношения равенства как из матери и корня» в двух математических обзорах II в. н. э., принадлежащих и . Теон сообщает, что эта конструкция была известна — знаменитому учёному, жившему в III в. до н. э.

Все дроби в деревьях Калкина — Уилфа и Штерна — Броко несократимы;

Каждая несократимая дробь появляется в дереве ровно один раз.

Для дерева Калкина — Уилфа эти свойства легко доказываются, если заметить, что каждому шагу по дереву в направлении к корню соответствует элементарный шаг вычитания меньшего числа из большего в для поиска наибольшего общего делителя.

source