Ряд Фарея

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Дроби Фарея»)
Перейти к навигации Перейти к поиску

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

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

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

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

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

Пример[править | править код]

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

Свойства[править | править код]

Если  — две соседние дроби в ряде Фарея, тогда .

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

Алгоритм генерации всех дробей Fn очень прост, как в возрастающем, так и в убывающем порядке. Каждая итерация алгоритма строит следующую дробь на основе двух предыдущих. Таким образом, если и — две уже построенные дроби, а — следующая неизвестная, то выполняется . Это значит, что для некоторого целого верно и , отсюда и . Так как должна быть максимально близкой к , то положим знаменатель максимальным из возможных, то есть , отсюда c учётом того, что — целое, имеем и

Пример реализации на 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)

Пример реализации на JavaScript:

class Fraction {
  constructor(numer, denom) {
    this.numer = numer;
    this.denom = denom;
  }
  copy() {
    return new Fraction(this.numer, this.denom);
  }
}
function* farey(n, asc = true) {
  let [a, b] = asc ? [
    new Fraction(0, 1),
    new Fraction(1, n)
  ] : [
    new Fraction(1, 1),
    new Fraction(n - 1, n)
  ];
  yield a.copy();
  while (asc && b.numer <= n || !asc && a.numer > 0) {
    yield b.copy();
    const k = Math.floor((n + a.denom) / b.denom),
      next = new Fraction(k * b.numer - a.numer, k * b.denom - a.denom);
    a = b;
    b = next;
  }
}

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

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

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

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

Ссылки[править | править код]