Ряд Фарея

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

ОпределениеПравить

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

\text{[math]}

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

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

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

ПримерПравить

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

\text{[math]}

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

\text{[math]}

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

\text{[math]}

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

\text{[math]}

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

\text{[math]}

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

\text{[math]}

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

\text{[math]}

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

\text{[math]}

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

СвойстваПравить

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

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

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

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

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

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

\text{[math]}

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

\text{[math]}

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

См. такжеПравить

СсылкиПравить

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