Ряд Фарея

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

Определение

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

$F_{n}{\stackrel {\text{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_{1}p_{2}-q_{2}p_{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_{1}p_{2}-q_{2}p_{1})/2$. Ч. т. д.

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

Алгоритм генерации

Алгоритм генерации всех дробей F_n очень прост, как в возрастающем, так и в убывающем порядке. Каждая итерация алгоритма строит следующую дробь на основе двух предыдущих. Таким образом, если ${\frac {a}{b}}$ и ${\frac {c}{d}}$ — две уже построенные дроби, а ${\frac {p}{q}}$ — следующая неизвестная, то выполняется ${\frac {c}{d}}={\frac {a+p}{b+q}}$. Это значит, что для некоторого целого $k$ верно $kc=a+p$ и $kd=b+q$, отсюда $p=kc-a$ и $q=kd-b$. Так как ${\frac {p}{q}}$ должна быть максимально близкой к ${\frac {c}{d}}$, то положим знаменатель максимальным из возможных, то есть $kd-b=n$, отсюда c учётом того, что $k$ — целое, имеем $k=\lfloor {\frac {n+b}{d}}\rfloor$ и

$p=\left\lfloor {\frac {n+b}{d}}\right\rfloor c-a$

$q=\left\lfloor {\frac {n+b}{d}}\right\rfloor d-b$

Пример реализации на Python:

def farey( n, asc=True ):
    if asc: 
        a, b, c, d = 0, 1, 1, n
    else:
        a, b, c, d = 1, 1, n-1, n
    print(f"{a}/{b}")
    while (asc and c <= n) or (not asc and a > 0):
        k = (n + b) // d
        a, b, c, d = c, d, k*c - a, k*d - b
        print(f"{a}/{b}")

Таким образом можно построить сколь угодно большое множество всех дробей в сокращенном виде, что можно использовать, например, для решения Диофантова уравнения полным перебором в рациональных числах.

История

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

См. также

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

Ссылки

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