Erdős–Woods number

From Wikipedia, the free encyclopedia

Consider a sequence of consecutive positive integers $[a, a+1, \dots a+k]$ . The length k is an Erdős-Woods number if there exists such a sequence in which each of the elements has a common factor with one of the endpoints, i.e. if there exists a positive integer a such that for each integer i, $0 \le i \le k$ , either $gcd(a, a + i) > 1$ or $gcd(a + i, a + k) > 1$ .

The Erdős-Woods numbers are listed as (sequence A059756 in OEIS). The first few are given as

16, 22, 34, 36, 46, 56, 64, 66, 70

though arguably 0 and 1 could also be included as trivial entries. A059757 lists the starting point of the corresponding sequences.

Investigation of such numbers stemmed from a 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, \dots a+k$ .

Alan R. Woods investigated this for his 1981 thesis, and conjectured that whenever k > 1, the interval $[a, a + k]$ always included a number coprime to both endpoints. It was only later that he found the first counterexample, $[2184, 2185, \dots 2200]$ with $k = 16$ .