Erdős–Woods number

From HandWiki
Short description: Type of positive integer

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

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, …, 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. 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) showed that the set of Erdős–Woods numbers is recursive.[3]

References

  1. ↑ Woods, Alan L. (1981). Some problems in logic and number theory, and their connections (PDF) (PhD). University of Manchester. Archived from the original (PDF) on 2019-06-08.
  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. .

External links



Retrieved from "https://handwiki.org/wiki/index.php?title=Erdős–Woods_number&oldid=3385137"