Дроби Фарея

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

Определение

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

$F_n\stackrel{\mathrm{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\}.$

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

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

Пример

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

$F_1=\left\{\frac{0}{1},\;\frac{1}{1}\right\};$

$F_2=\left\{\frac{0}{1},\;\frac{1}{2},\;\frac{1}{1}\right\};$

$F_3=\left\{\frac{0}{1},\;\frac{1}{3},\;\frac{1}{2},\;\frac{2}{3},\;\frac{1}{1}\right\};$

$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\};$

$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\};$

$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\};$

$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\};$

$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\}.$

Свойства

Если p1 / q1 < p2 / q2 — две соседние дроби в ряде Фарея, тогда q1p2 − q2p1 = 1.

Доказательство. Заметим, что треугольник на плоскости с вершинами $A=(0,\;0)$, $B=(p_1,\;q_1)$ и $C=(p_2,\;q_2)$ не может содержать целых точек, отличных от вершин. Иначе, если целая точка $(r,\;s)$ содержится в $\triangle ABC$, то дробь r / s лежит между p₁ / q₁ и p₂ / q₂, а знаменатель s не превосходит $\max\{q_1,\;q_2\}$. Значит, по формуле Пика, его площадь равна 1 / 2. С другой стороны, площадь $\triangle ABC$ равна (q₁p₂ − q₂p₁) / 2. Ч. т. д.

История

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

См. также

• Дерево Штерна — Броко

Ссылки

• Кноп К. Недвоичная система, Домашний компьютер, № 8 (2001).
• Weisstein, Eric W. Farey Sequence на сайте Wolfram MathWorld.(англ.)
• Числители и знаменатели рядов Фарея: последовательность A006842 в OEIS и последовательность A006843 в OEIS.