Перегляд вихідного коду сторінки Ряд Фарея

[[Файл:Farey diagram horizontal arc 9.svg|thumb|300px|'''Діаграма Фарея''' для послідовності <math>F_{9}</math> з використанням дуг кіл. На SVG зображені наведіть курсор на криву, щоб виділити її та її члени.]]
[[Файл:Farey diagram square 9.svg|thumb|300px|Діаграма Фарея для <math>F_{9}</math>]]
У [[математика|математиці]] '''послідовність Фарея''' порядку <math>n</math>&nbsp;— це [[послідовність]] нескоротних [[дріб|дробів]], від 0 до 1, або без цього обмеження, [[знаменник]]и яких менші або рівні <math>n</math>, а дроби розташовані в порядку зростання.

У рамках обмеженого означення кожна<ref>«Послідовність усіх нескоротних дробів зі знаменниками, що не перевищують <math>n</math>, записаних у порядку зростання, називається ''послідовністю Фарея'' порядку <math>n</math>». З коментарем: «Це означення ''послідовностей Фарея'' здається найзручнішим. Однак деякі автори вважають за краще обмежувати дроби інтервалом від 0 до 1.»&nbsp;— Нівен і Цукерман (1972).</ref> ''послідовність Фарея'' починається зі значення 0 (позначається як дріб <math>\frac{0}{1}</math>) і закінчується значенням 1 (позначається як дріб <math>\frac{1}{1}</math>), хоча деякі автори опускають ці члени.
[[Файл:Farey sequence denominators 9.svg|thumb|300px|Симетричний візерунок, утворений знаменниками послідовності Фарея <math>F_{9}</math>.]]
''Послідовність Фарея'' іноді називають [[Ряд (математика)|рядом]] Фарея, що не зовсім коректно, оскільки дроби не підсумовуються<ref>Guthery, Scott B. (2011). «1. The Mediant». A Motif of Mathematics: History and Application of the Mediant and the Farey Sequence. Boston: Docent Press. p. 7. ISBN 978-1-4538-1057-6. OCLC 1031694495. Retrieved 28 September 2020.</ref>.
[[Файл:Farey sequence denominators 25.svg|thumb|300px|Симетричний візерунок, утворений знаменниками послідовності Фарея <math>F_{25}</math>.]]
Наприклад, ряд Фарея порядку 5:
: <math>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\}.</math>

== Приклади ==
''Послідовність Фарея'' порядку від 1 до 8:
: <math>F_{1}=\left\{\frac{0}{1}, \frac{1}{1}\right\},</math>
: <math>F_{2}=\left\{\frac{0}{1}, \frac{1}{2}, \frac{1}{1}\right\},</math>
: <math>F_{3}=\left\{\frac{0}{1}, \frac{1}{3} , \frac{1}{2}, \frac{2}{3}, \frac{1}{1}\right\},</math>
: <math>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\},</math>
: <math>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\},</math>
: <math>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\},</math>
: <math>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\},</math>
: <math>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\}.</math>

{| class="toccolours" style="text-align:center; margin-top:1em"
! Відцентровані
|-
|<math>F_{1}=\left\{\frac{0}{1}, \frac{1}{1}\right\}</math>
|-
|<math>F_{2}=\left\{\frac{0}{1}, \frac{1}{2}, \frac{1}{1}\right\}</math>
|-
|<math>F_{3}=\left\{\frac{0}{1}, \frac{1}{3} , \frac{1}{2}, \frac{2}{3}, \frac{1}{1}\right\}</math>
|-
|<math>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\}</math>
|-
|<math>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\}</math>
|-
|<math>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\}</math>
|-
|<math>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\}</math>
|-
|<math>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\}</math>
|}

{| class="toccolours" style="margin-top:1em"
|-
! Відсортовані
|-
|<pre style="background:transparent; border:none; font-size:88%;">
 F1 = {0/1,                                                                                                          1/1}
 F2 = {0/1,                                                   1/2,                                                   1/1}
 F3 = {0/1,                               1/3,                1/2,                2/3,                               1/1}
 F4 = {0/1,                     1/4,      1/3,                1/2,                2/3,      3/4,                     1/1}
 F5 = {0/1,                1/5, 1/4,      1/3,      2/5,      1/2,      3/5,      2/3,      3/4, 4/5,                1/1}
 F6 = {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}
 F7 = {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}
 F8 = {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}
</pre>
|}

