In number theory, a positive integerk 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 divisorsgcd(a, a + i) or gcd(a + i, a + k) is greater than 1.
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.
^Woods, Alan L. (1981). (PDF) (PhD). University of Manchester. Archived from the original (PDF) on 2019.
^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)
January 14, 2023
erdős, woods, number, number, theory, positive, integer, said, following, property, there, exists, positive, integer, such, that, sequence, consecutive, integers, each, elements, trivial, common, factor, with, endpoints, other, words, there, exists, positive, . In number theory a positive integer k is said to be an Erdos 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 Erdos 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 Contents 1 Examples 2 History 3 References 4 External linksExamples EditThe first Erdos 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 EditInvestigation of such numbers stemmed from the following prior conjecture by Paul Erdos 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 gt 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 Erdos Woods number Dowe 1989 proved that there are infinitely many Erdos Woods numbers 2 and Cegielski Heroult amp Richard 2003 showed that the set of Erdos Woods numbers is recursive 3 References Edit 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 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 Cegielski Patrick Heroult Francois 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 EditOEIS sequence A059757 Initial terms of smallest Erdos Woods intervals Retrieved from https en wikipedia org w index php title Erdos Woods number amp oldid 1099037396, wikipedia, wiki, book, books, library,
