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

«Последовательности Фарея» (Farey sequence, или ряды Фарея, дроби Фарея, таблица Фарея) — семейство конечных подмножеств рациональных чисел с особыми, математически красивыми, свойствами.

Последовательность Фарея n-го порядка — возрастающая последовательность Fₙ всех неотрицательных несократимых дробей, не превосходящих 1, знаменатели которых меньше или равны n. Дроби 0/n и 1/1 считаются первым и последним элементами Fₙ.

Джон Фарей (1766–1826, John Farey) — английский геолог, писатель. Один из пионеров геофизики. Автор многочисленных научных работ в области геологии, метрологии, садоводства, музыки. Его единственным вкладом в математику были дроби, названные его именем. Это результат его исследований математики звука.

В 1816 году была опубликована краткая статья Фарея «Об интересном свойстве обыкновенных дробей», в которой он определил последовательность Fₙ.

Эта статья дошла до французского математика О. Л. Коши, который в том же году опубликовал доказательство гипотезы Фарея о том, что каждый новый член последовательности Фарея порядка n является медиантой своих соседей.

Понятие медианты двух дробей введено А. Я. Хинчиным в теории цепных дробей. Медианта двух обыкновенных дробей a/b и c/d равна отношению суммы их числителей к сумме знаменателей: (a + c) / (b + d).

Последовательность Фарея порядка n + 1 можно построить рекурсивно из последовательности порядка n по следующему правилу:

1. Копируем все элементы последовательности порядка n.
2. Если сумма знаменателей в двух соседних дробях последовательности порядка n даёт число не большее, чем n + 1, то вставляем между этими дробями их медианту.

Давайте проделаем небольшой эксперимент и получим опыт работы с последовательностями Фарея. Вот пробные задания для этого:

1. Попытайтесь самостоятельно построить последовательность F₆.
2. Докажите, что если a/b < c/d — две соседние дроби в последовательности Фарея Fₙ, то bc − ad = 1. Справедливо и обратное утверждение: если дроби a/b < c/d таковы, что bc − ad = 1, то они представляют собой соседние члены ряда Фарея Fₙ, где n = max(b, d).
3. Медианта двух дробей обладает таким замечательным свойством: она лежит между ними. Попробуйте это доказать.
   Если a/b < c/d, то a/b < (a + c)/(b + d) < c/d.
4. Всех несократимых дробей со знаменателями, равными n, имеется в точности φ(n) (это известная в теории чисел функция Эйлера). Обозначив через Lₙ длину последовательности Fₙ, получим рекуррентное соотношение:
   Lₙ = Lₙ₋₁ + φ(n).

У последовательностей Фарея очень много интересных приложений, в том числе в олимпиадной математике. Существуют различные алгоритмы генерации всех дробей Fₙ, которые исследуются в информатике. Также последовательности Фарея дают интересные темы и для научно-исследовательских работ.

__________

Ответы

1. F₆ = {0/1, 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6, 1/1}

2. Доказательство прямой теоремы индукцией по n.

n = 1, F₁ состоит из пары 0/1 и 1/1.

1×1 – 0×1 = 1

Оценим шаг индукции при переходе из n в n + 1.

Пусть a/b < c/d и bc − ad = 1. При переходе в следующую последовательность Фарея между ними вставляется медианта (a + c)/(b + d). Докажем, что искомое соотношение выполняется и для новых пар.

• Пара a/b и (a + c)/(b + d):

b(a + c) − a(b + d) = bc − ad = 1

• Пара (a + c)/(b + d) и c/d:

(b + d)с − (a + c)d = bc − ad = 1