Число Эрдёша — Вудса

В теории чисел числом Эрдёша — Вудса называется всякое положительное число k, для которого существует положительное целое a такое, что в последовательности [a, a + 1, …, a + k], каждый из элементов имеет нетривиальный общий делитель с одним из её крайних элементов.

Другими словами, k — число Эрдёша — Вудса, если имеется положительное целое a, такое, что для любого целого i между 0 и k по меньшей мере один из наибольших общих делителей НОД(a, a + i) и НОД(a + i, a + k) больше единицы.

Числа Эрдёша – Вудса образуют последовательность:

16, 22, 34, 36, 46, 56, 64, 66, 70 … (последовательность A059756 в OEIS).

История

[править | править код]

Интерес к числам Эрдёша — Вудса берёт начало от гипотезы Эрдёша[1]:

Существует положительное целое k, такое, что любое целое a однозначно определяется списком различных простых делителей чисел a, a + 1, …, a + k.

Алан Вудс исследовал этот вопрос в своей диссертации в 1981 году[2], где он предположил, что каким бы ни было k > 1, интервал [a, a + k], всегда содержит число, взаимно простое с обоими концами. Несколько позднее он нашел первый контрпример, [2184, 2185, …, 2200], с k = 16.

В 1989 году Довел доказал, что имеется бесконечно много чисел Эрдёша — Вудса, и Цегильски (Cégielski), Херольт(Heroult) и Ричард (Richard) в 2003 году показали, что множество чисел Эрдёша — Вудса является перечислимым.

Примечания

[править | править код]
  1. ↑ Erdős, P. (1980), "How many pairs of products of consecutive integers have the same prime factors? (Research problem)" (PDF), American Mathematical Monthly, Архивировано (PDF) 4 апреля 2015, Дата обращения: 4 марта 2013 {{citation}}: Неизвестный параметр |p.= игнорируется (справка); Неизвестный параметр |revue= игнорируется (справка); Неизвестный параметр |vol= игнорируется (|volume= предлагается) (справка)
  2. ↑ Alan L. Woods, Some problems in logic and number theory, and their connections Архивная копия от 8 июня 2019 на Wayback Machine. Ph.D. thesis, University of Manchester, 1981.

Литература

[править | править код]
  • Patrick Cégielski; François Heroult, Denis Richard. On the amplitude of intervals of natural numbers whose every element has a common prime divisor with at least an extremity (англ.) // Theoretical Computer Science[англ.] : journal. — 2003. — Vol. 303, no. 1. — P. 53—62. — doi:10.1016/S0304-3975(02)00444-9.
  • David L. Dowe. On the existence of sequences of co-prime pairs of integers (англ.) // J. Austral. Math. Soc. : journal. — 1989. — Vol. 47. — P. 84—89. — doi:10.1017/S1446788700031220.