In number theory, a positive integer is said to be an Erdős–Woods number if it has the following property:there exists a positive integer such that in the sequence of consecutive integers, each of the elements has a non-trivial common factor with one of the endpoints. In other words, is an Erdős–Woods number if there exists a positive integer such that for each integer between and, at least one of the greatest common divisors or is greater than .
16 is an Erdős–Woods number because the 15 numbers between 2184 and each share a prime factor with one of and These 15 numbers and their shared prime factor(s) are:
The first Erdős–Woods numbers areAlthough all of these initial numbers are even, odd Erdős–Woods numbers also exist. They include
The Erdős–Woods numbers can be characterized in terms of certain partitions of the prime numbers. A number is an Erdős–Woods number if and only if the prime numbers less than can be partitioned into two subsets and with the following property: for every pair of positive integers and with, either is divisible by a prime in, or is divisible by a prime in . For this reason, these numbers are also called prime-partitionable numbers.
For instance, 16 is prime-partitionable with and . The representations of 16 as and corresponding prime divisors in and are:
In a 1971 paper, Paul Erdős and John Selfridge considered intervals of integers containing an element coprime to both endpoints. They observed that earlier results of S. S. Pillai and George Szekeres implied that such an element exists for every interval of at most 16 integers; thus, no Erdős–Woods number can be less than 16. In his 1981 thesis, Alan R. Woods independently conjectured that whenever, the interval always includes a number coprime to both endpoints. It was only later that he found the first counterexample,, with . The existence of this counterexample shows that 16 is an Erdős–Woods number. proved that there are infinitely many Erdős–Woods numbers, and showed that the set of Erdős–Woods numbers is recursive.
Meanwhile, the prime-partitionable numbers had been defined by Holsztyński and Strube in 1978, following which Erdős and William T. Trotter proved in 1978 that they form an infinite sequence. Erdős and Trotter applied these results to generate pairs of directed cycles whose Cartesian product of graphs does not contain a Hamiltonian cycle, and they used a computer search to find several odd prime-partitionable numbers, including 15395 and 397197. In 2014, M. F. Hasler observed on the On-Line Encyclopedia of Integer Sequences that the prime-partitionable numbers appeared to be the same as the Erdős–Woods numbers, and this was proven in the same year by Christopher Hunt Gribble. The same equivalence was also shown by Hasler and Mathar in 2015, together with an equivalence between two definitions of the prime-partitionable numbers from the two earlier works on the subject.