Ряды Фарея (также дроби Фарея, последовательность Фарея или таблица Фарея) — семейство конечных подмножеств рациональных чисел.
Определение Последовательность Фарея -го порядка представляет собой возрастающий ряд всех положительных несократимых правильных дробей, знаменатель которых меньше или равен :
Последовательность Фарея порядка можно построить из последовательности порядка по следующему правилу: Копируем все элементы последовательности порядка . Если сумма знаменателей в двух соседних дробях последовательности порядка даёт число не большее, чем , то вставляем между этими дробями их медианту, равную отношению суммы их числителей к сумме знаменателей.
Пример Последовательности Фарея для от 1 до 8:
Свойства
Если — две соседние дроби в ряде Фарея, тогда .
Справедливо и обратное утверждение: если дроби таковы, что , то они представляют собой соседние члены ряда Фарея .
Количество членов в последовательности Фарея для целого определяется следующим образом:
Здесь - функция Эйлера, - суммированная функция Эйлера. Значения являются последовательностью A005728 в OEIS.
Для функции количества членов существует асимптотическое представление: , где цифры после запятой являются последовательностью A104141 в OEIS.
Алгоритм генерации Алгоритм генерации всех дробей 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 года о приближении десятичных дробей обыкновенными дробями.
См. также Дерево Штерна — Броко Функция Минковского Окружность Форда
Ссылки
Числители и знаменатели рядов Фарея: и . Farey sequence на сайте .
Категория:Теория чисел Категория:Дроби