Ряд Фарея

Последовательность Фарея ${\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 "%d/%d" % (a,b)
    while (asc and c <= n) or (not asc and a > 0):
        k = int((n + b)/d)
        a, b, c, d = c, d, k*c - a, k*d - b
        print "%d/%d" % (a,b)

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

class Fraction {
  constructor(numer, denom) {
    this.numer = numer;
    this.denom = denom;
  }
  copy() {
    return new Fraction(this.numer, this.denom);
  }
}
function* farey(n, asc = true) {
  let [a, b] = asc ? [
    new Fraction(0, 1),
    new Fraction(1, n)
  ] : [
    new Fraction(1, 1),
    new Fraction(n - 1, n)
  ];
  yield a.copy();
  while (asc && b.numer <= n || !asc && a.numer > 0) {
    yield b.copy();
    const k = Math.floor((n + a.denom) / b.denom),
      next = new Fraction(k * b.numer - a.numer, k * b.denom - a.denom);
    a = b;
    b = next;
  }
}

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

Джон Фарей — известный геолог, один из пионеров геофизики. Его единственным вкладом в математику были дроби, названные его именем. В 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.