последовательность Фэри

Возрастающая последовательность сокращенных дробей

Диаграмма Фарея для F ₉ представлена ​​дугами окружностей. На изображении SVG наведите курсор на кривую, чтобы выделить ее и ее члены.

В математике последовательность Фарея порядка n — это последовательность полностью сокращённых дробей , либо от 0 до 1, либо без этого ограничения, ^[a] которые в наименьших членах имеют знаменатели, меньшие или равные n , расположенные в порядке увеличения размера.

При ограниченном определении каждая последовательность Фарея начинается со значения 0, обозначаемого дробью ⁠0/1⁠ , и заканчивается значением 1, обозначенным дробью ⁠1/1⁠ (хотя некоторые авторы опускают эти термины).

Последовательность Фарея иногда называют рядом Фарея , что не совсем верно, поскольку ее члены не суммируются. ^[2]

Примеры

Последовательности Фарея порядков с 1 по 8 следующие:

Ф ₁ = { ⁠0/1⁠ _, ⁠1/1⁠ }

Ф ₂ = { ⁠0/1⁠ _, ⁠1/2⁠ _, ⁠1/1⁠ }

Ф ₃ = { ⁠0/1⁠ _, ⁠1/3⁠ _, ⁠1/2⁠ _, ⁠2/3⁠ _, ⁠1/1⁠ }

Ф ₄ = { ⁠0/1⁠ _, ⁠1/4⁠ _, ⁠1/3⁠ _, ⁠1/2⁠ _, ⁠2/3⁠ _, ⁠3/4⁠ _, ⁠1/1⁠ }

Ф ₅ = { ⁠0/1⁠ _, ⁠1/5⁠ _, ⁠1/4⁠ _, ⁠1/3⁠ _, ⁠2/5⁠ _, ⁠1/2⁠ _, ⁠3/5⁠ _, ⁠2/3⁠ _, ⁠3/4⁠ _, ⁠4/5⁠ _, ⁠1/1⁠ }

Ф ₆ = { ⁠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⁠ }

Ф ₇ = { ⁠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⁠ }

Ф ₈ = { ⁠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⁠ }

Фэри Санберст

Построение графика зависимости числителей от знаменателей для F ₆

Звездные вспышки итераций 1–10 наложены друг на друга

Построение графика зависимости числителей от знаменателей последовательности Фарея дает форму, подобную той, что показана справа для F ₆ .

Отражение этой формы вокруг диагональной и главной осей создает солнечный луч Фарея , показанный ниже. Солнечный луч Фарея порядка n соединяет видимые целочисленные точки сетки из начала координат в квадрате со стороной 2 n , центрированном в начале координат. Используя теорему Пика , площадь солнечного луча равна 4(| F _n | − 1) , где | F _n | — число дробей в Fn.

Солнечные лучи Фарея порядка 6 с 1 внутренней (красной) и 96 граничными (зелеными) точками, дающие площадь 1 + ⁠96/2⁠ − 1 = 48, согласно теореме Пика

История

История «серии Фэри» весьма любопытна — Харди и Райт (1979) ^[3]

... и снова человек, чье имя было присвоено математическому соотношению, не был его первооткрывателем, насколько это известно из записей. — Бейлер (1964) ^[4]

Последовательности Фарея названы в честь британского геолога Джона Фарея-старшего , чье письмо об этих последовательностях было опубликовано в Philosophical Magazine в 1816 году. Фарей предположил, не представив доказательств, что каждый новый член в расширении последовательности Фарея является медианой своих соседей. Письмо Фарея было прочитано Коши , который предоставил доказательство в своих Exercices de mathématique и приписал этот результат Фарею. Фактически, другой математик, Чарльз Арос , опубликовал похожие результаты в 1802 году, которые не были известны ни Фарею, ни Коши. ^[4] Таким образом, это была историческая случайность, которая связала имя Фарея с этими последовательностями. Это пример закона эпонимии Стиглера .

Характеристики

Длина последовательности и индекс дроби

Последовательность Фарея порядка n содержит все элементы последовательностей Фарея более низких порядков. В частности, F _n содержит все элементы F _{n −1} и также содержит дополнительную дробь для каждого числа, которое меньше n и взаимно просто с n . Таким образом, F ₆ состоит из F ₅ вместе с дробями ⁠1/6⁠ и ⁠5/6⁠ .

