Ряд Фарея

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Определение[править | править вики-текст]

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

Алгоритм генерации[править | править вики-текст]

Алгоритм генерации всех дробей 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)

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

История[править | править вики-текст]

Джон Фарей (John Farey) — известный геолог, один из пионеров геофизики. Его единственным вкладом в математику были дроби, названные его именем. В 1816 году была опубликована статья Фарея «On a curious property of vulgar fractions» («Об интересном свойстве обыкновенных дробей»), в которой Фарей определил последовательность F_n. Эта статья Фарея дошла до Коши, который в том же году опубликовал доказательство. Интересен тот факт, что последовательность, описанная Фареем в 1816 году, была использована Ш.Харосом (англ.) в его статье 1802 года о приближении десятичных дробей обыкновенными дробями.

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]