WikiSort.ru - Не сортированное

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

Определение

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

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

История

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