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

Определение

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

${\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}}}<{\frac {a_{i+1}}{b_{i+1}}}\right\}.}$

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

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

Пример

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

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

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

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

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

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

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

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

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

Свойства

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

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

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

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

См. также

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

Ссылки

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