WikiDer > Последовательность Фари

Farey sequence
Диаграмма Фарея к F9 представлен дугами окружности. В изображение SVG, наведите указатель мыши на кривую, чтобы выделить ее и ее условия.
Диаграмма Фари к F9.
Симметричный узор, составленный знаменателями последовательности Фарея, F9.
Симметричный узор, составленный знаменателями последовательности Фарея, F25.

В математика, то Последовательность Фари порядка п это последовательность полностью уменьшенный фракции, либо от 0 до 1, либо без этого ограничения,[а] который когда в самые низкие сроки имеют знаменатели меньше или равно пв порядке увеличения размера.

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

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

Примеры

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

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 }
По центру
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 }
Отсортировано
 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}
Санберст 8.png

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

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

Фари санберст порядка 6

История

История «Фарейского сериала» очень любопытна. - Харди и Райт (1979)[3]
... еще раз, человек, чье имя было дано математическому соотношению, не был первооткрывателем, насколько это известно. - Бейлер (1964)[4]

Последовательности Фари названы в честь Британский геолог Джон Фэри, старший, чье письмо об этих последовательностях было опубликовано в Философский журнал в 1816 году. Фари предположил, не предлагая доказательства, что каждый новый член в расширении последовательности Фарея является посредственный своих соседей. Письмо Фари прочитал Коши, который представил доказательства в своем Математические упражнения, и приписал этот результат Фари. Фактически, другой математик, Чарльз Харос, опубликовал аналогичные результаты в 1802 году, которые не были известны ни Фари, ни Коши.[4] Таким образом, это историческая случайность, которая связала имя Фари с этими эпизодами. Это пример Закон Стиглера эпонимии.

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

Схема упаковки кругов Фарея 5.png
Упаковка кругов Фарея 6.png

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

Последовательность порядка Фарея п содержит все члены последовательностей Фарея низших порядков. Особенно Fп содержит всех членов Fп−1 а также содержит дополнительную дробь для каждого числа, которое меньше п и совмещать к п. Таким образом F6 состоит из F5 вместе с дробями 1/6 и 5/6.

Средний член последовательности Фарея Fп всегда 1/2, за п > 1. Исходя из этого, мы можем связать длины Fп и Fп−1 с помощью Функция Эйлера  :

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

куда это сумматорный тотент.

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

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

где µ (d) является теоретико-числовым Функция Мёбиуса, и это функция пола.

Асимптотика |Fп| является :

Индекс доли в последовательности Фарея просто позиция, что занимает в последовательности. Это особенно актуально, так как используется в альтернативной формулировке Гипотеза Римана, видеть ниже. Далее следуют различные полезные свойства:

Индекс куда и это наименьший общий множитель из первых числа , дан кем-то:[6]

Фарей соседи

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

Если а/б и c/d являются соседями в последовательности Фарея, причем а/б < c/d, то их разница c/d − а/б равно 1/bd. Это связано с тем, что каждая следующая пара рациональных чисел Фарея имеет эквивалентную площадь 1.[7]

Если r1 = p / q и r2 = p '/ q' интерпретируются как векторы (p, q) в плоскости x, y, площадь A (p / q, p '/ q') определяется как qp ' - q'p. Поскольку любая добавленная дробь между двумя предыдущими последовательными дробями последовательности Фарея рассчитывается как медианта ()

A (r1, r1⊕r2) = A (r1, r1) + A (r1, r2) = A (r1, r2) = 1 (поскольку r1 = 1/0 и r2 = 0/1, его площадь должна быть равна единице) .

С:

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

.

Таким образом 1/3 и 2/5 соседи в F5, а их разница 1/15.

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

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

Если п/q есть соседи а/б и c/d в некоторой последовательности Фарея, с

тогда п/q это посредственный из а/б и c/d - другими словами,

Это легко следует из предыдущего свойства, так как если бпводный = qcpd = 1, тогда бп + pd = qc + водный, п(б + d) = q(а + c), п/q = а + c/б + d.

Отсюда следует, что если а/б и c/d являются соседями в последовательности Фарея, то первый член, который появляется между ними при увеличении порядка последовательности Фарея, будет

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

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

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

В Стерн – Броко представляет собой структуру данных, показывающую, как последовательность строится из 0 (= 0/1) и 1 (= 1/1), взяв последовательные медианты.

Фарей-соседи и непрерывные дроби

