Erdős–Woods number

From HandWiki
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.


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).


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[1] 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,[2] and (Cégielski Heroult) showed that the set of Erdős–Woods numbers is recursive.[3]


  1. Woods, Alan L. (1981). Some problems in logic and number theory, and their connections (PDF) (PhD). University of Manchester. Archived from the original (PDF) on 2019.
  2. Dowe, David L. (1989), "On the existence of sequences of co-prime pairs of integers", J. Austral. Math. Soc. Ser. A 47: 84–89, doi:10.1017/S1446788700031220 .
  3. Cégielski, Patrick; Heroult, François; Richard, Denis (2003). "On the amplitude of intervals of natural numbers whose every element has a common prime divisor with at least an extremity". Theoretical Computer Science 303 (1): 53–62. doi:10.1016/S0304-3975(02)00444-9. .

External links