Ряд Фарея

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

Определение

Последовательность Фарея [math]\displaystyle{ n }[/math]-го порядка представляет собой возрастающий ряд всех положительных несократимых правильных дробей, знаменатель которых меньше или равен [math]\displaystyle{ n }[/math]:

[math]\displaystyle{ 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} \lt \frac{a_{i+1}}{b_{i+1}}\right\}. }[/math]

Последовательность Фарея порядка [math]\displaystyle{ n + 1 }[/math] можно построить из последовательности порядка [math]\displaystyle{ n }[/math] по следующему правилу:

Копируем все элементы последовательности порядка [math]\displaystyle{ n }[/math].
Если сумма знаменателей в двух соседних дробях последовательности порядка [math]\displaystyle{ n }[/math] даёт число не большее, чем [math]\displaystyle{ n + 1 }[/math], то вставляем между этими дробями их медианту, равную отношению суммы их числителей к сумме знаменателей.

Пример

Последовательности Фарея для [math]\displaystyle{ n }[/math] от 1 до 8:

[math]\displaystyle{ F_1=\left\{\frac{0}{1},\;\frac{1}{1}\right\}; }[/math]

[math]\displaystyle{ F_2=\left\{\frac{0}{1},\;\frac{1}{2},\;\frac{1}{1}\right\}; }[/math]

[math]\displaystyle{ F_3=\left\{\frac{0}{1},\;\frac{1}{3},\;\frac{1}{2},\;\frac{2}{3},\;\frac{1}{1}\right\}; }[/math]

[math]\displaystyle{ 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\}; }[/math]

[math]\displaystyle{ 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\}; }[/math]

[math]\displaystyle{ 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\}; }[/math]

[math]\displaystyle{ 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\}; }[/math]

[math]\displaystyle{ 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\}. }[/math]

Свойства

Если [math]\displaystyle{ p_1/q_1\lt p_2/q_2 }[/math] — две соседние дроби в ряде Фарея, тогда [math]\displaystyle{ q_1p_2-q_2p_1=1 }[/math].

Доказательство.

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

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

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

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

[math]\displaystyle{ p = \left\lfloor\frac{n+b}{d}\right\rfloor c - a }[/math]

[math]\displaystyle{ q = \left\lfloor\frac{n+b}{d}\right\rfloor d - b }[/math]

Пример реализации на 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» («Об интересном свойстве обыкновенных дробей»), в которой он определил последовательность [math]\displaystyle{ F_n }[/math]. Эта статья дошла до Коши, который в том же году опубликовал доказательство гипотезы Фарея о том, что каждый новый член последовательности Фарея порядка [math]\displaystyle{ n+1 }[/math] является медиантой своих соседей. Последовательность, описанная Фареем в 1816 году, была использована Шарлем Харосом^[en] в его статье 1802 года о приближении десятичных дробей обыкновенными дробями.

См. также

Ссылки

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