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

Определение

править

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

 

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

  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(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» («Об интересном свойстве обыкновенных дробей»), в которой он определил последовательность  . Эта статья дошла до Коши, который в том же году опубликовал доказательство гипотезы Фарея о том, что каждый новый член последовательности Фарея порядка   является медиантой своих соседей. Последовательность, описанная Фареем в 1816 году, была использована Шарлем Харосом[англ.] в его статье 1802 года о приближении десятичных дробей обыкновенными дробями.

См. также

править

Ссылки

править