词条 | Erdős–Woods number |
释义 |
In number theory, a positive integer {{mvar|k}} is said to be an Erdős–Woods number if it has the following property: there exists a positive integer {{mvar|a}} such that in the sequence {{math|(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, {{mvar|k}} is an Erdős–Woods number if there exists a positive integer {{mvar|a}} such that for each integer {{mvar|i}} between {{math|0}} and {{mvar|k}}, at least one of the greatest common divisors {{math|gcd(a, a + i)}} and {{math|gcd(a + i, a + k)}} is greater than {{math|1}}. ExamplesThe first few Erdős–Woods numbers are 16, 22, 34, 36, 46, 56, 64, 66, 70 … {{OEIS|id=A059756}}. (Arguably 0 and 1 could also be included as trivial entries.) HistoryInvestigation of such numbers stemmed from the following prior conjecture by Paul Erdős: There exists a positive integer {{mvar|k}} such that every integer {{mvar|a}} is uniquely determined by the list of prime divisors of {{math|a, a + 1, …, a + k}}. Alan R. Woods investigated this question for his 1981 thesis. Woods conjectured[1] that whenever {{math|k > 1}}, the interval {{math|[a, a + k]}} always includes a number coprime to both endpoints. It was only later that he found the first counterexample, {{math|[2184, 2185, …, 2200]}}, with {{math|1=k = 16}}. The existence of this counterexample shows that 16 is an Erdős–Woods number. {{harvtxt|Dowe|1989}} proved that there are infinitely many Erdős–Woods numbers,[2] and {{harvtxt|Cégielski|Heroult|Richard|2003}} showed that the set of Erdős–Woods numbers is recursive.[3]References1. ^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. ^{{citation | last = Dowe | first = David L. | doi = 10.1017/S1446788700031220 | journal = J. Austral. Math. Soc. (A) | pages = 84–89 | title = On the existence of sequences of co-prime pairs of integers | volume = 47 | year = 1989}}. 3. ^{{citation | last1 = Cégielski | first1 = Patrick | last2 = Heroult | first2 = François | last3 = Richard | first3 = Denis | doi = 10.1016/S0304-3975(02)00444-9 | issue = 1 | journal = Theoretical Computer Science | pages = 53–62 | title = On the amplitude of intervals of natural numbers whose every element has a common prime divisor with at least an extremity | volume = 303 | year = 2003}}. External links
2 : Paul Erdős|Integer sequences |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。