Число Эрдеша – Вудса
В теории чисел положительное целое число k называется числом Эрдеша – Вудса, если оно обладает следующим свойством: существует целое положительное число a такое, что в последовательности ( a , a + 1, …, a + k ) последовательных целых чисел каждый из элементов имеет нетривиальный общий делитель с одним из концов. Другими словами, k является числом Эрдеша–Вудса, если существует целое положительное число a такое, что для каждого целого числа i между 0 и k есть хотя бы один из наибольших общих делителей gcd( a , a + i ) или gcd( a + я , а + k ) больше 1 .
Примеры
[ редактировать ]16 — это число Эрдеша-Вудса, потому что каждое из 15 чисел между 2184 и 2200 = 2184 + 16 имеет общий простой делитель с одним из 2184 = 2. 3 · 3 · 7 · 13 и 2200 = 2 2 · 5 2 · 11. Эти 15 чисел и их общие простые множители:
| 2185 5 |
2186 2 |
2187 3 |
2188 2 |
2189 11 |
| 2190 2, 3, 5 |
2191 7 |
2192 2 |
2193 3 |
2194 2 |
| 2195 5 |
2196 2, 3 |
2197 13 |
2198 2, 7 |
2199 3 |
Первые числа Эрдеша – Вудса:
Хотя все эти исходные числа четные, существуют и нечетные числа Эрдеша – Вудса. Они включают в себя
Основные разделы
[ редактировать ]Числа Эрдеша-Вудса можно охарактеризовать с точки зрения определенных разбиений простых чисел . Число k является числом Эрдеша–Вудса тогда и только тогда, когда простые числа меньше k можно разделить на два подмножества X и Y со следующим свойством: для каждой пары натуральных чисел x и y с x + y = k либо x делится на простое число в или y делится на простое число в Y. X По этой причине эти числа еще называют числами, разделяемыми на простые числа . [ 1 ]
Например, 16 делится на простые числа с X = {3, 7, 13 } и Y = {2, 5, 11 }. [ 2 ] Представления числа 16 в виде x + y и соответствующие простые делители в X и Y :
| 1 + 15 5 | и |
2 + 14 2 | и |
3 + 13 3 | х |
4 + 12 2 | и |
5 + 11 11 | и |
| 6 + 10 3 | х 2, 5 | и |
7 + 9 7 | х |
8 + 8 2 | и |
9 + 7 3 | х |
10 + 6 2 | и |
| 11 + 5 5 | и |
12 + 4 3 | х 2 | и |
13 + 3 13 | х |
14 + 2 7 | х 2 | и |
15 + 1 3 | х |
История
[ редактировать ]В статье 1971 года Пол Эрдеш и Джон Селфридж рассмотрели интервалы целых чисел, содержащие элемент, взаимно простой с обеими конечными точками. Они заметили, что более ранние результаты С. С. Пиллаи и Джорджа Секереса подразумевали, что такой элемент существует для каждого интервала, состоящего не более чем из 16 целых чисел; таким образом, ни одно число Эрдеша – Вудса не может быть меньше 16. [ 3 ] В своей диссертации 1981 года Алан Р. Вудс независимо выдвинул гипотезу. [ 4 ] что всякий раз, когда k > 1 , интервал [ a , a + k ] всегда включает число, взаимно простое с обеими конечными точками. Лишь позже он нашел первый контрпример, [2184, 2185, …, 2200] с k = 16 . Существование этого контрпримера показывает, что 16 — это число Эрдеша–Вудса. [ 5 ] Доу (1989) доказал, что существует бесконечно много чисел Эрдеша – Вудса: [ 5 ] и Цегельски, Эру и Ришар (2003) показали, что набор чисел Эрдеша – Вудса рекурсивен . [ 6 ]
Между тем, числа, которые можно разделить на простые числа, были определены Хольштыньским и Штрубе в 1978 году: [ 2 ] после чего Эрдеш и Уильям Т. Троттер в 1978 году доказали, что они образуют бесконечную последовательность. Эрдеш и Троттер применили эти результаты для генерации пар направленных циклов которых , декартово произведение графов не содержит гамильтонов цикл , и они использовали компьютерный поиск, чтобы найти несколько нечетных чисел, разделяемых простыми числами, включая 15395 и 397197. [ 7 ] В 2014 году М. Ф. Хаслер заметил в Онлайн-энциклопедии целочисленных последовательностей , что числа, делимые простыми числами, оказались такими же, как числа Эрдеша – Вудса, и это было доказано в том же году Кристофером Хантом Грибблом. [ 1 ] Та же эквивалентность была также продемонстрирована Хаслером и Матаром в 2015 году вместе с эквивалентностью между двумя определениями чисел, разделяемых простыми числами, из двух более ранних работ по этой теме. [ 8 ]
Ссылки
[ редактировать ]- ^ Перейти обратно: а б Слоан, Нью-Джерси (ред.). «Последовательность A059756» . Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.
- ^ Перейти обратно: а б Холштыньский, В.; Штрубе, РСЕ (1978). «Пути и схемы в конечных группах». Дискретная математика . 22 (3): 263–272. дои : 10.1016/0012-365X(78)90059-6 . МР 0522721 . См. исправление к списку чисел, разделяемых простыми числами, в Hasler & Mathar (2015) .
- ^ Эрдеш, П .; Селфридж, Дж.Л. (1971). «Полные простые подмножества последовательных целых чисел» (PDF) . Материалы Манитобской конференции по числовой математике (Университет Манитобы, Виннипег, Манипулятор, 1971) . Виннипег, Манитоба: Университет Манитобы. стр. 1–14. МР 0337828 . См. стр. 10.
- ^ Вудс, Алан Р. (1981). Некоторые проблемы логики и теории чисел и их связи (PDF) (доктор философии). Университет Манчестера. п. 88. Архивировано из оригинала (PDF) 8 июня 2019 г.
- ^ Перейти обратно: а б Доу, Дэвид Л. (1989). «О существовании последовательностей взаимно простых пар целых чисел» . Журнал Австралийского математического общества . 47 : 84–89. дои : 10.1017/S1446788700031220 .
- ^ Цегельски, Патрик; Эру, Франсуа; Ричард, Денис (2003). «Об амплитуде интервалов натуральных чисел, каждый элемент которых имеет общий простой делитель хотя бы с концом» . Теоретическая информатика . 303 (1): 53–62. дои : 10.1016/S0304-3975(02)00444-9 .
- ^ Троттер, Уильям Т. младший ; Эрдеш, Пол (1978). «Когда декартово произведение направленных циклов является гамильтоновым» (PDF) . Журнал теории графов . 2 (2): 137–142. дои : 10.1002/jgt.3190020206 . МР 0493392 . См. исправление к списку чисел, разделяемых простыми числами, в Hasler & Mathar (2015) .
- ^ Хаслер, Максимилиан Ф.; Матар, Ричард Дж. (27 октября 2015 г.). «Исправление к «Пути и схемы в конечных группах», Discr. Math. 22 (1978) 263». arXiv : 1510.07997 [ math.NT ].
Внешние ссылки
[ редактировать ]- Последовательность OEIS A059757 (начальные члены наименьших интервалов Эрдоса-Вудса)
- Числа Эрдеша-Вудса , Numberphile , 30 июня 2024 г.
Классы натуральных чисел |
|---|
