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:
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
[modifica]- ↑ (successió A059756 a l'OEIS)
- ↑ 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
- ↑ 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.
- ↑ 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.