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, \dots, 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[]

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

History[]

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, \dots, 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, \dots, 2200]$ , with $k = 16$ . The existence of this counterexample shows that 16 is an Erdős–Woods number.

Dowe (1989) proved that there are infinitely many Erdős–Woods numbers,^[2] and Cégielski, Heroult & Richard (2003) showed that the set of Erdős–Woods numbers is recursive.^[3]

References[]

^ 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)
^ Dowe, David L. (1989), "On the existence of sequences of co-prime pairs of integers", J. Austral. Math. Soc. Ser. A, 47: 84–89, doi:10.1017/S1446788700031220.
^ 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.

External links[]

OEIS sequence A059757 (Initial terms of smallest Erdos-Woods intervals)

[1] 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)

[2] Dowe, David L. (1989), "On the existence of sequences of co-prime pairs of integers", J. Austral. Math. Soc. Ser. A, 47: 84–89, doi:10.1017/S1446788700031220.

[3] 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.

[1]

[2]

[3]