Erdős–Woods number

Short description: Type of positive integer

In number theory, a positive integer k is said to be an Erdős–Woods number if it has the following property: there exists a positive integer a such that in the sequence (a, a + 1, …, a + k) of consecutive integers, each of the elements has a non-trivial common factor with one of the endpoints. In other words, k is an Erdős–Woods number if there exists a positive integer a such that for each integer i between 0 and k, at least one of the greatest common divisors gcd(a, a + i) or gcd(a + i, a + k) is greater than 1.

Examples

The first Erdős–Woods numbers are

16, 22, 34, 36, 46, 56, 64, 66, 70, 76, 78, 86, 88, 92, 94, 96, 100, 106, 112, 116 … (sequence A059756 in the OEIS).

History

Investigation of such numbers stemmed from the following prior conjecture by Paul Erdős:

There exists a positive integer k such that every integer a is uniquely determined by the list of prime divisors of a, a + 1, …, a + k.

Alan R. Woods investigated this question for his 1981 thesis. Woods conjectured that whenever k > 1, the interval [a, a + k] always includes a number coprime to both endpoints. It was only later that he found the first counterexample, [2184, 2185, …, 2200], with k = 16. The existence of this counterexample shows that 16 is an Erdős–Woods number.

(Dowe 1989) proved that there are infinitely many Erdős–Woods numbers, and (Cégielski Heroult) showed that the set of Erdős–Woods numbers is recursive.

External links

• OEIS sequence A059757 (Initial terms of smallest Erdos-Woods intervals)