Ряды Фарея (также дроби Фарея, последовательность Фарея или таблица Фарея) — семейство конечных подмножеств рациональных чисел.
Определение
Последовательность Фарея
-го порядка представляет собой возрастающий ряд всех положительных несократимых правильных дробей, знаменатель которых меньше или равен
:
![{\displaystyle F_{n}{\stackrel {\text{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\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5d9d86789d222ad75c9f8cbacecd64f962e1d8d8)
Последовательность Фарея порядка
можно построить из последовательности порядка
по следующему правилу:
- Копируем все элементы последовательности порядка
.
- Если сумма знаменателей в двух соседних дробях последовательности порядка
даёт число не большее, чем
, то вставляем между этими дробями их медианту, равную отношению суммы их числителей к сумме знаменателей.
Пример
Последовательности Фарея для
от 1 до 8:
![{\displaystyle F_{1}=\left\{{\frac {0}{1}},\;{\frac {1}{1}}\right\};}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cb1e36ab4112030e54d0a6f3061bbad5c3b1e397)
![{\displaystyle F_{2}=\left\{{\frac {0}{1}},\;{\frac {1}{2}},\;{\frac {1}{1}}\right\};}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bf73ca9115a8e36f05be59a293fff5874b92162e)
![{\displaystyle F_{3}=\left\{{\frac {0}{1}},\;{\frac {1}{3}},\;{\frac {1}{2}},\;{\frac {2}{3}},\;{\frac {1}{1}}\right\};}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d6a2487d08f395137f0b3ad098181aa6ec44ae7a)
![{\displaystyle 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\};}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3af2488f570085fbe0404099e9a495191e1dbb12)
![{\displaystyle 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\};}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9af32322381a2dbc7622a29ca4129829f191e3e7)
![{\displaystyle 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\};}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dbb106c31da8711ac23cfacd668fe3e3a127325a)
![{\displaystyle 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\};}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5d893970e6a597566d6d93933724fa39c3bca0cd)
![{\displaystyle 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\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9f7657b2e536d2058327ff0b5fab69066ba6e582)
Свойства
Если — две соседние дроби в ряде Фарея, тогда .
|
Заметим, что треугольник на плоскости с вершинами
,
и
не может содержать целых точек, отличных от вершин. Иначе, если целая точка
содержится в
, то дробь
лежит между
и
, а знаменатель
не превосходит
. Значит, по формуле Пика, его площадь равна
. С другой стороны, площадь
равна
. Ч. т. д.
Справедливо и обратное утверждение: если дроби
таковы, что
, то они представляют собой соседние члены ряда Фарея
.
Алгоритм генерации
Алгоритм генерации всех дробей Fn очень прост, как в возрастающем, так и в убывающем порядке. Каждая итерация алгоритма строит следующую дробь на основе двух предыдущих. Таким образом, если
и
— две уже построенные дроби, а
— следующая неизвестная, то выполняется
. Это значит, что для некоторого целого
верно
и
, отсюда
и
. Так как
должна быть максимально близкой к
, то положим знаменатель максимальным из возможных, то есть
, отсюда c учётом того, что
— целое, имеем
и
![{\displaystyle p=\left\lfloor {\frac {n+b}{d}}\right\rfloor c-a}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a955d908901c18620a385a1032a15bc03c63b0b1)
![{\displaystyle q=\left\lfloor {\frac {n+b}{d}}\right\rfloor d-b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e6afff3db0d437f2bd14da79c958b9ea268209ef)
Пример реализации на 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 года о приближении десятичных дробей обыкновенными дробями.
См. также
Ссылки