Ряд Фарея

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

Определение

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

$F_n\stackrel{\text{def}}{=}\{\frac{a_i}{b_i}:0⩽a_i⩽b_i⩽n,\gcd (a_i,b_i)=1,\frac{a_i}{b_i}<\frac{a_{i+1}}{b_{i+1}}\}.$

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

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

Пример

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

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

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

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

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

$F_5=\{\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}\};$

$F_6=\{\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}\};$

$F_7=\{\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}\};$

$F_8=\{\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}\}.$

Свойства

Шаблон:Рамка Если $p_1/q_1<p_2/q_2$ — две соседние дроби в ряде Фарея, тогда $q_1{p}_2-q_2{p}_1=1$. Шаблон:Конец рамки Шаблон:Скрытый

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

Алгоритм генерации всех дробей 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=\lfloor \frac{n+b}{d}\rfloor c-a$

$q=\lfloor \frac{n+b}{d}\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 года о приближении десятичных дробей обыкновенными дробями.

См. также

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

Ссылки

• Шаблон:Статья
• Шаблон:MathWorld
• Числители и знаменатели рядов Фарея: Шаблон:OEIS и Шаблон:OEIS.
• Farey sequence на сайте Шаблон:Iw.