Средний член последовательности Фарея F _n всегда равен ⁠1/2⁠ , для n > 1. Отсюда мы можем связать длины F _n и F _{n −1} с помощью функции Эйлера  : ${\displaystyle \varphi (n)}$

${\displaystyle |F_{n}|=|F_{n-1}|+\varphi (n).}$

Используя тот факт, что | F ₁ | = 2, мы можем вывести выражение для длины F _n : ^[5]

${\displaystyle |F_{n}|=1+\sum _{m=1}^{n}\varphi (m)=1+\Phi (n),}$

где - суммарный тотиент . ${\displaystyle \Phi (n)}$

У нас также есть:

${\displaystyle |F_{n}|={\frac {1}{2}}\left(3+\sum _{d=1}^{n}\mu (d)\left\lfloor {\tfrac {n}{d}}\right\rfloor ^{2}\right),}$

и по формуле обращения Мёбиуса  :

${\displaystyle |F_{n}|={\frac {1}{2}}(n+3)n-\sum _{d=2}^{n}|F_{\lfloor n/d\rfloor }|,}$

где μ( d ) — теоретико-числовая функция Мёбиуса , а — функция пола . ${\displaystyle \lfloor {\tfrac {n}{d}}\rfloor }$

Асимптотическое поведение | F _n | имеет вид:

${\displaystyle |F_{n}|\sim {\frac {3n^{2}}{\pi ^{2}}}.}$

Число дробей Фарея со знаменателями, равными в F _{n ,} задается выражением , когда и нулем в противном случае. Относительно числителей можно определить функцию , которая возвращает число дробей Фарея со знаменателями, равными в F _n . Эта функция обладает некоторыми интересными свойствами, такими как ^[6] ${\displaystyle k}$ ${\displaystyle \varphi (k)}$ ${\displaystyle k\leq n}$ ${\displaystyle {\mathcal {N}}_{n}(h)}$ ${\displaystyle h}$

${\displaystyle {\mathcal {N}}_{n}(1)=n}$,

${\displaystyle {\mathcal {N}}_{n}(p^{m})=\left\lceil (n-p^{m})\left(1-1/p\right)\right\rceil }$для любого простого числа , ${\displaystyle p}$

${\displaystyle {\mathcal {N}}_{n+mh}(h)={\mathcal {N}}_{n}(h)+m\varphi (h)}$ для любого целого числа , ${\displaystyle m\geq 0}$

${\displaystyle {\mathcal {N}}_{n}(4h)={\mathcal {N}}_{n}(2h)-\varphi (2h)}$.

В частности, свойство в третьей строке выше подразумевает и, далее, . Последнее означает, что для последовательностей Фарея четного порядка n число дробей с числителями, равными n/2, совпадает с числом дробей со знаменателями, равными n/2 , то есть . ${\displaystyle {\mathcal {N}}_{mh}(h)=(m-1)\varphi (h)}$ ${\displaystyle {\mathcal {N}}_{2h}(h)=\varphi (h)}$ ${\displaystyle {\mathcal {N}}_{n}(n/2)=\varphi (n/2)}$

Индекс дроби в последовательности Фарея — это просто позиция, которую она занимает в последовательности. Это имеет особое значение, поскольку используется в альтернативной формулировке гипотезы Римана , см. ниже. Далее следуют различные полезные свойства: ${\displaystyle I_{n}(a_{k,n})=k}$ ${\displaystyle a_{k,n}}$ ${\displaystyle F_{n}=\{a_{k,n}:k=0,1,\ldots ,m_{n}\}}$ ${\displaystyle a_{k,n}}$

${\displaystyle I_{n}(0/1)=0,}$

${\displaystyle I_{n}(1/n)=1,}$

${\displaystyle I_{n}(1/2)=(|F_{n}|-1)/2,}$

${\displaystyle I_{n}(1/1)=|F_{n}|-1,}$

${\displaystyle I_{n}(h/k)=|F_{n}|-1-I_{n}((k-h)/k).}$

Индекс, где и является наименьшим общим кратным первых чисел, , определяется по формуле: ^[7] ${\displaystyle 1/k}$ ${\displaystyle n/(i+1)<k\leq n/i}$ ${\displaystyle n}$ ${\displaystyle i}$ ${\displaystyle n={\rm {lcm}}([2,i])}$

