Ряд Фарея

Материал из Википедии — свободной энциклопедии

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

Содержание

1 Определение
2 Пример
3 Свойства
4 История
5 См. также
6 Ссылки

[править] Определение

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

$F_n\stackrel{def}{=}\left\{\frac{a_i}{b_i}:\;0 \leq a_i \leq b_i \leq n,\;GCD(a_i,\;b_i)=1,\;\frac{a_i}{b_i}<\;\frac{a_{i+1}}{b_{i+1}}\right\}.$

[править] Пример

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

F₁ = {⁰⁄₁, ¹⁄₁}

F₂ = {⁰⁄₁, ¹⁄₂, ¹⁄₁}

F₃ = {⁰⁄₁, ¹⁄₃, ¹⁄₂, ²⁄₃, ¹⁄₁}

F₄ = {⁰⁄₁, ¹⁄₄, ¹⁄₃, ¹⁄₂, ²⁄₃, ³⁄₄, ¹⁄₁}

F₅ = {⁰⁄₁, ¹⁄₅, ¹⁄₄, ¹⁄₃, ²⁄₅, ¹⁄₂, ³⁄₅, ²⁄₃, ³⁄₄, ⁴⁄₅, ¹⁄₁}

F₆ = {⁰⁄₁, ¹⁄₆, ¹⁄₅, ¹⁄₄, ¹⁄₃, ²⁄₅, ¹⁄₂, ³⁄₅, ²⁄₃, ³⁄₄, ⁴⁄₅, ⁵⁄₆, ¹⁄₁}

F₇ = {⁰⁄₁, ¹⁄₇, ¹⁄₆, ¹⁄₅, ¹⁄₄, ²⁄₇, ¹⁄₃, ²⁄₅, ³⁄₇, ¹⁄₂, ⁴⁄₇, ³⁄₅, ²⁄₃, ⁵⁄₇, ³⁄₄, ⁴⁄₅, ⁵⁄₆, ⁶⁄₇, ¹⁄₁}

F₈ = {⁰⁄₁, ¹⁄₈, ¹⁄₇, ¹⁄₆, ¹⁄₅, ¹⁄₄, ²⁄₇, ¹⁄₃, ³⁄₈, ²⁄₅, ³⁄₇, ¹⁄₂, ⁴⁄₇, ³⁄₅, ⁵⁄₈, ²⁄₃, ⁵⁄₇, ³⁄₄, ⁴⁄₅, ⁵⁄₆, ⁶⁄₇, ⁷⁄₈, ¹⁄₁}

[править] Свойства

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

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

Если $p 1 / q 1 < p 2 / q 2$ две соседние дроби в ряде Фарея, тогда $q 1 p 2 - q 2 p 1 = 1$ .

Доказательство. Заметим, что треугольник на плоскости с вершинами $A=(0,\;0)$ , $B=(p_1,\;q_1)$ и $C=(p_2,\;q_2)$ не может содержать целых точек, отличных от вершин. Иначе, если целая точка $(r,\;s)$ содержится в $\triangle ABC$ , то дробь

r / s

лежит между

p 1 / q 1

p 2 / q 2

, а знаменатель

s

не превосходит $\max\{q_1,\;q_2\}$ . Значит, по формуле Пика, его площадь равна

1 / 2

. С другой стороны, площадь $\triangle ABC$ равна

(q 1 p 2 - q 2 p 1) / 2

. ч.т.д.

[править] История

Биография Фарея занимает двадцать строк словарной статьи, в которой расписаны его заслуги, как геолога. Однако та единственная работа, обессмертившая его имя, там не упомянута.

Готтфри Харди

Джон Фарей (John Farey) был геологом по образованию, его единственным вкладом в математику были дроби, названные его именем. В 1816 году была опубликована статья Фарея «On a curious property of vulgar fractions» («О интересном свойстве обыкновенных дробей»), в которой Фарей определил последовательность $F n$ и описал то самое «интересное свойство» итеративного построения последовательностей.

Эта статья Фарея дошла до Коши, который в том же году опубликовал доказательство. Интересен тот факт, что «интересное свойство» и сама последовательность, описанные Фареем в 1816 году было использовано Харосом в его статье 1802 года об аппроксимации десятичных дробей дробями обыкновенными. В вопросе авторства историки расходятся: Харди считает Хароса исходным автором последовательности, однако МакТьютор указывает на тот факт, что Харос не дал ни описания последовательности в общем виде, ни доказательства «интересного свойства».

[править] См. также

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

[править] Ссылки

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