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 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) and gcd(a + i, a + k) is greater than 1.
The first few Erdős–Woods numbers are
(Arguably 0 and 1 could also be included as trivial entries.)
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.
Dowe (1989) proved that there are infinitely many Erdős–Woods numbers, and Cégielski, Heroult & Richard (2003) showed that the set of Erdős–Woods numbers is recursive.
References
- Patrick Cégielski (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.
{{cite journal}}: Invalid|ref=harv(help); Unknown parameter|coauthors=ignored (|author=suggested) (help) - David L. Dowe (1989). "On the existence of sequences of co-prime pairs of integers". J. Austral. Math. Soc. A. 47: 84–89. doi:10.1017/S1446788700031220.
{{cite journal}}: Invalid|ref=harv(help)
External links
- ^ Alan L. Woods, Some problems in logic and number theory, and their connections. Ph.D. thesis, University of Manchester, 1981. Available online at http://school.maths.uwa.edu.au/~woods/thesis/WoodsPhDThesis.pdf (accessed July 2012)
- Sloane, N. J. A. (ed.). "Sequence A059757 (Initial terms of smallest Erdos-Woods intervals)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
 | This number theory-related article is a stub. You can help Wikipedia by expanding it. |