Ряд Фарея

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

Определение

Последовательность Фарея $n$-ного порядка представляет собой возрастающий ряд всех несократимых дробей, знаменатель которых меньше или равен $n$:

$F_n\stackrel{\mathrm{def}}{=}\left\{\frac{a_i}{b_i}:\;0 \leqslant a_i \leqslant b_i \leqslant n,\;\gcd(a_i,\;b_i)=1,\;\frac{a_i}{b_i}<\;\frac{a_{i+1}}{b_{i+1}}\right\}.$

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

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

Пример

Последовательности Фарея для $n$ от 1 до 8:

$F_1=\left\{\frac{0}{1},\;\frac{1}{1}\right\};$

$F_2=\left\{\frac{0}{1},\;\frac{1}{2},\;\frac{1}{1}\right\};$

$F_3=\left\{\frac{0}{1},\;\frac{1}{3},\;\frac{1}{2},\;\frac{2}{3},\;\frac{1}{1}\right\};$

$F_4=\left\{\frac{0}{1},\;\frac{1}{4},\;\frac{1}{3},\;\frac{1}{2},\;\frac{2}{3},\;\frac{3}{4},\;\frac{1}{1}\right\};$

$F_5=\left\{\frac{0}{1},\;\frac{1}{5},\;\frac{1}{4},\;\frac{1}{3},\;\frac{2}{5},\;\frac{1}{2},\;\frac{3}{5},\;\frac{2}{3},\;\frac{3}{4},\;\frac{4}{5},\;\frac{1}{1}\right\};$

$F_6=\left\{\frac{0}{1},\;\frac{1}{6},\;\frac{1}{5},\;\frac{1}{4},\;\frac{1}{3},\;\frac{2}{5},\;\frac{1}{2},\;\frac{3}{5},\;\frac{2}{3},\;\frac{3}{4},\;\frac{4}{5},\;\frac{5}{6},\;\frac{1}{1}\right\};$

$F_7=\left\{\frac{0}{1},\;\frac{1}{7},\;\frac{1}{6},\;\frac{1}{5},\;\frac{1}{4},\;\frac{2}{7},\;\frac{1}{3},\;\frac{2}{5},\;\frac{3}{7},\;\frac{1}{2},\;\frac{4}{7},\;\frac{3}{5},\;\frac{2}{3},\;\frac{5}{7},\;\frac{3}{4},\;\frac{4}{5},\;\frac{5}{6},\;\frac{6}{7},\;\frac{1}{1}\right\};$

$F_8=\left\{\frac{0}{1},\;\frac{1}{8},\;\frac{1}{7},\;\frac{1}{6},\;\frac{1}{5},\;\frac{1}{4},\;\frac{2}{7},\;\frac{1}{3},\;\frac{3}{8},\;\frac{2}{5},\;\frac{3}{7},\;\frac{1}{2},\;\frac{4}{7},\;\frac{3}{5},\;\frac{5}{8},\;\frac{2}{3},\;\frac{5}{7},\;\frac{3}{4},\;\frac{4}{5},\;\frac{5}{6},\;\frac{6}{7},\;\frac{7}{8},\;\frac{1}{1}\right\}.$

Свойства

Если $p_1/q_1<p_2/q_2$ — две соседние дроби в ряде Фарея, тогда $q_1p_2-q_2p_1=1$.

Доказательство. Заметим, что треугольник на плоскости с вершинами $A=(0,\;0)$, $B=(p_1,\;q_1)$ и $C=(p_2,\;q_2)$ не может содержать целых точек, отличных от вершин. Иначе, если целая точка $(r,\;s)$ содержится в $\triangle ABC$, то дробь $r/s$ лежит между $p_1/q_1$ и $p_2/q_2$, а знаменатель $s$ не превосходит $\max\{q_1,\;q_2\}$. Значит, по формуле Пика, его площадь равна $1/2$. С другой стороны, площадь $\triangle ABC$ равна $(q_1p_2-q_2p_1)/2$. Ч. т. д.

Справедливо и обратное утверждение: если дроби $p_1/q_1<p_2/q_2$ таковы, что $q_1p_2-q_2p_1=1$, то они представляют собой соседние члены ряда Фарея $F_{\max\{q_1,q_2\}}$.

История

Джон Фарей (John Farey) — известный геолог, один из пионеров геофизики. Его единственным вкладом в математику были дроби, названные его именем. В 1816 году была опубликована статья Фарея «On a curious property of vulgar fractions» («Об интересном свойстве обыкновенных дробей»), в которой Фарей определил последовательность $F_n$. Эта статья Фарея дошла до Коши, который в том же году опубликовал доказательство. Интересен тот факт, что последовательность, описанная Фареем в 1816 году, была использована Харосом в его статье 1802 года о приближении десятичных дробей обыкновенными дробями.

См. также

• Дерево Штерна — Броко
• Функция Минковского

Ссылки

• Кноп К. Недвоичная система // Домашний компьютер. — 2001. — № 8.
• Weisstein, Eric W. Farey Sequence (англ.) на сайте Wolfram MathWorld.
• Числители и знаменатели рядов Фарея: последовательность A006842 в OEIS и последовательность A006843 в OEIS.