Графік залежності чисельника від знаменника дробів ''послідовності Фарея'' має вигляд подібний до наведеного для послідовності <math>F_{6}</math>.
Віддзеркаленя цієї фігури відносно діагоналі та координатних осей утворює ''сонячний спалах Фарея'', як показано нижче.
[[Файл:Unburst 8.png|thumb|200px]]
Сонячний спалах Фарея порядку <math>n</math> з'єднує видимі цілі точки решітки з початком координат у квадраті зі стороною <math>2n</math> і центром у початку координат.
Відповідно до [[Теорема Піка|теореми Піка]], площа сонячного спалаху Фарея дорівнює <math>4(|F_{n}|-1)</math>, де <math>|F_{n}|</math> ― кількість дробів у послідовності <math>F_{n}</math>.
[[Файл:Farey sunbursts 1-10.svg|thumb|right|200px|Ітерації 1–10]]
[[Файл:Sunburst 6.png|thumb|250px|center]]

== Історія ==
: ''Історія «рядів Фарея» дуже цікава''&nbsp;— Харді і Райт (1979)<ref>{{cite book |author1=Hardy, G.H. |author2=Wright, E.M. |year=1979 |title=An Introduction to the Theory of Numbers |edition=Fifth |publisher=Oxford University Press |isbn=0-19-853171-0 |at=[https://archive.org/details/introductiontoth00hard/page/ Chapter&nbsp;III] |url=https://archive.org/details/introductiontoth00hard/page/ }}</ref>

: ''… і знову людина, чиє ім'я було дано математичному поняттю, не була його першовідкривачем, якщо вірити записам.''&nbsp;— Бейлер (1964)<ref name=Beiler>{{cite book |author=Beiler, Albert H. |year=1964 |title=Recreations in the Theory of Numbers |url=https://archive.org/details/recreationsinthe00beil |edition=Second |publisher=Dover |isbn=0-486-21096-0 |at=Chapter&nbsp;XVI}} Cited in {{cite web |url=http://www.cut-the-knot.org/blue/FareyHistory.shtml |title=Farey Series, A Story |publisher=[[Cut-the-Knot]]}}</ref>

''Послідовність Фарея'' названа на честь [[Велика Британія|британського]] [[геолог]]а [[Джон Фарей|Джона Фарея старшого]], який 1816 року опублікував замітку про ці послідовності у ''[[Philosophical Magazine|Філософському журналі]]''. Він припустив, але без жодних доведень, що кожен новий дріб у послідовності є [[Медіанта (математика)|медіантою]] його сусідів. Замітку Фарея прочитав [[Оґюстен-Луї Коші|Коші]], який довів цю гіпотезу в своїй роботі ''Exerces de mathématique'', і приписав цей результат Фарею. Насправді, інший математик, {{нп|Чарльз Гарос||en|Charles Haros}}, ще 1802 року опублікував аналогічні результати, які не були відомі ні Фарею, ні Коші.<ref>Beiler, Albert H. (1964). Recreations in the Theory of Numbers (Second ed.). Dover. Chapter XVI. ISBN 0-486-21096-0. Cited in «Farey Series, A Story». Cut-the-Knot.</ref> Тому зв'язок Фарея з цією послідовністю просто історична випадковість. Це приклад вияву [[Закон Стіглера|закону Стіглера про епонімію]].

== Властивості ==
[[Файл:Farey diagram circle packing 4.png|thumb]]
[[Файл:Farey diagram circle packing 6.png|thumb]]

=== Довжина послідовності та індекс дробу ===
''Послідовність Фарея'' порядку <math>n</math> містить усі члени послідовностей нижчих порядків. Зокрема, послідовність <math>F_{n}</math> містить усі члени послідовності <math>F_{n-1}</math> та додаткові дроби для кожного числа, яке менше <math>n</math>, та є [[взаємно прості числа|взаємно простим]] з <math>n</math>. Таким чином, послідовність <math>F_{6}</math> складається з послідовності <math>F_{5}</math> та дробів <math>\frac{1}{6}</math> і <math>\frac{5}{6}</math>.

Середнім дробом для ''послідовності Фарея'' <math>F_{n}</math> завжди є <math>\frac{1}{2}</math>, за умови що <math>n>1</math>. Тому можемо пов'язати довжини послідовностей <math>F_{n}</math> і <math>F_{n-1}</math> за допомогою [[функція Ейлера|функції Ейлера]] <math>\varphi(n)</math>:
: <math>|F_{n}|=|F_{n-1}|+\varphi(n).</math>
Використовуючи той факт, що <math>|F_{1}|=2</math>, можна вивести співвідношення для довжини послідовності <math>F_{n}</math> :<ref>Sloane, N. J. A. (ed.). «Sequence A005728». The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.</ref>
: <math>|F_{n}|=1+\sum_{m=1}^{n}\varphi(m)=1+\Phi(n),</math>
де <math>\Phi(n)</math> ― {{нп|сумарна тотієнт функція|сумарна тотієнт функція||Totient summatory function}}.

Також довжину послідовності <math>F_{n}</math> можна знайти за формулою:
: <math>|F_{n}|=\frac{1}{2} \left(3+\sum_{d=1}^{n}\mu(d) \left\lfloor\frac{n}{d}\right\rfloor^{2}\right),</math>
або за {{нп|Формула інверсії Мебіуса|формулою інверсії Мебіуса|en|Möbius inversion formula}}:
: <math>|F_{n}|=\frac{1}{2}(n+3)n-\sum_{d=2}^{n}|F_{\lfloor\frac{n}{d}\rfloor}|,</math>
де <math>\mu(d)</math> ― теоретико-числова [[функція Мебіуса]], <math>\lfloor\tfrac{n}{d}\rfloor </math> ― [[Ціла частина числа|функція підлоги]].

Асимптотична поведінка послідовності <math>|F_{1}|</math> визначається за формулою:
: <math>|F_{n}|\sim \frac{3n^{2}}{\pi^{2}}.</math>
Індекс <math>I_n(a_{k,n})=k</math> для дробу <math>a_{k,n}</math> у ''послідовності Фарея'' <math>F_n=\{a_{k,n}\colon k = 0, 1, \ldots, m_n\}</math> це позиція, яку дріб <math>a_{k,n}</math> займає в послідовності. Поняття індекса має особливе значення, оскільки використовується в альтернативному формулюванні [[гіпотеза Рімана|гіпотези Рімана]]. Деякі корисні властивості:
: <math>I_n(0/1) = 0,</math>
: <math>I_n(1/n) = 1,</math>
: <math>I_n(1/2) = (|F_n|-1)/2,</math>
: <math>I_n(1/1) = |F_n|-1 ,</math>
: <math>I_n(h/k) = |F_n|-1-I_n((k-h)/k).</math>
Індекс дробу <math>\frac{1}{k}</math>, де <math>\frac{n}{i+1}<k\leq \frac{n}{i}</math> і <math>n</math> є [[найменше спільне кратне|найменшим спільним кратним]] перших <math>i</math> чисел, тобто <math>n={\rm lcm}([2,i]) </math>, обчислюється за формулою:<ref>Tomas, Rogelio (January 2022). «Partial Franel sums» (PDF). Journal of Integer Sequences. 25(1).</ref>
: <math>I_{n}\left(\frac{1}{k}\right)=1+n\sum_{j=1}^{i}\frac{\varphi(j)}{j}-k\Phi(i).</math>

=== Сусіди Фарея ===
Дроби, які є сусідніми в будь-якій ''послідовності Фарея'', називають ''парами Фарея'', вони мають такі властивості: Якщо <math>\frac{a}{b}</math> і <math>\frac{c}{d}</math> ― ''пара Фарея'', при чому <math>\frac{a}{b}<\frac{c}{d}</math>, то їх різниця <math>\frac{a}{b} - 
\frac{c}{d}</math> дорівнює <math>\frac{1}{bd}</math>. Це пов'язано з тим, що кожна послідовна пара раціональних чисел Фарея має еквівалентну площу 1<ref>Austin, David (December 2008). «Trees, Teeth, and Time: The mathematics of clock making». American Mathematical Society. Rhode Island. Archived from the original on 4 February 2020. Retrieved 28 September 2020.</ref>.

Якщо <math>r_{1}=\frac{p}{q}</math> і <math>r_{2}=\frac{p'}{q'}</math> розглядати як вектори <math>(p,q)</math> у площині <math>xy</math>, то площа <math>A\left(\frac{p}{q},\frac{p'}{q'}\right)</math> обчислюється як <math>qp'-q'p</math>. Оскільки будь-який дріб між двома попередніми послідовними дробами ''послідовності Фарея'' обчислюється як медіанта <math>(\oplus)</math>, то
: <math>A(r_{1},r_{1}\oplus r_{2})= A(r_{1},r_{1}+A(r_{1},r_{2}+ A(r_{1},r_{2}))=1</math>
(оскільки <math>r_{1}=1/0</math> і <math>r_{2}=0/1</math>, то його площа повинна дорівнювати одиниці).

Оскільки <math>\frac{c}{d}-\frac{a}{b}=\frac{bc-ad}{bd}</math>, то це еквівалентно умові <math>bc-ad=1</math>. Таким чином, <math>\frac{1}{3}</math> і <math>\frac{2}{5}</math> ― сусіди в послідовності <math>F_{5}</math>, і їх різниця дорівнює <math>\frac{1}{15}</math>.

Обернене також істинне. Якщо
: <math>bc-ad=1</math>
для натуральних чисел <math>a</math>, <math>b</math>, <math>c</math> і <math>d</math> та <math>a<b</math> і <math>c<d</math>, то дроби <math>\frac{a}{b}</math> і <math>\frac{c}{d}</math> ― ''пара Фарея'' порядку <math>\max(b,d)</math>.

Якщо <math>\frac{p}{q}</math> має сусідів <math>\frac{a}{b}</math> і <math>\frac{c}{d}</math> у деякій ''послідовності Фарея'', причому
: <math>\frac{a}{b} < \frac{p}{q} < \frac{c}{d} </math>,
то <math>\frac{p}{q}</math> є медіантою дробів <math>\frac{a}{b}</math> і <math>\frac{c}{d}</math>. Іншими словами:
: <math>\frac{p}{q}=\frac{a+c}{b+d}</math>.

Це легко випливає з попередньої властивості, оскільки якщо <math>bp-aq=qc-pd=1, </math> то <math>bp+pd=qc+aq</math>, <math>p(b+d)=q(a+c)</math>, <math>\frac{p}{q}=\frac{a+c}{b+d}</math>.

З цього випливає, що якщо <math>\frac{a}{b}</math> і <math>\frac{c}{d}</math> є ''парою Фарея'', то першим членом, який з'являється між ними при збільшенні порядку послідовності, буде <math>\frac{a+c}{b+d}</math>, і він же буде першим членом ''послідовності Фарея'' порядку <math>b+d</math>.

Наприклад, першим дробом, що з'являється між <math>\frac{1}{3}</math> і <math>\frac{2}{5}</math>, є <math>\frac{3}{8}</math> у послідовності <math>F_{8}</math>.

Загальна кількість ''пар Фарея'' в послідовності <math>F_{n}</math> становить <math>2F_{n}-3</math>.

[[Дерево Штерна — Броко]] ― це структура даних, яка показує побудову послідовності з 0 (= <math>\frac{0}{1}</math>) і 1 (= <math>\frac{1}{1}</math>) за допомогою послідовних медіант.

=== Сусіди Фарея та ланцюгові дроби ===
Дроби, що з'являються як сусіди в ''послідовності Фарея'' тісно пов'язані з розкладами [[ланцюгові дроби|ланцюгових дробів]]. Кожен дріб має два розклади на неперевні дроби ― один кінцевий член дорівнює 1, інший ― більший за 1. Якщо дріб <math>\frac{p}{q}</math>, який уперше з'являється в ''послідовності Фарея'' <math>F_{q}</math>, допускає розклади у вигляді ланцюгових дробів
: <math>[0,a_{1}, a_{2},\ldots, a_{n-1}, a_{n}, 1],</math>
: <math>[0,a_{1}, a_{2},\ldots, a_{n-1}, a_{n}+1],</math>
то один сусідній дріб дробу <math>\frac{p}{q}</math> (який є його сусідом із більшим знаменником) у послідовності <math>F_{q}</math> має розклад у ланцюговий дріб вигляду
: <math>[0; a_{1}, a_{2},\ldots, a_{n}],</math>
а його інший сусід має розклад у ланцюговий дріб вигляду
: <math>[0; a_{1}, a_{2},\ldots, a_{n-1}].</math>

Наприклад <math>\frac{3}{8}</math> має два розклади у вигляді ланцюгових дробів: <math>[0; 2, 1, 1, 1]</math> та <math>[0; 2, 1, 2]</math>, а його сусідами в послідовності <math>F_{8}</math> є <math>\frac{2}{5}</math>, який можна розкласти як <math>[0; 2, 1, 1]</math>, та <math>\frac{1}{3}</math>, який можна розкласти як <math>[0; 2, 1]</math>.

=== Дроби Фарея та найменше спільне кратне ===
[[Найменше спільне кратне]] можна представити у вигляді добутку дробів ''послідовності Фарея''
: <math>{\text{lcm}}[1,2,\dots ,N]=e^{\psi(N)}={\frac {1}{2}}\left(\prod _{r\in F_{N},0<r\leq 1/2}2\sin(\pi r)\right)^{2},</math>
де <math>\psi(N)</math>&nbsp;― друга {{нп|функція Чебишова||en|Chebyshev function}}<ref>Martin, Greg (2009). «A product of Gamma function values at fractions with the same denominator». arXiv:0907.4384 [math.CA].</ref><ref>Wehmeier, Stefan (2009). «The <math>{\rm LCM}(1,2,\dots ,n)</math> as a product of sine values sampled over the points in Farey sequences». arXiv:0909.1838 [math.CA].</ref>.

=== Дроби Фарея та найбільший спільний дільник ===
Оскільки [[функція Ейлера]] безпосередньо пов'язана з [[найбільший спільний дільник|найбільшим спільним дільником]], так само як і кількість елементів у <math>F_{n}</math>, то <math>|F_{n}|</math> можна обчислити за формулою:
: <math>|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}}.</math>
Для будь-яких трьох дробів ''послідовності Фарея'' <math>\frac{a}{b}</math>, <math>\frac{c}{d}</math> і <math>\frac{e}{f}</math> виконується рівність для найбільших спільних дільників абсолютних значень визначників матриць розмірності 2x2:<ref>Tomas Garcia, Rogelio (August 2020). «Equalities between greatest common divisors involving three coprime pairs» (PDF). Notes on Number Theory and Discrete Mathematics. 26 (3). doi:10.7546/nntdm.2020.26.3.5-7.</ref>,<ref>Tomas, Rogelio (January 2022). «Partial Franel sums» (PDF). Journal of Integer Sequences. 25 (1).</ref>
: <math>\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).</math>

=== Застосування ===
''Послідовності Фарея'' дуже корисні для пошуку раціональних наближень ірраціональних чисел.<ref>«Farey Approximation». NRICH.maths.org. Archived from the original on 19 November 2018. Retrieved 18 November 2018.</ref> Наприклад, побудова Еліахау<ref>Eliahou, Shalom (August 1993). «The <math>3x+1</math> problem: new lower bounds on nontrivial cycle lengths». Discrete Mathematics. 118 (1–3): 45–56. doi:10.1016/0012-365X(93)90052-U.</ref> нижньої межі довжини нетривіальних циклів у [[Гіпотеза Коллатца#Цикли|<math>3x+1</math> процесі]] використовує ''послідовності Фарея'' для обчислення розкладу в ланцюговий дріб числа <math>\log_{2}(3)</math>.

У фізичних системах із резонансними явищами ''послідовності Фарея'' забезпечують дуже простий і ефективний метод обчислення резонансних позицій для розмірностей 1<ref>Zhenhua Li, A.; Harter, W.G. (2015). «Quantum Revivals of Morse Oscillators and Farey-Ford Geometry». Chem. Phys. Lett. 633: 208—213. arXiv:1308.4470. doi:10.1016/j.cplett.2015.05.035. S2CID 66213897.</ref> та 2<ref>Tomas, R. (2014). «From Farey sequences to resonance diagrams». Physical Review Special Topics&nbsp;— Accelerators and Beams. 17: 014001. doi:10.1103/PhysRevSTAB.17.014001.</ref>.

''Послідовності Фарея'' посідають важливе місце в дослідженнях {{нп|планування шляху під будь-яким кутом||en|any-angle path planning}} на клітинках квадратів сітки, наприклад, для характеристики їх обчислювальної складності<ref name=":0">Harabor, Daniel Damir; Grastien, Alban; Öz, Dindar; Aksakalli, Vural (26 May 2016). «Optimal Any-Angle Pathfinding In Practice». Journal of Artificial Intelligence Research. 56: 89–118. doi:10.1613/jair.5007.</ref> або оптимальності<ref name=":0"/>. З'єднання можна розглядати з точки зору ''<math>r</math>-обмежених'' шляхів, а саме шляхів, які складаються з відрізків, кожен з яких перетинає максимум <math>r</math> рядків і не більше <math>r</math> стовпців клітинок. Нехай <math>Q</math> ― множина взаємнопростих векторів <math>(q,p)</math> таких, що <math> 1\leq q\leq r</math>, <math>0\leq p\leq q</math>. Нехай <math>Q*</math> ― результат відбиття множини <math>Q</math> відносно прямої <math>y=x</math>. Нехай <math> S=\{(\pm x, \pm y) \colon (x,y)\in Q\cup Q*\}.</math> Тоді будь-який <math>r</math>-обмежений шлях можна описати як послідовність векторів з <math>S</math>. Існує бієкція між множиною <math>Q</math> і ''послідовністю Фарея'' порядку <math>r</math>, заданою відображенням вектора <math>(q,p)</math> на дріб <math>\frac{p}{q}</math>.

=== Кола Форда ===
[[Файл:Comparison_Ford_circles_Farey_diagram.svg|thumb|250px|Порівняння кіл Форда і діаграми Фарея з круговими дугами для <math>n</math> від 1 до 9. Кожна дуга перетинає відповідні кола під прямим кутом. На [[Медіа:Comparison Ford circles Farey diagram.svg|svg-рисунку]] наведіть вказівник на коло чи криву, щоб виділити їх або їх елементи.]]
Існує зв'язок між ''послідовністю Фарея'' і [[Круги Форда|колами Форда]].

Для кожного дробу <math>\frac{p}{q}</math> (в його найменших термінах) існує коло Форда <math>C\left[\frac{p}{q}\right]</math> з радіусом <math>\frac{1}{2q^{2}}</math> і центром у точці <math>\left(\frac{p}{q}, \frac{1}{2q^{2}}\right)</math>. Два кола Форда для різних дробів або [[Неперетинні множини|не перетинаються]], або [[Тангенс|дотикаються]] ― кола Форда ніколи не перетинаються. Якщо <math>0<\frac{p}{q}<1</math>, то кола Форда, які дотичні до кола <math>C\left[\frac{p}{q}\right]</math> є колами Форда для дробів, які є сусідами дробу <math>\frac{p}{q}</math> в деякій ''послідовності Фарея''. Таким чином, коло <math>C\left[\frac{2}{5}\right]</math> є дотичним до кіл <math>C\left[\frac{1}{2}\right]</math>, <math>C\left[\frac{1}{3}\right]</math>, <math>C\left[\frac{3}{7}\right]</math>, <math>C\left[\frac{3}{8}\right]</math> тощо.

[[Файл:Apolloinan gasket Farey.png|650px|thumb|center|[[Сітка Аполлонія]] <math>(0,0,1,1)</math> і резонансна діаграма Фарея.]]
Кола Форда з'являються також у [[Сітка Аполлонія|сітці Аполлонія]] <math>(0,0,1,1)</math>. Рисунок нижче ілюструє це разом з резонансними лініями послідовності Фарея.<ref>Tomas, Rogelio (2020). «Imperfections and corrections». arXiv:2006.10661 [physics].</ref>

=== Гіпотеза Рімана ===
''Послідовності Фарея'' використовуються в двох формулюваннях [[гіпотеза Рімана|гіпотези Рімана]]. Нехай <math>F_{n}</math> є <math>\{{a_{k,n} \colon \ k=0,1,\ldots, m_{n}}\}.</math> Визначити <math>d_{k,n}=a_{k,n}-\frac{k}{m_{n}},</math> іншими словами <math>d_{k,n}</math> ― різниця між <math>k</math>-м членом <math>n</math>-ї ''послідовності Фарея'' і <math>k</math>-м членом множини з тією ж кількістю точок, розміщених на однаковій відстані одна від одної на одиничному інтервалі. У 1924 році {{нп|Жером Франель|Жером Франель||Jérôme Franel}}<ref>Franel, Jérôme (1924). «Les suites de Farey et le problème des nombres premiers». Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen. Mathematisch-Physikalische Klasse (in French): 198—201.</ref> довів, що твердження
: <math>\sum_{k=1}^{m_{n}}d_{k,n}^{2}=O(n^{r}), \quad \forall r>1/2,</math>
еквівалентне гіпотезі Рімана, а потім [[Едмунд Ландау]]<ref>Landau, Edmund (1924). «Bemerkungen zu der vorstehenden Abhandlung von Herrn Franel». Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen. Mathematisch-Physikalische Klasse (in German): 202—206.</ref> зауважив (відразу після статті Франеля), що твердження
: <math>\sum_{k=1}^{m_{n}}|d_{k,n}|=O(n^{r}), \quad \forall r>-1,</math>
також еквівалентне гіпотезі Рімана.

=== Інші суми з дробами Фарея ===
Сума всіх дробів ''послідовності Фарея'' порядку <math>n</math> дорівнює половині кількості елементів цієї послідовності:
: <math>\sum_{r\in F_{n}}r=\frac{1}{2}|F_{n}|.</math>
Сума знаменників у ''послідовності Фарея'' в два рази перевищує суму чисельників і може бути представлена функцією Ейлера:
: <math>\sum{\frac{a}{b}\in F_{n}}b=2\sum{\frac{a}{b}\in F_{n}}a=1+\sum_{i=1}^{n}i\varphi(i).</math>
Цю гіпотезу висунув Гарольд Л. Аарон у 1962 році, а довів Джин А. Блейк у 1966 році. Доведення в один рядок гіпотези Гарольда Л. Аарона таке. Сума чисельників дорівнює:
: <math>1+\sum_{2\leq b\leq n} \sum_{(a,b)=1}a=1+\sum_{2\leq b\leq n}b\frac{\varphi(b)}{2}.</math>
Сума знаменників дорівнює:
: <math>2+\sum_{2\leq b\leq n} \sum_{(a,b)=1}b=2+\sum_{2\leq b\leq n}b\varphi(b).</math>
Відношення першої суми до другої дорівнює <math>\frac{1}{2}</math>.

Нехай <math>b_{j}</math>&nbsp;— впорядковані знаменники послідовності <math>F_{n}</math>, тоді<ref>Kurt Girstmair; Girstmair, Kurt (2010). «Farey Sums and Dedekind Sums». The American Mathematical Monthly. 117 (1): 72-78. doi:10.4169/000298910X475005. JSTOR 10.4169/000298910X475005. S2CID 31933470.</ref>
: <math>\sum_{j=0}^{|F_{n}|-1}\frac{b_{j}}{b_{j}+1}=\frac{3|F_{n}|-4}{2},</math>
і
: <math>\sum_{j=0}^{|F_{n}|-1}\frac{1}{b_{j=1}+b_{j}}=1.</math>
Нехай <math>\frac{a_{j}}{b_{j}}</math>&nbsp;— <math>j</math>-й дріб ''послідовності Фарея'' <math>F_{n}</math>, тоді
: <math>\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,</math>
як показано в роботі Галла і Шіу<ref>Hall, R. R.; Shiu, P. (2003). «The Index of a Farey Sequence». Michigan Math. J. 51 (1): 209—223. doi:10.1307/mmj/1049832901.</ref>. Також, згідно з цією роботою, член всередині суми можна представити багатьма різними способами:
: <math>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,</math>
отримуючи таким чином багато різних сум за елементами ''послідовності Фарея'' з однаковим результатом. Використовуючи симетрію відносно <math>\frac{1}{2}</math>, суму можна обмежити половиною послідовності:
: <math>\sum_{j=1}^{|F_{n}|/2}a_{j-1}b_{j+1}-a_{j+1}b_{j-1}=3(|F_{n}|-1)/2-n-\lceil n/2\rceil.</math>

[[Функція Мертенса|Функцію Мертенса]] можна подати як суму дробів ''послідовності Фарея'' в такий спосіб:
: <math>M(n)=-1+\sum_{a\in {\mathcal F}_{n}}{\rm e}^{2\pi {\rm i}a},</math>
де <math>{\mathcal F}_{n}</math> ― ''послідовність Фарея'' порядку <math>n</math>. Ця формула використовується в доведенні теореми Франеля ― Ландау<ref>Edwards, Harold M. (1974). «12.2 Miscellany. The Riemann Hypothesis and Farey Series». In Smith, Paul A.; Ellenberg, Samuel (eds.). Riemann's Zeta Function. Pure and Applied Mathematics. New York: Academic Press. pp.~263--267. ISBN 978-0-08-087373-2. OCLC 316553016. Retrieved 30 September 2020.</ref>.

== Наступний член ==
Існує надзвичайно простий алгоритм для обчислення дробів у послідовності Фарея <math>F_{n}</math> в традиційному порядку (зростання) або нетрадиційному порядку (спадання). Алгоритм обчислює кожен наступний елемент, враховуючи попередні два і застосовуючи до них властивість [[Медіанта (математика)|медіанти]]. Якщо <math>\frac{a}{b}</math> і <math>\frac{c}{d}</math>&nbsp;— два відомі елементи, і <math>\frac{p}{q}</math> ― невідомий наступний елемент, то <math>\frac{c}{d}=\frac{a+p}{b+q}</math>. Оскільки <math>\frac{c}{d}</math> нескоротний дріб, то існує ціле число <math>k</math> таке, що <math>kc=a+p</math> і <math>kd=b+q</math>, а тому <math>p=kc-a</math> і <math>q=kd-b</math>. Якщо розглядати <math>p</math> і <math>q</math> як функції від <math>k</math>, то
: <math>\frac{p(k)}{q(k)}-\frac{c}{d}=\frac{cb-da}{d(kd-b)},</math>
тому чим більше беремо <math>k</math>, тим ближче <math>\frac{p}{q}</math> розташовується до <math>\frac{c}{d}</math>.

Щоб знайти наступний дріб у послідовності Фарея, <math>k</math> має бути якомога більшим, враховуючи що <math>kd-b\leq n</math> (оскільки розглядаємо лише числа зі знаменниками не більше <math>n</math>), то <math>k</math> ― найбільше ціле число, <math>k\leq\frac{n+b}{d}</math>. Підставляючи це значення <math>k</math> у співвідношення для <math>p</math> і <math>q</math> отримуємо:
: <math>p=\left\lfloor \frac{n+b}{d}c-a \right\rfloor,</math>
: <math>q=\left\lfloor \frac{n+b}{d}d-b \right\rfloor.</math>
Цей алгоритм можна реалізувати мовою [[Python]] так:
<syntaxhighlight lang="python">
def farey_sequence(n: int, descending: bool = False) -> None:
    """Print the n'th Farey sequence. Allow for either ascending or descending."""
    (a, b, c, d) = (0, 1, 1, n)
    if descending:
        (a, c) = (1, n - 1)
    print("{0}/{1}".format(a, b))
    while (c <= n and not descending) or (a > 0 and descending):
        k = (n + b) // d
        (a, b, c, d) = (c, d, k * c - a, k * d - b)
        print("{0}/{1}".format(a, b))
</syntaxhighlight>

Для прямого знаходження розв'язків [[Діофантові рівняння|діофантових рівнянь]] у раціональних числах часто можна використовувати ряди Фарея (для знаходження лише зведених форм). Рядки з позначкою <math>(*)</math> також можна змінити, щоб включити будь-які два суміжних члени для отримання членів лише більших (або менших) ніж заданий член<ref>Routledge, Norman (March 2008). «Computing Farey series»''. The Mathematical Gazette. Vol.~92, no. 523. pp. 55-62.</ref>.

== Див. також ==
* [[Дерево Штерна — Броко]]
* {{нп|Шаблон ABACABA||en|ABACABA pattern}}
* [[Функція Ейлера]]

== Примітки ==
{{Примітки|2}}

== Джерела ==
# Математическая энциклопедия. В пяти томах. Том 5./ Под ред. И.&nbsp;М.&nbsp;Виноградова. {{М.}}: Советская энциклопедия, 1984, с. 598

== Література ==
* {{cite web |first=Allen |last=Hatcher |url=http://pi.math.cornell.edu/~hatcher/TN/TNpage.html |title=Topology of Numbers |department=Mathematics |publisher=Cornell U. |place=Ithaca, NY}}
* {{cite book |first1=Ronald L. |last1=Graham |first2=Donald E. |last2=Knuth |first3=Oren |last3=Patashnik |title=Concrete Mathematics: A foundation for computer science |edition=2nd |publisher=Addison-Wesley |place=Boston, MA |year=1989 |isbn=0-201-55802-5 |pages=115–123, 133–139, 150, 462–463, 523–524}}&nbsp;— in particular, see §&nbsp;4.5 (pp.&nbsp;115–123), Bonus Problem&nbsp;4.61 (pp.&nbsp;150, 523—524), §&nbsp;4.9 (pp.&nbsp;133–139), §&nbsp;9.3, Problem&nbsp;9.3.6 (pp.&nbsp;462–463).
* {{cite web |first=Linas |last=Vepstas |title=The Minkowski Question Mark, GL(2,Z), and the Modular Group |url=http://linas.org/math/chap-minkowski.pdf}}&nbsp;— reviews the isomorphisms of the Stern-Brocot Tree.
* {{cite web |first=Linas |last=Vepstas |title=Symmetries of Period-Doubling Maps |url=http://linas.org/math/chap-takagi.pdf}}&nbsp;— reviews connections between Farey Fractions and Fractals.
* {{cite journal |first1=Cristian |last1=Cobeli |first2=Alexandru |last2=Zaharescu |title=The Haros-Farey sequence at two hundred years. A survey |journal=Acta Univ. Apulensis Math. Inform. |issue=5 |year=2003 |pages=1–38}} {{cite web |url=http://www.emis.de/journals/AUA/acta5/survey3.ps_pages1-20.pdf |website=Acta Univ. Apulensis |title=pp.&nbsp;1&ndash;20}} {{cite web |url=http://www.emis.de/journals/AUA/acta5/survey3.ps_pages21-38.pdf |website=Acta Univ. Apulensis |title=pp.&nbsp;21&ndash;38}}
* {{cite book |first=Andrey O. |last=Matveev |title=Farey Sequences: Duality and Maps Between Subsequences |publisher=De Gruyter |place=Berlin, DE |year=2017 |isbn=978-3-11-054662-0}}

== Посилання ==
* {{cite web |first=Alexander |last=Bogomolny |url=http://www.cut-the-knot.org/blue/Farey.shtml |title=Farey series |publisher=[[Cut-the-Knot]]}}
* {{cite web |first=Alexander |last=Bogomolny |url=http://www.cut-the-knot.org/blue/Stern.shtml |title=Stern-Brocot Tree |publisher=[[Cut-the-Knot]]}}
* {{cite web |first=Ettore |last=Pennestri |url=https://www.researchgate.net/publication/297000899 |title=A Brocot table of base&nbsp;120}}
* «Farey series», Encyclopedia of Mathematics, EMS Press, 2001 [1994]
* {{MathWorld | urlname=Stern-BrocotTree | title=Stern-Brocot Tree}}
* Число дробів у ряді Фарея порядку n&nbsp;— {{OEIS|A005728}}
* Чисельники ряду Фарея порядку n&nbsp;— {{OEIS|A006842}}
* Знаменники ряду Фарея порядку n&nbsp;— {{OEIS|A006843}}
* Archived at [https://ghostarchive.org/varchive/youtube/20211212/0hlvhQZIOQw Ghostarchive]{{cbignore}} and the [https://web.archive.org/web/20181007135618/https://www.youtube.com/watch?bpctr=9999999999&hl=en&disable_polymer=true&gl=US&v=0hlvhQZIOQw&has_verified=1 Wayback Machine]{{cbignore}}: {{cite AV media |last1=Bonahon |first1=Francis |author-link=Francis Bonahon |title=Funny Fractions and Ford Circles |url=https://www.youtube.com/watch?v=0hlvhQZIOQw |publisher=Brady Haran |access-date=9 червня 2015 |via=YouTube |medium=video}}{{cbignore}}

== Посилання ==
* {{MathWorld|FareySequence|Послідовність Фарея}}
{{Бібліоінформація}}

[[Категорія:Теорія чисел]]
[[Категорія:Дроби]]
[[Категорія:Ряди та послідовності]]