Русская Википедия:Ряд Фарея
Ряды Фарея (также дроби Фарея, последовательность Фарея или таблица Фарея) — семейство конечных подмножеств рациональных чисел.
Определение
Последовательность Фарея <math>n</math>-го порядка представляет собой возрастающий ряд всех положительных несократимых правильных дробей, знаменатель которых меньше или равен <math>n</math>:
- <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\}.</math>
Последовательность Фарея порядка <math>n + 1</math> можно построить из последовательности порядка <math>n</math> по следующему правилу:
- Копируем все элементы последовательности порядка <math>n</math>.
- Если сумма знаменателей в двух соседних дробях последовательности порядка <math>n</math> даёт число не большее, чем <math>n + 1</math>, то вставляем между этими дробями их медианту, равную отношению суммы их числителей к сумме знаменателей.
Пример
Последовательности Фарея для <math>n</math> от 1 до 8:
- <math>F_1=\left\{\frac{0}{1},\;\frac{1}{1}\right\};</math>
- <math>F_2=\left\{\frac{0}{1},\;\frac{1}{2},\;\frac{1}{1}\right\};</math>
- <math>F_3=\left\{\frac{0}{1},\;\frac{1}{3},\;\frac{1}{2},\;\frac{2}{3},\;\frac{1}{1}\right\};</math>
- <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\};</math>
- <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\};</math>
- <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\};</math>
- <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\};</math>
- <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\}.</math>
Свойства
Шаблон:Рамка Если <math>p_1/q_1<p_2/q_2</math> — две соседние дроби в ряде Фарея, тогда <math>q_1p_2-q_2p_1=1</math>. Шаблон:Конец рамки Шаблон:Скрытый</math>. }}
Алгоритм генерации
Алгоритм генерации всех дробей Fn очень прост, как в возрастающем, так и в убывающем порядке. Каждая итерация алгоритма строит следующую дробь на основе двух предыдущих. Таким образом, если <math>\frac{a}{b}</math> и <math>\frac{c}{d}</math> — две уже построенные дроби, а <math>\frac{p}{q}</math> — следующая неизвестная, то выполняется <math>\frac{c}{d} = \frac{a + p}{b + q}</math>. Это значит, что для некоторого целого <math>k</math> верно <math>kc = a + p</math> и <math>kd = b + q</math>, отсюда <math>p = kc - a</math> и <math>q = kd - b</math>. Так как <math>\frac{p}{q}</math> должна быть максимально близкой к <math>\frac{c}{d}</math>, то положим знаменатель максимальным из возможных, то есть <math>kd - b = n</math>, отсюда c учётом того, что <math>k</math> — целое, имеем <math>k = \lfloor\frac{n + b}{d}\rfloor</math> и
- <math> p = \left\lfloor\frac{n+b}{d}\right\rfloor c - a</math>
- <math> q = \left\lfloor\frac{n+b}{d}\right\rfloor d - b</math>
Пример реализации на 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» («Об интересном свойстве обыкновенных дробей»), в которой он определил последовательность <math>F_n</math>. Эта статья дошла до Коши, который в том же году опубликовал доказательство гипотезы Фарея о том, что каждый новый член последовательности Фарея порядка <math>n+1</math> является медиантой своих соседей. Последовательность, описанная Фареем в 1816 году, была использована en (Charles Haros) в его статье 1802 года о приближении десятичных дробей обыкновенными дробями.
См. также
Ссылки
- Шаблон:Статья
- Шаблон:MathWorld
- Числители и знаменатели рядов Фарея: Шаблон:OEIS и Шаблон:OEIS.
- Farey sequence на сайте Шаблон:Iw.