${\displaystyle I_{n}(1/k)=1+n\sum _{j=1}^{i}{\frac {\varphi (j)}{j}}-k\Phi (i).}$

соседи Фэри

Дроби, являющиеся соседними членами в любой последовательности Фарея, называются парами Фарея и обладают следующими свойствами.

Если ⁠а/б⁠ и ⁠с/г⁠ являются соседями в последовательности Фарея, причем ⁠а/б⁠ < ⁠с/г⁠ , то их разность ⁠с/г⁠ − ⁠а/б⁠ равно ⁠1/бд⁠ . Так как

${\displaystyle {\frac {c}{d}}-{\frac {a}{b}}={\frac {bc-ad}{bd}},}$

это эквивалентно тому, что сказать, что

${\displaystyle bc-ad=1}$.

Таким образом ⁠1/3⁠ и ⁠2/5⁠ являются соседями в F ₅ , и их разность составляет ⁠1/15⁠ .

Обратное также верно. Если

${\displaystyle bc-ad=1}$

для положительных целых чисел a , b , c и d, где a < b и c < d, то ⁠а/б⁠ и ⁠с/г⁠ будут соседями в последовательности Фарея порядка max( b,d ).

Если ⁠п/д⁠ имеет соседей ⁠а/б⁠ и ⁠с/г⁠ в некоторой последовательности Фэри, с

${\displaystyle {\frac {a}{b}}<{\frac {p}{q}}<{\frac {c}{d}}}$

тогда ⁠п/д⁠ является медианой ⁠​а/б⁠ и ⁠с/г⁠ – другими словами,

${\displaystyle {\frac {p}{q}}={\frac {a+c}{b+d}}.}$

Это легко следует из предыдущего свойства, так как если bp – aq = qc – pd = 1 , то bp + pd = qc + aq , p ( b + d ) = q ( a + c ) , ⁠п/д⁠ = ⁠а + с/б + г⁠ .

Из этого следует, что если ⁠а/б⁠ и ⁠с/г⁠ являются соседями в последовательности Фарея, то первый член, который появляется между ними по мере увеличения порядка последовательности Фарея, равен

${\displaystyle {\frac {a+c}{b+d}},}$

который впервые появляется в последовательности Фарея порядка b + d .

Таким образом, первый член, который появляется между ⁠1/3⁠ и ⁠2/5⁠ есть ⁠3/8⁠ , который появляется в F ₈ .

Общее число пар соседей Фарея в F _n равно 2| F _n | − 3.

Дерево Штерна–Броко — это структура данных, показывающая, как строится последовательность из 0 ( = ⁠0/1⁠ ) ​​и 1 ( = ⁠1/1⁠ ) ​​, взяв последовательные медианты.

Интерпретация эквивалентной площади

Каждая последовательная пара рациональных чисел Фарея имеет эквивалентную площадь 1. ^[8] Посмотрите на это, интерпретируя последовательные рациональные числа r ₁ = p / q и r ₂ = p ′/ q ′ как векторы ( p , q ) в плоскости x–y. Площадь A ( p / q , p ′/ q ′) определяется как qp ′ − q ′ p . Поскольку любая добавленная дробь между двумя предыдущими последовательными дробями последовательности Фарея вычисляется как медиана (⊕), то A ( r ₁ , r ₁ ⊕ r ₂ ) = A ( r ₁ , r ₁ ) + A ( r ₁ , r ₂ ) = A ( r ₁ , r ₂ ) = 1 (так как r ₁ = 1/0 и r ₂ = 0/1, ее площадь должна быть равна 1).

Соседи Фарея и непрерывные дроби

Дроби, которые появляются как соседи в последовательности Фарея, имеют тесно связанные расширения непрерывной дроби . Каждая дробь имеет два расширения непрерывной дроби — в одном последний член равен 1; в другом последний член больше на 1. Если ⁠п/д⁠ , который впервые появляется в последовательности Фарея F _q , имеет разложения в непрерывные дроби

[0; а ₁ , а ₂ , ..., а _{n − 1} , а _n , 1]

[0; а ₁ , а ₂ , ..., а _{n − 1} , а _n + 1]

тогда ближайший сосед ⁠п/д⁠ в F _q (который будет его соседом с большим знаменателем) имеет расширение непрерывной дроби