Фракции, которые появляются как соседи в последовательности Фарея, имеют близкое родство. непрерывная дробь расширения. Каждая дробь имеет два раскрытия непрерывной дроби - в одной конечный член равен 1; в другом - последний член больше 1. Если п/q, который впервые появляется в последовательности Фарея Fq, имеет продолжение дробных разложений

[0; а1, а2, ..., ап − 1, ап, 1]
[0; а1, а2, ..., ап − 1, ап + 1]

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

[0; а1, а2, ..., ап]

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

[0; а1, а2, ..., ап − 1]

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

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

В lcm может быть выражено как произведение дробей Фарея как

куда это второй Функция Чебышева.[8][9]

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

Поскольку Функция Эйлера напрямую связан с gcd так количество элементов в Fп,

Для любых 3 дробей Фарея а/б, c/d и е/ж следующее тождество между gcdиз 2x2 детерминанты матрицы по абсолютной величине имеет:[6]

Приложения

Последовательности Фарея очень полезны для поиска рациональных приближений иррациональных чисел.[10] Например, строительство Элиаху[11] оценки снизу длины нетривиальных циклов в 3Икс+1 процесс использует последовательности Фарея для вычисления непрерывной дроби числа log2(3).

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

Последовательности Фари занимают видное место в исследованиях планирование пути под любым углом на сетках с квадратными ячейками, например, для характеристики их вычислительной сложности[14] или оптимальность.[15] Связь можно рассматривать с точки зрения р-ограниченные пути, а именно пути, состоящие из линейных сегментов, каждый из которых проходит не более ряды и самое большее столбцы ячеек. Позволять быть набором векторов такой, что , , и , взаимно просты. Позволять быть результатом отражения в соответствии . Позволять . Тогда любой р-ограниченный путь можно описать как последовательность векторов из . Между и последовательность порядка Фарея данный отображение на .

Круги Форда

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

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

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

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

Круги Форда появляются также в Аполлонийская прокладка (0,0,1,1). На рисунке ниже это показано вместе с резонансными линиями Фарея.[16]

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

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

Последовательности Фарея используются в двух эквивалентных формулировках Гипотеза Римана. Предположим, что условия находятся . Определять , другими словами разница между k-й срок пth последовательность Фарея, и k-й член набора из одинакового количества точек, равномерно распределенных на единичном интервале. В 1924 г. Жером Франель[17] доказал, что утверждение

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

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

Другие суммы с участием дробей Фарея

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

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

гипотезу Гарольда Л. Аарона в 1962 году и продемонстрировал Джин А. Блейк в 1966 году. Однострочное доказательство гипотезы Гарольда Л. Аарона выглядит следующим образом. Сумма числителей равна . Сумма знаменателей равна. Отношение первой суммы ко второй сумме равно .

Позволять бj быть упорядоченными знаменателями Fп, тогда:[19]

и

Позволять аj/бj j-я фракция Фарея в Fп, тогда

который демонстрируется в.[20] Кроме того, согласно этой ссылке, термин внутри суммы может быть выражен разными способами:

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

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

куда последовательность порядка Фарея п.

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

Следующий семестр

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

так что больше k становится, тем ближе п/q добирается до c/d.

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

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

def farey_sequence(п: int, нисходящий: bool = Ложь) -> Никто:    "" "Выведите n-ю последовательность Фарея. Допускается либо возрастание, либо убывание." ""    (а, б, c, d) = (0, 1, 1, п)    если нисходящий:        (а, c) = (1, п - 1)    Распечатать("{0}/{1}".формат(а, б))    пока (c <= п и нет нисходящий) или же (а > 0 и нисходящий):        k = (п + б) // d        (а, б, c, d) = (c, d, k * c - а, k * d - б)        Распечатать("{0}/{1}".формат(а, б))

Брутфорс ищет решения Диофантовы уравнения в рациональных числах часто можно использовать ряд Фарея (для поиска только сокращенных форм). Строки, отмеченные (*), также могут быть изменены для включения любых двух соседних терминов, чтобы генерировать термины только больше (или меньше), чем данный термин.[22]

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

Сноски

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

