Ряд Фарея

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

Определение


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

Fn=def{aibi:0aibin,gcd(ai,bi)=1,aibi<ai+1bi+1}.
  Последовательность Фарея порядка n+1 можно построить из последовательности порядка n по следующему правилу:

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

Пример


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

F1={01,11};
F2={01,12,11};
F3={01,13,12,23,11};
F4={01,14,13,12,23,34,11};
F5={01,15,14,13,25,12,35,23,34,45,11};
F6={01,16,15,14,13,25,12,35,23,34,45,56,11};
F7={01,17,16,15,14,27,13,25,37,12,47,35,23,57,34,45,56,67,11};
F8={01,18,17,16,15,14,27,13,38,25,37,12,47,35,58,23,57,34,45,56,67,78,11}.

Свойства


 Если $p_1/q_1

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


 Алгоритм генерации всех дробей Fn очень прост, как в возрастающем, так и в убывающем порядке. Каждая итерация алгоритма строит следующую дробь на основе двух предыдущих. Таким образом, если ab и cd — две уже построенные дроби, а pq — следующая неизвестная, то выполняется cd=a+pb+q. Это значит, что для некотого целого k верно kc=a+p и kd=b+q, отсюда p=kca и q=kdb. Так как pq должна быть максимально близкой к cd, то положим знаменатель максимальным из возможных, то есть kdb=n, отсюда c учётом того, что k — целое, имеем k=n+bd и
p=n+bdca

q=n+bddb

 Пример реализации на Python:
 \beginShaded \beginHighlighting[] \KeywordTokdef \NormalTokfarey( n, asc=\OtherTokTrue \NormalTok): \KeywordTokif \NormalTokasc: \NormalToka, b, c, d = \DecValTok0\NormalTok, \DecValTok1\NormalTok, \DecValTok1\NormalTok, n \KeywordTokelse\NormalTok: \NormalToka, b, c, d = \DecValTok1\NormalTok, \DecValTok1\NormalTok, n\DecValTok-1\NormalTok, n \DataTypeTokprint \StringTok"\OtherTok \KeywordTokwhile \NormalTok(asc and c <= n) or (not asc and a > \DecValTok0\NormalTok): \NormalTokk = \DataTypeTokint\NormalTok((n + b)/d) \NormalToka, b, c, d = c, d, k*c - a, k*d - b \DataTypeTokprint \StringTok"\OtherTok\endHighlighting \endShaded
 Таким образом можно построить сколь угодно большое множество всех дробей в сокращенном виде, что можно использовать, например, для решения Диофантова уравнения полным перебором в рациональных числах.

История


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