Número de Erdős-Woods

En teoría de números, se dice que un entero positivo k es un número de Erdős-Woods si tiene la siguiente propiedad: existe un número entero positivo tal que en la secuencia (a, a + 1, ..., a + k) de enteros consecutivos, cada uno de los elementos tiene un factor común no trivial con uno de los puntos finales. En otras palabras, k es un número de Erdős-Woods si existe un entero positivo tal que para cada entero i entre 0 y k, al menos uno de los máximos comunes divisores MCD (a, a + i) y MCD (a + i, a + k) es mayor que 1.

Ejemplo

Los primeros números de Erdős-Woods son

16, 22, 34, 36, 46, 56, 64, 66, 70 … (sucesión A059756 en OEIS).

(Podría decirse que 0 y 1 también podrían incluirse como entradas triviales).

Historia

La investigación de tales números surgió de la siguiente conjetura previa de Paul Erdős:

Existe un entero positivo k tal que cada entero a está determinado únicamente por la lista de divisores primos de a, a + 1, ..., a + k.

Alan R. Woods investigó esta cuestión para su tesis de 1981. Woods conjeturó[1]​ que siempre que k > 1, el intervalo [a, a + k] siempre incluye un número coprimo para ambos puntos finales. Poco después encontró la primera secuencia ejemplo, [2184, 2185, ..., 2200], con k = 16. La existencia de esta secuencia muestra que 16 es un número de Erdős-Woods.

Dowe (1989) demostró que hay infinitos números de Erdős-Woods,[2]​ y Cégielski, Heroult y Richard (2003) probaron que el conjunto de números de Erdős-Woods es recursivo.[3]​

Referencias

  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 Archivado el 8 de junio de 2019 en Wayback Machine.
  2. ↑ Dowe, David L. (1989), «On the existence of sequences of co-prime pairs of integers», J. Austral. Math. Soc. (A) 47: 84-89, doi:10.1017/S1446788700031220 ..
  3. ↑ Cégielski, Patrick; Heroult, François; Richard, Denis (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, doi:10.1016/S0304-3975(02)00444-9 ..

Enlaces externos