Рекомендации

  1. ^ Нивен, Иван М.; Цукерман, Герберт С. (1972). Введение в теорию чисел (Третье изд.). Джон Уайли и сыновья. Определение 6.1.
  2. ^ Гутери, Скотт Б. (2011). "1. Медиант". Мотив математики: история и применение медианты и последовательности Фари. Бостон: Docent Press. п. 7. ISBN 978-1-4538-1057-6. OCLC 1031694495. Получено 28 сентября 2020.
  3. ^ Харди, Г.; Райт, Э. (1979). Введение в теорию чисел (Пятое изд.). Издательство Оксфордского университета. Глава III.. ISBN 0-19-853171-0.
  4. ^ а б Бейлер, Альберт Х. (1964). Развлечение в теории чисел (Второе изд.). Дувр. Глава XVI. ISBN 0-486-21096-0. Цитируется в "Сериал Фарей. Рассказ". Разрезать узел.
  5. ^ Слоан, Н. Дж. А. (ред.). «Последовательность A005728». В Он-лайн энциклопедия целочисленных последовательностей. Фонд OEIS.
  6. ^ а б Томас, Рохелио (2018). «Частичные суммы Франеля». arXiv:1802.07792 [math.NT].
  7. ^ Остин, Дэвид (декабрь 2008 г.). «Деревья, зубы и время: математика изготовления часов». Американское математическое общество. Род-Айленд. В архиве из оригинала 4 февраля 2020 г.. Получено 28 сентября 2020.
  8. ^ Мартин, Грег (2009). «Произведение значений гамма-функции на дроби с одинаковым знаменателем». arXiv:0907.4384 [math.CA].
  9. ^ Вемайер, Стефан (2009). «НОК (1,2, ..., n) как произведение значений синуса, выбранных по точкам в последовательностях Фарея». arXiv:0909.1838 [math.CA].
  10. ^ «Аппроксимация Фарея». NRICH.maths.org. Архивировано из оригинал 19 ноября 2018 г.. Получено 18 ноября 2018.
  11. ^ Элиаху, Шалом (август 1993 г.). «Задача 3x + 1: новые нижние оценки нетривиальной длины цикла». Дискретная математика. 118 (1–3): 45–56. Дои:10.1016 / 0012-365X (93) 90052-U.
  12. ^ Zhenhua Li, A .; Хартер, У.Г. (2015). "Квантовые возрождения осцилляторов Морса и геометрии Фари-Форда". Chem. Phys. Латыш. 633: 208–213. arXiv:1308.4470. Дои:10.1016 / j.cplett.2015.05.035.
  13. ^ Томас, Р. (2014). «От последовательностей Фарея к резонансным диаграммам». Phys. Преподобный ST Accel. Балки. 17: 014001. Дои:10.1103 / PhysRevSTAB.17.014001.
  14. ^ Харабор, Даниэль Дамир; Grastien, Alban; Оз, Диндар; Аксакаллы, Вурал (26 мая 2016 г.). «Оптимальный поиск пути под любым углом на практике». Журнал исследований искусственного интеллекта. 56: 89–118. Дои:10.1613 / jair.5007.
  15. ^ Хью, Патрик Чисан (19 августа 2017 г.). «Длина кратчайших путей к вершинам в двоичных сетках размещения по сравнению с кратчайшими r-ограничениями». Журнал исследований искусственного интеллекта. 59: 543–563. Дои:10.1613 / jair.5442.
  16. ^ Томас, Рохелио (2020). «Недостатки и исправления». arXiv:2006.10661 [физика].
  17. ^ Франель, Жером (1924). "Les suites de Farey et le problème des nombres premiers". Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen. Mathematisch-Physikalische Klasse (на французском языке): 198–201.
  18. ^ Ландау, Эдмунд (1924). "Bemerkungen zu der vorstehenden Abhandlung von Herrn Franel". Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen. Mathematisch-Physikalische Klasse (на немецком языке): 202–206.
  19. ^ Курт Гирстмэр; Гирстмэр, Курт (2010). «Суммы Фарея и Дедекинды». Американский математический ежемесячник. 117 (1): 72–78. Дои:10.4169 / 000298910X475005. JSTOR 10.4169 / 000298910X475005.
  20. ^ Hall, R. R .; Шиу П. (2003). "Указатель последовательности Фарея". Michigan Math. J. 51 (1): 209–223. Дои:10.1307 / mmj / 1049832901.
  21. ^ Эдвардс, Гарольд М. (1974). «12.2 Разное. Гипотеза Римана и ряд Фарея». В Смит, Пол А.; Элленберг, Самуэль (ред.). Дзета-функция Римана. Чистая и прикладная математика. Нью-Йорк: Академическая пресса. С. 263–267. ISBN 978-0-08-087373-2. OCLC 316553016. Получено 30 сентября 2020.
  22. ^ Рутледж, Норман (март 2008 г.). «Вычислительная серия Фарея». Математический вестник. Vol. 92 нет. 523. С. 55–62.

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

внешняя ссылка