Erdős–Woods number

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 = 2³ · 3 · 7 · 13 and 2200 = 2² · 5² · 11. These 15 numbers and their shared prime factor(s) are:

2185 5	2186 2	2187 3	2188 2	2189 11
2190 2, 3, 5	2191 7	2192 2	2193 3	2194 2
2195 5	2196 2, 3	2197 13	2198 2, 7	2199 3

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

Although all of these initial numbers are even, odd Erdős–Woods numbers also exist. They include

903, 2545, 4533, 5067, 8759, 9071, 9269, 10353, 11035, 11625, 11865, 13629, 15395, ... (sequence A111042 in the OEIS).

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.^[1]

For instance, 16 is prime-partitionable with X = {3, 7, 13} and Y = {2, 5, 11}.^[2] The representations of 16 as x + y and corresponding prime divisors in X and Y are:

1 + 15 5 | y	2 + 14 2 | y	3 + 13 3 | x	4 + 12 2 | y	5 + 11 11 | y
6 + 10 3 | x 2, 5 | y	7 + 9 7 | x	8 + 8 2 | y	9 + 7 3 | x	10 + 6 2 | y
11 + 5 5 | y	12 + 4 3 | x 2 | y	13 + 3 13 | x	14 + 2 7 | x 2 | y	15 + 1 3 | x

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.^[3] In his 1981 thesis, Alan R. Woods independently conjectured^[4] 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.^[5] Dowe (1989) proved that there are infinitely many Erdős–Woods numbers,^[5] and Cégielski, Heroult & Richard (2003) showed that the set of Erdős–Woods numbers is recursive.^[6]

Meanwhile, the prime-partitionable numbers had been defined by Holsztyński and Strube in 1978,^[2] 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.^[7] 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.^[1] 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.^[8]

References

1. Sloane, N. J. A. (ed.). "Sequence A059756". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
2. Holsztyński, W.; Strube, R. F. E. (1978). "Paths and circuits in finite groups". Discrete Mathematics. 22 (3): 263–272. doi:10.1016/0012-365X(78)90059-6. MR 0522721. See correction to the list of prime-partitionable numbers in Hasler & Mathar (2015).
3. Erdős, P.; Selfridge, J. L. (1971). "Complete prime subsets of consecutive integers" (PDF). Proceedings of the Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1971). Winnipeg, Manitoba: University of Manitoba. pp. 1–14. MR 0337828. See p. 10.
4. Woods, Alan R. (1981). Some problems in logic and number theory, and their connections (PDF) (PhD). University of Manchester. p. 88. Archived from the original (PDF) on 2019-06-08.
5. Dowe, David L. (1989). "On the existence of sequences of co-prime pairs of integers". Journal of the Australian Mathematical Society. 47: 84–89. doi:10.1017/S1446788700031220.
6. 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.
7. Trotter, William T. Jr.; Erdős, Paul (1978). "When the Cartesian product of directed cycles is Hamiltonian" (PDF). Journal of Graph Theory. 2 (2): 137–142. doi:10.1002/jgt.3190020206. MR 0493392. See correction to the list of prime-partitionable numbers in Hasler & Mathar (2015).
8. Hasler, Maximilian F.; Mathar, Richard J. (27 October 2015). "Corrigendum to "Paths and circuits in finite groups", Discr. Math. 22 (1978) 263". arXiv:1510.07997 [math.NT].

External links

• OEIS sequence A059757 (Initial terms of smallest Erdos-Woods intervals)
• Erdős-Woods numbers, Numberphile, June 30, 2024