Erdős–Woods-számok

A Wikipédiából, a szabad enciklopédiából

A számelméletben egy pozitív egész szám, k Erdős–Woods-szám, ha létezik egy pozitív egész a, hogy az (a, a + 1, …, a + k) számok egyike sem relatív prím mindkét végponthoz. Más szavakkal, k Erdős–Woods szám, ha van egy pozitív egész a, hogy minden 0 és k közötti egészre az lnko(a, a + i) és az lnko(a + i, a + k) legnagyobb közös osztók valamelyike nem 1.

Az első néhány Erdős–Woods szám:

16, 22, 34, 36, 46, 56, 64, 66, 70 … (A059756 sorozat az OEIS-ben).

Az első háromhoz tartozó a értékek:

2184, 3521210, 47563752566 Sablon:OEIS2C.

A 0 és az 1 triviális Erdős–Woodsnak tekinthetők.

Erdős Pál sejtése nyomán kezdték el vizsgálni, ami azt állította, hogy van egy pozitív egész k szám, hogy az a, a + 1, …, a + k prímosztói egyértelműen meghatároznak egy alkalmas a egészet.

Alan R. Woods 1981-ben foglalkozott a kérdéssel, és azt a sejtést fogalmazta meg, hogy minden k-ra az [a, a + k] egész intervallum mindig tartalmaz olyan számot, ami mindkét végponthoz relatív prím.[1] Később az első ellenpéldát is ő találta meg: [2184, 2185, …, 2200], k = 16.

Dowe (1989) belátta, hogy végtelen sok Erdős–Woods szám létezik, és Cégielski, Heroult & Richard (2003) megmutatta, hogy az Erdős–Woods számok halmaza rekurzív.

Jegyzetek[szerkesztés | forrásszöveg szerkesztése]

  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)

Források[szerkesztés | forrásszöveg szerkesztése]

  • 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. o. 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. 47, 84–89. o. DOI:10.1017/S1446788700031220.