Показать меню

Ряд Фарея

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

Определение

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

F n = def { a i b i : 0 ⩽ a i ⩽ b i ⩽ n ,   gcd ( a i , b i ) = 1 ,   a i b i < a i + 1 b i + 1 } . {displaystyle F_{n}{stackrel { ext{def}}{=}}left{{frac {a_{i}}{b_{i}}}:0leqslant 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}}} ight}.}

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

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

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

    F 1 = { 0 1 , 1 1 } ; {displaystyle F_{1}=left{{frac {0}{1}},;{frac {1}{1}} ight};} F 2 = { 0 1 , 1 2 , 1 1 } ; {displaystyle F_{2}=left{{frac {0}{1}},;{frac {1}{2}},;{frac {1}{1}} ight};} F 3 = { 0 1 , 1 3 , 1 2 , 2 3 , 1 1 } ; {displaystyle F_{3}=left{{frac {0}{1}},;{frac {1}{3}},;{frac {1}{2}},;{frac {2}{3}},;{frac {1}{1}} ight};} F 4 = { 0 1 , 1 4 , 1 3 , 1 2 , 2 3 , 3 4 , 1 1 } ; {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}} ight};} F 5 = { 0 1 , 1 5 , 1 4 , 1 3 , 2 5 , 1 2 , 3 5 , 2 3 , 3 4 , 4 5 , 1 1 } ; {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}} ight};} F 6 = { 0 1 , 1 6 , 1 5 , 1 4 , 1 3 , 2 5 , 1 2 , 3 5 , 2 3 , 3 4 , 4 5 , 5 6 , 1 1 } ; {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}} ight};} F 7 = { 0 1 , 1 7 , 1 6 , 1 5 , 1 4 , 2 7 , 1 3 , 2 5 , 3 7 , 1 2 , 4 7 , 3 5 , 2 3 , 5 7 , 3 4 , 4 5 , 5 6 , 6 7 , 1 1 } ; {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}} ight};} F 8 = { 0 1 , 1 8 , 1 7 , 1 6 , 1 5 , 1 4 , 2 7 , 1 3 , 3 8 , 2 5 , 3 7 , 1 2 , 4 7 , 3 5 , 5 8 , 2 3 , 5 7 , 3 4 , 4 5 , 5 6 , 6 7 , 7 8 , 1 1 } . {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}} ight}.}

    Свойства

    Доказательство.

    Заметим, что треугольник на плоскости с вершинами A = ( 0 , 0 ) {displaystyle A=(0,;0)} , B = ( p 1 , q 1 ) {displaystyle B=(p_{1},;q_{1})} и C = ( p 2 , q 2 ) {displaystyle C=(p_{2},;q_{2})} не может содержать целых точек, отличных от вершин. Иначе, если целая точка ( r , s ) {displaystyle (r,;s)} содержится в △ A B C {displaystyle riangle ABC} , то дробь r / s {displaystyle r/s} лежит между p 1 / q 1 {displaystyle p_{1}/q_{1}} и p 2 / q 2 {displaystyle p_{2}/q_{2}} , а знаменатель s {displaystyle s} не превосходит max { q 1 , q 2 } {displaystyle max{q_{1},;q_{2}}} . Значит, по формуле Пика, его площадь равна 1 / 2 {displaystyle 1/2} . С другой стороны, площадь △ A B C {displaystyle riangle ABC} равна ( q 1 p 2 − q 2 p 1 ) / 2 {displaystyle (q_{1}p_{2}-q_{2}p_{1})/2} . Ч. т. д.

    Справедливо и обратное утверждение: если дроби p 1 / q 1 < p 2 / q 2 {displaystyle p_{1}/q_{1}<p_{2}/q_{2}} таковы, что q 1 p 2 − q 2 p 1 = 1 {displaystyle q_{1}p_{2}-q_{2}p_{1}=1} , то они представляют собой соседние члены ряда Фарея F max { q 1 , q 2 } {displaystyle F_{max{q_{1},q_{2}}}} .

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

    Алгоритм генерации всех дробей Fn очень прост, как в возрастающем, так и в убывающем порядке. Каждая итерация алгоритма строит следующую дробь на основе двух предыдущих. Таким образом, если a b {displaystyle {frac {a}{b}}} и c d {displaystyle {frac {c}{d}}} — две уже построенные дроби, а p q {displaystyle {frac {p}{q}}} — следующая неизвестная, то выполняется c d = a + p b + q {displaystyle {frac {c}{d}}={frac {a+p}{b+q}}} . Это значит, что для некоторого целого k {displaystyle k} верно k c = a + p {displaystyle kc=a+p} и k d = b + q {displaystyle kd=b+q} , отсюда p = k c − a {displaystyle p=kc-a} и q = k d − b {displaystyle q=kd-b} . Так как p q {displaystyle {frac {p}{q}}} должна быть максимально близкой к c d {displaystyle {frac {c}{d}}} , то положим знаменатель максимальным из возможных, то есть k d − b = n {displaystyle kd-b=n} , отсюда c учётом того, что k {displaystyle k} — целое, имеем k = ⌊ n + b d ⌋ {displaystyle k=lfloor {frac {n+b}{d}} floor } и

    p = ⌊ n + b d ⌋ c − a {displaystyle p=leftlfloor {frac {n+b}{d}} ight floor c-a} q = ⌊ n + b d ⌋ d − b {displaystyle q=leftlfloor {frac {n+b}{d}} ight floor d-b}

    Пример реализации на 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)

    Таким образом можно построить сколь угодно большое множество всех дробей в сокращенном виде, что можно использовать, например, для решения Диофантова уравнения полным перебором в рациональных числах.

    История

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

    Еще по этой теме:
    Цепь Каннингема
    11:22, 17 декабрь
    Цепь Каннингема
    Цепь Каннингема (цепь почти удвоенных чисел) — последовательность простых чисел определённого вида, названо в честь математика Алана Каннингема. Цепь Каннингема первого рода длины n — это
    Нётерово пространство
    01:20, 15 декабрь
    Нётерово пространство
    Нётерово пространство (по имени Эмми Нётер) — топологическое пространство X, удовлетворяющее условию обрыва убывающих цепей замкнутых подмножеств. То есть для каждой последовательности замкнутых
    Гладкая функция
    08:57, 13 декабрь
    Гладкая функция
    Гладкая функция, или непрерывно дифференцируемая функция, — функция, имеющая непрерывную производную на всём множестве определения. Очень часто под гладкими функциями подразумевают функции, имеющие
    Максимальный тор
    12:52, 03 декабрь
    Максимальный тор
    Максимальный тор связной вещественной группы Ли G {displaystyle G} — связная компактная коммутативная подгруппа Ли T
    Вариационный ряд
    08:23, 03 декабрь
    Вариационный ряд
    Вариационный ряд (упорядоченная выборка) — последовательность X ( 1 ) ⩽
    Квадратное треугольное число
    05:27, 02 декабрь
    Квадратное треугольное число
    В теории чисел квадратным треугольным числом (или треугольным квадратным числом) называется число, являющееся как треугольным, так и квадратным. Существует бесконечное число квадратных треугольных
    Комментарии:
    Добавить комментарий
    Ваше Имя:
    Ваш E-Mail: