Ряд Фарея

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

Последовательность Фарея ${\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\}.}$

• Если ${\displaystyle p_{1}/q_{1}$ — две соседние дроби в ряде Фарея, тогда ${\displaystyle q_{1}p_{2}-q_{2}p_{1}=1}$.

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

• Количество членов ${\displaystyle N(n)}$ в последовательности Фарея для целого ${\displaystyle n}$ определяется следующим образом:

${\displaystyle N(n)=1+\sum _{k=1}^{n}\phi (k)=1+\Phi (n).}$ Здесь ${\displaystyle \phi (n)}$ - функция Эйлера, ${\displaystyle \Phi (n)}$ - суммированная функция Эйлера. Значения ${\displaystyle N(n)-2,3,5,7,11,13,19,...-}$ являются последовательностью A005728 в OEIS.

• Для функции количества членов ${\displaystyle N(n)}$ существует асимптотическое представление:

${\displaystyle N(n)\sim {\frac {3n^{2}}{\pi ^{2}}}=0.3039635509...n^{2}}$, где цифры после запятой являются последовательностью A104141 в OEIS.

Алгоритм генерации всех дробей 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):ifasc:a,b,c,d=0,1,1,nelse:a,b,c,d=1,1,n-1,nprint(f"{a}/{b}")while(ascandc<=n)or(notascanda>0):k=(n+b)//da,b,c,d=c,d,k*c-a,k*d-bprint(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.Farey Sequence (англ.) на сайте Wolfram MathWorld.
• Числители и знаменатели рядов Фарея: последовательность A006842 в OEIS и последовательность A006843 в OEIS.
• Farey sequence на сайте Rosetta Code^[англ.].