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.
16 is an Erdős–Woods number because the 15 numbers between 2184 and 2200 = 2184 + 16 each share a prime factor with one of 2184 = 23 · 3 · 7 · 13 and
2200 = 22 · 52 · 11. These 15 numbers and their shared prime factor(s) are:
 ;templatestyles src="Block indent/styles.css"/ ;
The first Erdős–Woods numbers are
 ;templatestyles src="Block indent/styles.css"/ ;
Although all of these initial numbers are even, odd Erdős–Woods numbers also exist. They include
 ;templatestyles src="Block indent/styles.css"/ ;
Prime partitions.
The Erdős–Woods numbers can be characterized in terms of certain partitions of the prime numbers. A number k is an Erdős–Woods number if and only if the prime numbers less than k can be partitioned into two subsets X and Y with the following property: for every pair of positive integers x and y with "x" + "y" = "k", either x is divisible by a prime in X, or y is divisible by a prime in Y. For this reason, these numbers are also called "prime-partitionable numbers".
For instance, 16 is prime-partitionable with "X" = {3, 7, 13} and "Y" = {2, 5, 11}. The representations of 16 as "x" + "y" and corresponding prime divisors in X and Y are:
 ;templatestyles src="Block indent/styles.css"/ ;
History.
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 "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. 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.
References.
 ;templatestyles src="Reflist/styles.css" / ;