Erdős-Woods-getal: verschil tussen versies

In de getaltheorie is een positief geheel getal k een Erdős–Woods-getal wanneer er een rij van opeenvolgende gehele getallen (a, a+1, ..., a+k) bestaat, met a een positief geheel getal, zodanig dat elk van de elementen in de rij een deler gemeen heeft met een van de eindpunten van de rij. Met andere woorden: geen enkel getal in de rij is relatief priem met beide eindpunten van de rij.

Men kan dit ook als volgt formuleren: k is een Erdős–Woods-getal indien er een positief geheel getal a bestaat, zodat voor elk geheel getal i tussen 0 en k, ggd(a, a+i) > 1 of ggd(a+k, a+i) > 1.

De Erdős–Woods-getallen

De eerste niet-triviale Erdős–Woods-getallen zijn:

16, 22, 34, 36, 46, 56, 64, 66, 70, ... (rij A059756 in OEIS).

De corresponderende getallen a (beginpunt van de rij) zijn:

2184, 3521210, 47563752566, 12913165320, 3180417880379694, 2212091405535117414, 3843095117044776029646, 3615758618744894508744, 13151117479433859435440, ... (rij A059757 in OEIS).

Geschiedenis

De Erdős–Woods-getallen danken hun naam aan een probleem dat geformuleerd werd door Paul Erdős in 1980: bestaat er voor elk natuurlijk getal a een geheel getal k zodat a eenduidig bepaald is door alle priemfactoren van a, a+1, ..., a+k?

Alan R. Woods, die (onder meer) dit probleem onderzocht in zijn doctoraatsthesis aan de universiteit van Manchester^[1], formuleerde dit als het vermoeden dat er een geheel getal k bestaat zo dat de gehele getallen x en y gelijk zijn als en slechts als voor i=0, 1, ..., k, de getallen x+i en y+i dezelfde priemfactoren hebben. Dit staat bekend als het vermoeden van Erdős–Woods.

Tevens vermoedde Woods dat er voor elk geordend paar (a,k) van natuurlijke getallen, met k > 2, er een natuurlijk getal c bestaat, tussen a en a+k, dat relatief priem is met a en met a+k. Hij vond echter reeds kort daarna een tegenvoorbeeld van dit vermoeden, namelijk het paar (2184,16): geen elk getal tussen 2184 en 2184+16=2200 is relatief priem met 2184 en 2200.

In 1987 bewees David Dowe dat er oneindig veel van deze getallen k zijn; die zijn bekend geworden als Erdős–Woods-getallen.^[2]

Patrick Cégielski en medewerkers bewezen in 2003 dat k steeds kleiner is dan a en dat de verzameling van Erdős–Woods-getallen recursief is, en kan berekend worden met een algoritme. Zij berekenden de getallen tot circa 600.^[3] Al deze getallen zijn even; maar dit betekent niet dat alle Erdős–Woods-getallen even zijn, zoals Dowe vermoedde. Het eerste oneven Erdős–Woods-getal is k=903, en er zijn oneindig veel even zowel als oneven Erdős–Woods-getallen. Een Erdős–Woods-getal kan ook een priemgetal zijn (bijvoorbeeld k=15493).

Open vragen

Cégielski et al. formuleerden een aantal open vragen in verband met deze getallen, onder meer:

• Als het Erdős–Woods-getal k in het paar (a, k) even is, is a dan altijd even of niet?
• Er zijn veel "koppels" van Erdős–Woods-getallen, die opeenvolgende even getallen zijn: 34 en 36, 64 en 66, enz. Zijn er oneindig veel van deze koppels?
• Er zijn rijen van drie opeenvolgende even Erdős–Woods-getallen (92,94,96) en van vier opeenvolgende (216, 218, 220, 222). Is er voor elk geheel getal n een rij van n opeenvolgende even Erdős–Woods-getallen?
• Bestaat er voor elk geheel getal n > 1 een verschil tussen twee opeenvolgende Erdős–Woods-getallen dat gelijk is aan n?