В теории чисел , А положительное целое число K называется быть число Эрдеша-Вудс , если он обладает следующим свойством: существует натуральное число таким образом, что в последовательности ( , + 1, ..., + K ) последовательных целыми числами, каждый из элементов имеет нетривиальный общий делитель с одной из конечных точек. Другими словами, k является числом Эрдеша – Вудса, если существует положительное целое число a такое, что для каждого целого числа i от 0 до k , хотя бы один из наибольших общих делителей gcd ( a , a + i ) или gcd ( a + i , a + k ) больше 1 .
Примеры
Первые числа Эрдеша – Вудса следующие:
История
Исследование таких чисел было основано на следующей гипотезе Пола Эрдеша :
- Существует натуральное число k такое, что каждое целое число a однозначно определяется списком простых делителей чисел a , a + 1,…, a + k .
Алан Р. Вудс исследовал этот вопрос в своей диссертации 1981 года. Вудс предположил [1], что всякий раз, когда k > 1 , интервал [ a , a + k ] всегда включает число, взаимно простое с обеими конечными точками. Лишь позже он нашел первый контрпример [2184, 2185,…, 2200] с k = 16 . Существование этого контрпримера показывает, что 16 - это число Эрдеша – Вудса.
Доу (1989) доказал, что существует бесконечно много чисел Эрдеша – Вудса, [2] и Сегельски, Херулт и Ричард (2003) показали, что набор чисел Эрдеша – Вудса рекурсивен . [3]
Рекомендации
- ^ Алан Л. Вудс, Некоторые проблемы логики и теории чисел, и их связи. Кандидат наук. диссертация, Манчестерский университет, 1981 г. Доступно в Интернете по адресу http://school.maths.uwa.edu.au/~woods/thesis/WoodsPhDThesis.pdf (по состоянию на июль 2012 г.)
- ^ Доу, Дэвид Л. (1989), "О существовании последовательностей пар целых чисел, совпадающих с простыми числами", J. Austral. Математика. Soc. Сер. А , 47 : 84–89, DOI : 10.1017 / S1446788700031220.
- ^ Сегельски, Патрик; Эру, Франсуа; Ричард, Денис (2003), «Об амплитуде интервалов натуральных чисел, каждый элемент которых имеет общий простой делитель, по крайней мере, с концом», Теоретическая информатика , 303 (1): 53–62, doi : 10.1016 / S0304- 3975 (02) 00444-9.