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

(перенаправлено с «Число Эрдёша — Вуда»)

В теории чисел числом Эрдёша — Вудса называется всякое положительное число 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.