Задачи, связанные с арифметическими прогрессиями
Задачи, связанные с арифметическими прогрессиями, представляют интерес в теории чисел , [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 год [обновлять]самая длинная известная арифметическая прогрессия простых чисел имеет длину 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). «Некоторые вопросы об арифметических прогрессиях». American Mathematical Monthly . 86 (7). Математическая ассоциация Америки: 579–582. doi :10.2307/2320590. JSTOR 2320590.
- ^ Эрдёш, Пол ; Туран, Пол (1936). «О некоторых последовательностях целых чисел» (PDF) . Журнал Лондонского математического общества . 11 (4): 261–264. doi :10.1112/jlms/s1-11.4.261. MR 1574918.
- ^ Конлон, Дэвид ; Фокс, Джейкоб ; Чжао, Юфэй (2014). «Теорема Грина–Тао: изложение». Обзоры EMS по математическим наукам . 1 (2): 249–282. arXiv : 1403.2957 . doi :10.4171/EMSS/6. MR 3285854. S2CID 119301206.
- ^ Йенс Крузе Андерсен, Простые числа в записях арифметической прогрессии. Получено 10 августа 2020 г.
- ^ Х. Дубнер; Т. Форбс; Н. Лигерос; М. Мизони; Х. Нельсон; П. Циммерман, «Десять последовательных простых чисел в арифметической прогрессии», Math. Comp. 71 (2002), 1323–1328.
- ^ Проект «Девять и десять простых чисел»
- ^ Всеволод Ф. Лев (2000). «Одновременные приближения и покрытие арифметическими прогрессиями над Fp». Журнал комбинаторной теории . Серия A. 92 (2): 103–118. doi : 10.1006/jcta.1999.3034 .
- ^ Слоан, Н. Дж. А. (ред.). "Последовательность A053732 (Число способов разбиения {1,...,n} на арифметические прогрессии длины >= 1)". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.
- ^ Слоан, Н. Дж. А. (ред.). "Последовательность A072255 (Число способов разбиения {1,2,...,n} на арифметические прогрессии...)". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.