[0; а ₁ , а ₂ , ..., а _н ]

а его другой сосед имеет непрерывную дробь расширения

[0; а ₁ , а ₂ , ..., а _{n − 1} ]

Например, ⁠3/8⁠ имеет два расширения непрерывной дроби [0; 2, 1, 1, 1] и [0; 2, 1, 2] , а его соседями в F ₈ являются ⁠2/5⁠ , который можно разложить как [0; 2, 1, 1] ; и ⁠1/3⁠ , который можно разложить как [0; 2, 1] .

Дроби Фарея и наименьшее общее кратное

НОК можно выразить как произведение дробей Фарея:

${\displaystyle {\text{lcm}}[1,2,...,N]=e^{\psi (N)}={\frac {1}{2}}\left(\prod _{r\in F_{N},0<r\leq 1/2}2\sin(\pi r)\right)^{2}}$

где - вторая функция Чебышева . ^{[9] [10]} ${\displaystyle \psi (N)}$

Дроби Фарея и наибольший общий делитель

Поскольку функция Эйлера напрямую связана с наибольшим общим делителем, то же самое относится и к числу элементов в F _n ,

${\displaystyle |F_{n}|=1+\sum _{m=1}^{n}\varphi (m)=1+\sum \limits _{m=1}^{n}\sum \limits _{k=1}^{m}\gcd(k,m)\cos {2\pi {\frac {k}{m}}}.}$

Для любых 3 дробей Фарея ⁠а/б⁠ , ⁠с/г⁠ и ⁠е/ф⁠ выполняется следующее тождество между наибольшими общими делителями определителей матриц 2x2 по абсолютной величине: ^[11]

${\displaystyle \gcd \left({\begin{Vmatrix}a&c\\b&d\end{Vmatrix}},{\begin{Vmatrix}a&e\\b&f\end{Vmatrix}}\right)=\gcd \left({\begin{Vmatrix}a&c\\b&d\end{Vmatrix}},{\begin{Vmatrix}c&e\\d&f\end{Vmatrix}}\right)=\gcd \left({\begin{Vmatrix}a&e\\b&f\end{Vmatrix}},{\begin{Vmatrix}c&e\\d&f\end{Vmatrix}}\right)}$

^[7]

Приложения

Последовательности Фарея очень полезны для поиска рациональных приближений иррациональных чисел. ^[12] Например, построение Элиаху ^[13] нижней границы длины нетривиальных циклов в процессе 3 x +1 использует последовательности Фарея для вычисления разложения в непрерывную дробь числа log ₂ (3).

В физических системах с резонансными явлениями последовательности Фарея обеспечивают очень элегантный и эффективный метод вычисления местоположений резонансов в 1D ^[14] и 2D ^{[15] .}

Последовательности Фарея играют важную роль в исследованиях планирования траекторий под любым углом на сетках с квадратными ячейками, например, при характеристике их вычислительной сложности ^[16] или оптимальности. ^[17] Связь можно рассматривать в терминах r -ограниченных траекторий, а именно траекторий, состоящих из отрезков прямых, каждый из которых проходит не более чем через строки и не более чем через столбцы ячеек. Пусть будет набором векторов, таких что , , и , являются взаимно простыми. Пусть будет результатом отражения относительно линии . Пусть . Тогда любой r -ограниченный траекторий можно описать как последовательность векторов из . Существует биекция между и последовательностью Фарея порядка, заданного отображением в . ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle Q}$ ${\displaystyle (q,p)}$ ${\displaystyle 1\leq q\leq r}$ ${\displaystyle 0\leq p\leq q}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle Q*}$ ${\displaystyle Q}$ ${\displaystyle y=x}$ ${\displaystyle S=\{(\pm x,\pm y):(x,y)\in Q\cup Q*\}}$ ${\displaystyle S}$ ${\displaystyle Q}$ ${\displaystyle r}$ ${\displaystyle (q,p)}$ ${\displaystyle {\tfrac {p}{q}}}$

Форд круги

Сравнение окружностей Форда и диаграммы Фарея с дугами окружностей для n от 1 до 9. Каждая дуга пересекает соответствующие ей окружности под прямым углом. На изображении SVG наведите курсор на окружность или кривую, чтобы выделить ее и ее члены.

