Викия

Математика

Дроби Фарея

1457статей на
этой вики
Добавить новую страницу
Обсуждение2 Share

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

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

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

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

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

F_n\stackrel{\mathrm{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\}.

Последовательность Фарея порядка n+1 можно построить из последовательности порядка n по следующему правилу:

  1. Копируем все элементы последовательности порядка n.
  2. Если сумма знаменателей в двух соседних дробях последовательности порядка n дает число не большее, чем n+1, вставляем между этими дробями их медианту, равную отношению суммы их числителей к сумме знаменателей.

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

Последовательности Фарея для n от 1 до 8:

F_1=\left\{\frac{0}{1},\;\frac{1}{1}\right\};
F_2=\left\{\frac{0}{1},\;\frac{1}{2},\;\frac{1}{1}\right\};
F_3=\left\{\frac{0}{1},\;\frac{1}{3},\;\frac{1}{2},\;\frac{2}{3},\;\frac{1}{1}\right\};
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\};
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\};
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\};
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\};
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\}.

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

Если p_1/q_1<p_2/q_2 — две соседние дроби в ряде Фарея, тогда q_1p_2-q_2p_1=1.

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

Справедливо и обратное утверждение: если дроби p_1/q_1<p_2/q_2 таковы, что q_1p_2-q_2p_1=1, то они представляют собой соседние члены ряда Фарея F_{\max\{q_1,q_2\}}. }}

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

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

 p = \left\lfloor\frac{n+b}{d}\right\rfloor c - a
 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» («Об интересном свойстве обыкновенных дробей»), в которой Фарей определил последовательность F_n. Эта статья Фарея дошла до Коши, который в том же году опубликовал доказательство. Интересен тот факт, что последовательность, описанная Фареем в 1816 году, была использована Ш. Харосом в его статье 1802 года о приближении десятичных дробей обыкновенными дробями.

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

Викия-сеть

Случайная вики