Nombre d'Erdős-Woods

En teoria de nombres, es diu que un nombre enter positiu k és un nombre d'Erdős-Woods si té la següent propietat: existeix un nombre positiu a tal que en la seqüència (a, a+1,...,a+k) d'enters consecutius, cada element de la sèrie té un factor comú amb un dels extrems de la sèrie (a i a+k). Dit en altres paraules, k és un nombre d'Erdős-Woods si existeix un nombre enter positiu a que per a cada enter i entre 0 i k, almenys un dels màxims comuns divisors mcd(a,a+i) o mcd(a+i,a+k) sigui estrictament superior a 1.

Els primers nombres d'Erdős-Woods són:

16, 22, 34, 36, 46, 56, 64, 66, 70...^[1] (es podrien afegir els casos del 0 i l'1 com a casos trivials)

La investigació d'aquests nombres prové de la conjectura atribuïda a Paul Erdős:

Existeix un enter positiu k tal que cada nombre enter a es determina de forma única per la llista de divisors primers de a, a + 1, …, a + k.

Alan R. Woods ho va investigar en la seva tesi de 1981. Woods va conjecturar^[2] que sempre que k>1, l'interval[a,a+k] sempre inclou un nombre coprimer als dos extrems de l'interval. Posteriorment va trobar el contraexemple [2184, 2185, …, 2200], amb k = 16.

L'any 1989, Dowe va demostrar^[3] que existeixen infinits nombres d'Erdős-Woods. Posteriorment, l'any 2003, Cégielsi, Heroult i Richard van demostrar^[4] que el conjunt dels nombres d'Erdős-Woods és un conjunt recursiu.

Referències

1. (successió A059756 a l'OEIS)
2. Alan L. Woods, Some problems in logic and number theory, and their connections Arxivat 2019-06-08 a Wayback Machine.. Ph.D. thesis, University of Manchester, 1981
3. David L. Dowe «On the existence of sequences of co-prime pairs of integers». J. Austral. Math. Soc., 47, 1989, pàg. 84–89. DOI: 10.1017/S1446788700031220.
4. Patrick Cégielski; François Heroult, Denis Richard «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, 2003, pàg. 53–62. DOI: 10.1016/S0304-3975(02)00444-9.