.
Erdős–Woods number
In number theory, an Erdős–Woods number is a positive integer that has the following property:
Consider a sequence of consecutive positive integers \( [a, a+1, \dots, a+k] \). The number k is an Erdős–Woods number if there exists such a sequence, beginning with some number a, in which each of the elements has a common factor with one of the endpoints. In other words, if there exists a positive integer a such that for each integer \( i, 0 \le i \le k \), either \( \gcd(a, a+i) > 1 \) or \( \gcd(a+i, a+k) > 1 \). The first few Erdős–Woods numbers are:
16, 22, 34, 36, 46, 56, 64, 66, 70 … (sequence A059756 in OEIS).
(Arguably 0 and 1 could also be included as trivial entries.)
Investigation of such numbers stemmed from a 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, \dots, a+k \).
Alan R. Woods investigated this for his 1981 thesis, and conjectured that whenever k > 1, the interval [a, a+k] always included a number coprime to both endpoints. It was only later that he found the first counterexample, [2184, 2185, \dots, 2200] with k = 16.
David L. Dowe proved that there are infinitely many Erdős–Woods numbers, and Cégielski, Heroult and Richard showed that the set is recursive.
References
Patrick Cégielski; François Heroult, Denis Richard (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.
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.
External links
Sloane's A059757 : Initial terms of smallest Erdos-Woods intervals. The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