Существует связь между последовательностью Фарея и кругами Форда .

Для каждой дроби ⁠п/д⁠ (в самом простом смысле) существует круг Форда C[ ⁠п/д⁠ ], которая представляет собой окружность с радиусом 1/(2 q ² ) и центром в ( ⁠п/д⁠ , ⁠1/ 2 к ² ⁠ ). Две окружности Форда для разных дробей либо не пересекаются , либо касаются друг друга — две окружности Форда никогда не пересекаются. Если 0 < ⁠п/д⁠ < 1, то окружности Форда, которые касаются C[ ⁠п/д⁠ ] являются в точности окружностями Форда для дробей, которые являются соседями ⁠п/д⁠ в какой-то последовательности Фэри.

Таким образом, С [ ⁠2/5⁠ ] касается C [ ⁠1/2⁠ ], С [ ⁠1/3⁠ ], С [ ⁠3/7⁠ ], С [ ⁠3/8⁠ ] и т.д.

Фордовские круги также появляются в аполлоновском уплотнении (0,0,1,1). Рисунок ниже иллюстрирует это вместе с резонансными линиями Фарея. ^[18]

Аполлоновская прокладка (0,0,1,1) и резонансная диаграмма Фарея.

гипотеза Римана

Последовательности Фарея используются в двух эквивалентных формулировках гипотезы Римана . Предположим, что члены имеют вид . Определим , другими словами, это разность между k -м членом n- й последовательности Фарея и k -м членом множества из того же числа точек, равномерно распределенных на единичном интервале. В 1924 году Жером Френель ^[19] доказал, что утверждение ${\displaystyle F_{n}}$ ${\displaystyle \{a_{k,n}:k=0,1,\ldots ,m_{n}\}}$ ${\displaystyle d_{k,n}=a_{k,n}-k/m_{n}}$ ${\displaystyle d_{k,n}}$

${\displaystyle \sum _{k=1}^{m_{n}}d_{k,n}^{2}=O(n^{r})\quad \forall r>-1}$

эквивалентно гипотезе Римана, а затем Эдмунд Ландау ^[20] заметил (сразу после статьи Френеля), что утверждение

${\displaystyle \sum _{k=1}^{m_{n}}|d_{k,n}|=O(n^{r})\quad \forall r>1/2}$

также эквивалентна гипотезе Римана.

Другие суммы, включающие дроби Фарея

Сумма всех дробей Фарея порядка n составляет половину числа элементов:

${\displaystyle \sum _{r\in F_{n}}r={\frac {1}{2}}|F_{n}|.}$

Сумма знаменателей в последовательности Фарея в два раза больше суммы числителей и связана с функцией тотиента Эйлера:

${\displaystyle \sum _{a/b\in F_{n}}b=2\sum _{a/b\in F_{n}}a=1+\sum _{i=1}^{n}i\varphi (i),}$

которая была выдвинута Гарольдом Л. Аароном в 1962 году и продемонстрирована Джин А. Блейк в 1966 году. ^[21] Однострочное доказательство гипотезы Гарольда Л. Аарона выглядит следующим образом. Сумма числителей равна . Сумма знаменателей равна . Частное от первой суммы на вторую сумму равно . ${\displaystyle {\displaystyle 1+\sum _{2\leq b\leq n}\sum _{(a,b)=1}a=1+\sum _{2\leq b\leq n}b{\frac {\varphi (b)}{2}}}}$ ${\displaystyle {\displaystyle 2+\sum _{2\leq b\leq n}\sum _{(a,b)=1}b=2+\sum _{2\leq b\leq n}b\varphi (b)}}$ ${\displaystyle {\frac {1}{2}}}$

Пусть b _j будут упорядоченными знаменателями F _n , тогда: ^[22]

${\displaystyle \sum _{j=0}^{|F_{n}|-1}{\frac {b_{j}}{b_{j+1}}}={\frac {3|F_{n}|-4}{2}}}$

и

${\displaystyle \sum _{j=0}^{|F_{n}|-1}{\frac {1}{b_{j+1}b_{j}}}=1.}$

Пусть a _j / b _{j —} j -я дробь Фарея в F _n , тогда

