Задачи, связанные с арифметическими прогрессиями
Проблемы, связанные с арифметическими прогрессиями, представляют интерес для теории чисел . [1] комбинаторика и информатика , как с теоретической, так и с прикладной точек зрения.
Крупнейшие подмножества без прогрессирования
[ редактировать ]Найдите мощность (обозначаемую A k ( m )) наибольшего подмножества {1, 2, ..., m }, которое не содержит прогрессии из k различных членов. Элементы запрещенных прогрессий не обязаны быть последовательными. Например, A 4 (10) = 8, поскольку {1, 2, 3, 5, 6, 8, 9, 10} не имеет арифметических прогрессий длины 4, а все 9-элементные подмножества {1, 2, . .., 10} есть один.
В 1936 году Пол Эрдеш и Пал Туран задали вопрос, связанный с этим числом. [2] и Эрдеш назначил премию в 1000 долларов за ответ на него. Премия была получена Эндре Семереди за опубликованное в 1975 году решение, которое стало известно как теорема Семереди .
Арифметические прогрессии от простых чисел
[ редактировать ]Теорема Семереди утверждает, что набор натуральных чисел ненулевой верхней асимптотической плотности содержит конечные арифметические прогрессии любой произвольной длины k .
Эрдеш выдвинул более общую гипотезу , из которой следует, что
- Последовательность простых чисел содержит арифметические прогрессии любой длины.
Этот результат был доказан Беном Грином и Теренсом Тао в 2004 году и теперь известен как теорема Грина-Тао . [3]
См. также теорему Дирихле об арифметических прогрессиях .
По состоянию на 2020 год [update], самая длинная известная арифметическая прогрессия простых чисел имеет длину 27: [4]
- 224584605939537911 + 81292139·23#· n , для n = от 0 до 26. ( 23# = 223092870 )
По состоянию на 2011 год самая длинная известная арифметическая прогрессия последовательных простых чисел имеет длину 10. Она была обнаружена в 1998 году. [5] [6] Прогрессия начинается с 93-значного числа.
- 100 99697 24697 14247 63778 66555 87969 84032 95093 24689
- 19004 18036 03417 75890 43417 03348 88215 90672 29719
и имеет общую разность 210.
Простые числа в арифметических прогрессиях
[ редактировать ]Теорема о простых числах для арифметических прогрессий касается асимптотического распределения простых чисел в арифметической прогрессии.
Накрытие и разбиение на арифметические прогрессии
[ редактировать ]- Найдите минимальный l n такой, что любой набор из n вычетов по модулю p можно покрыть арифметической прогрессией длины l n . [7]
- Для заданного набора S целых чисел найдите минимальное количество арифметических прогрессий, покрывающих S
- Для заданного набора S целых чисел найдите минимальное количество непересекающихся арифметических прогрессий, покрывающих S
- Найдите количество способов разбить {1, ..., n } на арифметические прогрессии. [8]
- Найдите количество способов разбить {1, ..., n } на арифметические прогрессии длины не менее 2 с одинаковым периодом. [9]
- См. также Система покрытия.
См. также
[ редактировать ]Примечания
[ редактировать ]- ^ Сэмюэл С. Вагстафф-младший (1979). «Некоторые вопросы об арифметических прогрессиях». Американский математический ежемесячник . 86 (7). Математическая ассоциация Америки: 579–582. дои : 10.2307/2320590 . JSTOR 2320590 .
- ^ Эрдеш, Пол ; Туран, Пол (1936). «О некоторых последовательностях целых чисел» (PDF) . Журнал Лондонского математического общества . 11 (4): 261–264. дои : 10.1112/jlms/s1-11.4.261 . МР 1574918 .
- ^ Конлон, Дэвид ; Фокс, Джейкоб ; Чжао, Юфэй (2014). «Теорема Грина-Дао: изложение». EMS-обзоры по математическим наукам . 1 (2): 249–282. arXiv : 1403.2957 . дои : 10.4171/EMSS/6 . МР 3285854 . S2CID 119301206 .
- ^ Йенс Крузе Андерсен, Простые числа в записях арифметической прогрессии . Проверено 10 августа 2020 г.
- ^ Х. Дубнер; Т. Форбс; Н. Лигерос; М. Мизони; Х. Нельсон; П. Циммерманн, «Десять последовательных простых чисел в арифметической прогрессии», Math. Комп. 71 (2002), 1323–1328.
- ^ Проект девяти и десяти простых чисел
- ^ Всеволод Федорович Лев (2000). «Совместные приближения и покрытие арифметическими прогрессиями над F p » . Журнал комбинаторной теории . Серия А. 92 (2): 103–118. дои : 10.1006/jcta.1999.3034 .
- ^ Слоан, Нью-Джерси (ред.). «Последовательность A053732 (Количество способов разбить {1,...,n} на арифметические прогрессии длины >= 1)» . Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.
- ^ Слоан, Нью-Джерси (ред.). «Последовательность A072255 (Количество способов разбить {1,2,...,n} на арифметические прогрессии...)» . Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.