Erdős-Woods-getal

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Naar zoeken springen

In de getaltheorie heet een positief geheel getal k een Erdős–Woods-getal als er een rij van opeenvolgende gehele getallen a, a+1, ..., a+k bestaat, zodanig dat alle elementen in de rij een factor met een van de eindpunten van de rij gemeen hebben. Met andere woorden: geen enkel getal in de rij is relatief priem met beide eindpunten van de rij.

De eerste Erdős–Woods-getallen k zijn:

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

De corresponderende beginpunten a zijn:

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

Voor het eerste Erdős–Woods-getal 16 geldt bijvoorbeeld dat van de rij:

2184, ...., 2200

het beginpunt 2184 = 2×3×7×13, en het eindpunt 2200=2×2×2×5×5×11, zodat van de tussenliggende getallen sowieso de even getallen voldoen, evenals de 3-vouden en de 5-vouden. Blijven over: 2189 = 11×199, 2191 = 3×7×13 en 2197 = 13×439, dus 11-, 7- of 13-vouden.

Geschiedenis[bewerken | brontekst bewerken]

De Erdős–Woods-getallen danken hun naam aan een vermoeden, dat in 1980 door Paul Erdős werd geformuleerd:

Er bestaat een geheel getal k, zodat voor ieder paar a en b de beide kleinste gemene veelvouden van a, a+1, ..., a+k en b, b+1, ..., b+k een priemfactor verschillend hebben.

en aan AR Woods, die hier aan de Universiteit van Manchester onderzoek naar deed[1] en het eerste voorbeeld boven heeft gevonden.

In 1987 bewees David Dowe dat er oneindig veel van Erdős–Woods-getallen k zijn.[2]

Patrick Cégielski en medewerkers bewezen in 2003 dat k steeds kleiner is dan a, dat de verzameling van Erdős–Woods-getallen recursief is en met een algoritme kan worden berekend. 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[bewerken | brontekst bewerken]

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 paren van Erdős–Woods-getallen, die opeenvolgende even getallen zijn: 34 en 36, 64 en 66, enz. Zijn er oneindig veel van deze paren?
  • 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?

Referenties[bewerken | brontekst bewerken]

  1. (en) AR Woods aan de Universiteit van Manchester. Some problems in logic and number theory, and their connections, 1981, (pdf). PhD Thesis.
  2. (en) DL Dowe in Journal of the Australian Mathematical Society, series A. On the existence of sequences of co-prime pairs of integers , 1989. blz. 84-89. DOI:10.1017/S1446788700031220
  3. (en) Cégielski, F Heroult, D Richard in Theoretical Computer Science. On the amplitude of intervals of natural numbers whose every element has a common prime divisor with at least an extremity, 2003. vol. 303, nr. 1, blz. 53-62. DOI:10.1016/S0304-3975(02)00444-9