${\displaystyle \sum _{j=1}^{|F_{n}|-1}(a_{j-1}b_{j+1}-a_{j+1}b_{j-1})=\sum _{j=1}^{|F_{n}|-1}{\begin{Vmatrix}a_{j-1}&a_{j+1}\\b_{j-1}&b_{j+1}\end{Vmatrix}}=3(|F_{n}|-1)-2n-1,}$

что продемонстрировано в ^[23] Также согласно этой ссылке член внутри суммы может быть выражен многими различными способами:

${\displaystyle a_{j-1}b_{j+1}-a_{j+1}b_{j-1}={\frac {b_{j-1}+b_{j+1}}{b_{j}}}={\frac {a_{j-1}+a_{j+1}}{a_{j}}}=\left\lfloor {\frac {n+b_{j-1}}{b_{j}}}\right\rfloor ,}$

получая таким образом много различных сумм по элементам Фарея с тем же результатом. Используя симметрию относительно 1/2, прежнюю сумму можно ограничить половиной последовательности, как

${\displaystyle \sum _{j=1}^{\lfloor |F_{n}|/2\rfloor }(a_{j-1}b_{j+1}-a_{j+1}b_{j-1})=3(|F_{n}|-1)/2-n-\lceil n/2\rceil ,}$

Функцию Мертенса можно выразить как сумму дробей Фарея:

${\displaystyle M(n)=-1+\sum _{a\in {\mathcal {F}}_{n}}e^{2\pi ia}}$   где     — последовательность Фарея порядка n . ${\displaystyle {\mathcal {F}}_{n}}$

Эта формула используется в доказательстве теоремы Френеля–Ландау. ^[24]

Следующий срок

Существует удивительно простой алгоритм для генерации членов F _n в традиционном порядке (по возрастанию) или нетрадиционном порядке (по убыванию). Алгоритм вычисляет каждую последующую запись в терминах предыдущих двух записей, используя свойство медианы, приведенное выше. Если ⁠а/б⁠ и ⁠с/г⁠ — это две заданные записи, и ⁠п/д⁠ — неизвестная следующая запись, затем ⁠с/г⁠ = ⁠а + п/б + д⁠ . Так как ⁠с/г⁠ в низших терминах, должно быть целое число k такое, что kc = a + p и kd = b + q , что дает p = kc − a и q = kd − b . Если мы рассматриваем p и q как функции k , то

${\displaystyle {\frac {p(k)}{q(k)}}-{\frac {c}{d}}={\frac {cb-da}{d(kd-b)}}}$

поэтому чем больше k , тем ближе ⁠п/д⁠ добирается до ⁠с/г⁠ .

Чтобы получить следующий член последовательности, k должен быть как можно больше, при условии kd − b ≤ n (так как мы рассматриваем только числа со знаменателями не больше n ), поэтому k — наибольшее целое число ≤ ⁠н + б/г⁠ . Подстановка этого значения k обратно в уравнения для p и q дает

${\displaystyle p=\left\lfloor {\frac {n+b}{d}}\right\rfloor c-a}$

${\displaystyle q=\left\lfloor {\frac {n+b}{d}}\right\rfloor d-b}$

Это реализовано на Python следующим образом:

из  импорта дробей  Дробь из импорта collections.abc Генератор    def  farey_sequence ( n :  int ,  descending :  bool  =  False )  ->  Generator [ Fraction ]: """  Вывести n-ную последовательность Фарея. Разрешить как возрастание, так и убывание.  >>> print(*farey_sequence(5), sep=' ')  0 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1  """  a ,  b ,  c ,  d  =  0 ,  1 ,  1 ,  n  если  по убыванию :  a ,  c  =  1 ,  n  -  1  вывести  дробь ( a ,  b )  пока  0  <=  c  <=  n :  k  =  ( n  +  b )  //  d  a ,  b ,  c ,  d  =  c ,  d ,  k  *  c  -  a ,  k  *  d  -  b  вывести  дробь ( a ,  b )если  __name__  ==  "__main__" :  импортировать  doctest doctest . testmod ()

Поиск методом грубой силы решений диофантовых уравнений в рациональных числах часто может использовать ряд Фарея (для поиска только редуцированных форм). Хотя этот код использует первые два члена последовательности для инициализации a , b , c , и d , можно заменить любую пару соседних членов, чтобы исключить те, которые меньше (или больше) определенного порога. ^[25]

Смотрите также

• Модель ABACABA
• Дерево Штерн–Броко
• Функция Эйлера

