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.