Сноски

1. « Последовательность всех сокращенных дробей со знаменателями, не превышающими n, перечисленных в порядке их размера, называется последовательностью Фарея порядка n ». С комментарием: « Это определение последовательностей Фарея кажется наиболее удобным. Однако некоторые авторы предпочитают ограничивать дроби интервалом от 0 до 1 ». — Нивен и Цукерман (1972) ^[1]

Ссылки

1. Нивен, Иван М.; Цукерман, Герберт С. (1972). Введение в теорию чисел (третье изд.). John Wiley and Sons. Определение 6.1.
2. Guthery, Scott B. (2011). "1. Медианта". Мотив математики: история и применение медианты и последовательности Фарея . Бостон: Docent Press. стр. 7. ISBN 978-1-4538-1057-6. OCLC  1031694495 . Получено 28 сентября 2020 г. .
3. Харди, ГХ ; Райт, ЭМ (1979). Введение в теорию чисел (Пятое изд.). Oxford University Press. Глава III. ISBN 0-19-853171-0.
4. Beiler, Albert H. (1964). Recreations in the Theory of Numbers (Второе изд.). Дувр. Глава XVI. ISBN 0-486-21096-0.Цитируется в "Farey Series, A Story". Cut-the-Knot .
5. Sloane, N. J. A. (ред.). "Последовательность A005728". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.
6. Томас Гарсия, Рохелио (июль 2024 г.). «Дроби Фарея с равными числителями и ранг единичных дробей» (PDF) . Целые числа . 24 .
7. Tomas, Rogelio (январь 2022 г.). "Частичные суммы Френеля" (PDF) . Журнал целочисленных последовательностей . 25 (1).
8. Остин, Дэвид (декабрь 2008 г.). «Деревья, зубы и время: математика создания часов». Американское математическое общество . Род-Айленд. Архивировано из оригинала 4 февраля 2020 г. Получено 28 сентября 2020 г.
9. Мартин, Грег (2009). «Произведение значений гамма-функции в дробях с одинаковым знаменателем». arXiv : 0907.4384 [math.CA].
10. Вехмайер, Стефан (2009). «НОК(1,2,...,n) как произведение значений синуса, выбранных по точкам в последовательностях Фарея». arXiv : 0909.1838 [math.CA].
11. Томас Гарсия, Рохелио (август 2020 г.). «Равенства между наибольшими общими делителями, включающими три взаимно простые пары» (PDF) . Заметки по теории чисел и дискретной математике . 26 (3): 5–7. doi : 10.7546/nntdm.2020.26.3.5-7 . S2CID  225280271.
12. "Приближение Фэри". NRICH.maths.org . Архивировано из оригинала 19 ноября 2018 г. Получено 18 ноября 2018 г.
13. Элиаху, Шалом (август 1993 г.). «Проблема 3x+1: новые нижние границы нетривиальных длин циклов». Дискретная математика . 118 (1–3): 45–56. doi : 10.1016/0012-365X(93)90052-U .
14. Zhenhua Li, A.; Harter, WG (2015). «Квантовые возрождения осцилляторов Морзе и геометрии Фари–Форда». Chem. Phys. Lett . 633 : 208–213. arXiv : 1308.4470 . Bibcode : 2015CPL...633..208L. doi : 10.1016/j.cplett.2015.05.035. S2CID  66213897.
15. Томас, Р. (2014). "От последовательностей Фарея к резонансным диаграммам" (PDF) . Physical Review Специальные темы - Ускорители и пучки . 17 (1): 014001. Bibcode :2014PhRvS..17a4001T. doi : 10.1103/PhysRevSTAB.17.014001 .
16. Харабор, Дэниел Дамир; Грастиен, Альбан; Оз, Диндар; Аксакалли, Вурал (26 мая 2016 г.). «Оптимальный поиск пути под любым углом на практике». Журнал исследований искусственного интеллекта . 56 : 89–118. дои : 10.1613/jair.5007 .
17. Хью, Патрик Чисан (19 августа 2017 г.). «Длина кратчайших путей вершин в сетках двоичной занятости в сравнении с кратчайшими r-ограниченными». Журнал исследований искусственного интеллекта . 59 : 543–563. doi : 10.1613/jair.5442 .
18. Томас, Рохелио (2020). «Несовершенства и исправления». arXiv : 2006.10661 [physics.acc-ph].
19. Франель, Жером (1924). «Сюиты Фарея и проблемы премьер-министров». Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen . Mathematich-Physikalische Klasse (на французском языке): 198–201.
20. Ландау, Эдмунд (1924). «Bemerkungen zu der vorstehenden Abhandlung von Herrn Franel». Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen . Mathematich-Physikalische Klasse (на немецком языке): 202–206.
21. Блейк, Джин А. (1966). «Некоторые характерные свойства ряда Фарея». The American Mathematical Monthly . 73 (1): 50–52. doi :10.2307/2313922. JSTOR  2313922.
22. Курт Гирстмайер; Гирстмайер, Курт (2010). «Суммы Фэри и Дедекинда». The American Mathematical Monthly . 117 (1): 72–78. doi :10.4169/000298910X475005. JSTOR  10.4169/000298910X475005. S2CID  31933470.
23. Холл, Р.Р.; Шиу, П. (2003). «Индекс последовательности Фарея». Мичиганская математика. Дж . 51 (1): 209–223. дои : 10.1307/mmj/1049832901 .
24. Эдвардс, Гарольд М. (1974). "12.2 Miscellany. The Riemann Hypothesis and Farey Series" . В Смит, Пол А. ; Элленберг, Сэмюэл (ред.). Дзета-функция Римана . Чистая и прикладная математика. Нью-Йорк: Academic Press . стр. 263–267. ISBN 978-0-08-087373-2. OCLC  316553016 . Получено 30 сентября 2020 г. .
25. Routledge, Norman (март 2008). «Вычислительная серия Фарея». The Mathematical Gazette . Т. 92, № 523. С. 55–62.

Дальнейшее чтение

• Хэтчер, Аллен (2022), Топология чисел , Провиденс, Род-Айленд: Американское математическое общество , ISBN 978-1470456115
• Грэм, Рональд Л.; Кнут , Дональд Э .; Паташник, Орен (1989). Конкретная математика: основа компьютерной науки (2-е изд.). Бостон, Массачусетс: Addison-Wesley. стр. 115–123, 133–139, 150, 462–463, 523–524. ISBN 0-201-55802-5.— в частности, см. §4.5 (стр. 115–123), Бонусная задача 4.61 (стр. 150, 523–524), §4.9 (стр. 133–139), §9.3, Задача 9.3.6 (стр. 462–463).
• Вепстас, Линас. «Вопросительный знак Минковского, GL(2,Z) и модулярная группа» (PDF) .— рассматривает изоморфизмы дерева Штерна-Броко.
• Вепстас, Линас. «Симметрии отображений удвоения периода» (PDF) .— рассматривает связи между дробями Фэри и фракталами.
• Кобели, Кристиан; Захареску, Александру (2003). «Последовательность Хароса–Фарея в двести лет. Обзор». Acta Univ. Apulensis Math. Inform. (5): 1–38. «Стр. 1–20» (PDF) . Акта Univ. Апуленсис . «Стр. 21–38» (PDF) . Акта Univ. Апуленсис .
• Матвеев, Андрей О. (2017). Последовательности Фарея: дуальность и отображения между подпоследовательностями . Берлин, Германия: De Gruyter. ISBN 978-3-11-054662-0.Опечатки + Код

Внешние ссылки

• Хэтчер, Аллен. «Топология чисел» (PDF) .Электронная копия книги
• Богомольный, Александр . "Серия Фэри". Cut-the-Knot .
• Богомольный, Александр . "Дерево Штерн-Броко". Cut-the-Knot .
• Пеннестри, Этторе. «Таблица Броко с основанием 120».
• «Серия Фэри», Энциклопедия математики , EMS Press , 2001 [1994]
• Вайсштейн, Эрик В. «Дерево Штерна-Броко». MathWorld .
• Последовательность OEIS A005728 (Число дробей в ряду Фарея порядка n)
• Последовательность OEIS A006842 (Числители ряда Фарея порядка n)
• Последовательность OEIS A006843 (Знаменатели ряда Фарея порядка n)
• Архивировано в Ghostarchive и Wayback Machine: Bonahon, Francis . Funny Fractions and Ford Circles (видео). Brady Haran . Получено 9 июня 2015 г. – через YouTube.