El "conjunto generador" de los números primos

Imaginaos que un día alguien (un profesor, un compañero de clase, un amigo…) os dice lo siguiente:

Soy capaz de darte una lista de 26 números primos tal que si tomas cualquier otro número primo puedes llegar a alguno de esos 26 tachando una o más de sus cifras.

La primera sensación (al menos así fue la mía) es de sorpresa. ¿Cómo puede existir una especie de conjunto generador de los números primos teniendo en cuenta que este conjunto es infinito (demostración de Euclides; demostración usando primos de Fermat) y la casi nula (al menos hasta donde se conoce en nuestros días) regularidad del mismo?

Supongamos que esa persona insiste mucho y nos acabamos creyendo el asunto. Lo siguiente que se nos puede pasar por la cabeza es que la demostración de este resultado debe ser muy larga y engorrosa. Cuando nos dicen que la misma no llega a página y media de un archivo pdf la sensación de sorpresa aumenta. Un resultado tan curioso con una demostración tan corta aún tiene más valor.

Algún problema debe tener esto, podríamos pensar. Resultado curioso e interesante, demostración no muy larga…Ya está, la demostración es muy poco intuitiva o utiliza resultados demasiado avanzados. Nada más lejos de la realidad: la demostración es totalmente constructiva y los números de la lista van apareciendo por sí solos después de utilizar razonamientos bastante básicos si tenemos en cuenta la potencia del resultado. En dos palabras: absolutamente increible.

¿Cómo se os ha quedado el cuerpo? ¿Hay ganas de adentrarse en el asunto? Espero que sí, porque vamos a ello.

Notación preliminar

En todo el artículo hablaremos de los números como cadenas de dígitos que representaremos con las letras w, x, y y z. Dadas dos cadenas w y x, diremos que w es una subsecuencia de x si podemos obtener w a partir de x tachando cero o más dígitos de x. Por ejemplo, 359\triangleleft 2436590. Representaremos esta situación así: w\triangleleft x. Denotaremos por \epsilon a la cadena que no contiene ningún dígito, es decir, a la cadena vacía.

Usaremos también la siguiente notación para denotar la formación de cadenas en las que el primer elemento es del primer conjunto y el segundo elemento es del segundo conjunto: \left \{ 2,5 \right \}\left \{3,7 \right \}=\left \{23,27,53,57 \right \}.

Para terminar, usaremos el símbolo * para denotar que consideramos un número cualquiera de repeticiones de los miembros de un conjunto en cualquier orden. Por ejemplo: \left \{ 2,5 \right \}\left \{3,7 \right \}^*=\left \{2,5,23,27,53,57,233,237,273,277,533,537,573,577,2333,2337, \cdots \right \}.

Dado un conjunto de cadenas S podemos definir el conjunto M(S) de sus elementos mínimos. Por un teorema clásico de la teoría del lenguaje formal se sabe que este conjunto es finito. La cuestión ahora por tanto es determinar M(S) para S=\left \{ \mbox{primos} \right \}.

Teorema

Si S=\left \{ \mbox{primos} \right \}=\left \{2,3,5,7,11, \dots \right \}, entonces:

\begin{matrix} M(S)=\{ 2,3,5,7,11,19,41,61,89,409,449,499,881,991,6469,6949,9001,9049,9649,9949, \\ 60649,666649,946669,60000049,66000049,66600049 \} \end{matrix}

Es decir, tomando cualquier número primo y tachando cero o más de sus cifras de forma conveniente siempre llegaremos a alguno de los números primos de esa lista.

Demostración

Evidentemente todos los números de esa lista son números primos y no se puede llegar a ninguno de ellos desde otro de la lista tachando cifras (os dejo la comprobación de estos dos hechos a vosotros). Vamos con el grueso de la demostración:

Sea x\in\left \{ \mbox{primos} \right \} Si x tiene longitud 1, entonces x \in \left \{2,3,5,7 \right \} y por tanto x\in M(S). Asumiremos entonces que x es un número primo con longitud mayor o igual que 2. En este caso el último dígito de x debe ser uno de éstos: \left \{1,3,7,9 \right \} (al ser primo). Si el último dígito es 3 ó 7 entonces podemos tachar todos los demás hasta llegar a ellos, o lo que es lo mismo, usando nuestra notación, 3\triangleleft x y 7\triangleleft x respectivamente y por tanto ya habríamos terminado. Las únicas posibilidades que nos quedan para ese último dígito de x son 1 y 9.

Caso 1: x termina en 1

Sea x=y1 (siendo y cualquier cadena de dígitos$). Si y contiene alguno de los dígitos del conjunto \left \{2,3,5,7 \right \} entonces x tiene una subsecuencia en M(S) y por tanto hemos terminado. Si y contiene alguno de los elementos del conjunto \left \{1,4,6 \right \} también hemos acabado ya que 11\triangleleft x, 41\triangleleft x y 61\triangleleft x respectivamente. Por tanto tenemos que y\in \left \{8,9 \right \} \left \{0,8,9 \right \}^*.

Caso 1a: x comienza por 8

En este caso x=8z1 con z una cadena cuyos dígitos son {0}, 8 ó 9 colocados de la forma comentada en el Caso 1. Si 9\triangleleft z entonces 89\triangleleft x y hemos terminado. Si 8\triangleleft z entonces 881\triangleleft x y acabamos. Por tanto x\in 80^*1, es decir, x es un número que comienza en 8, continúa con un determinado número de ceros y termina en 1. Pero entonces la suma de los dígitos de x es 9 y por tanto es múltiplo de 3. En consecuencia no es primo. Este estudio completa este subcaso.

Caso 1b: x comienza por 9

En este caso x=9z1 con z una cadena cuyos dígitos son {0}, 8 ó 9 colocados de la forma comentada en el Caso 1. Si 9\triangleleft z entonces 991\triangleleft x y acabamos. Si z contiene dos o más ceros entonces 9001\triangleleft x y terminamos. Si z contiene dos o más ochos se tiene que 881\triangleleft x y se acaba. Por eliminación z no contiene ningún nueve y contendrá uno o dos ceros y uno o dos ochos. Pero entonces x\in \left \{91, 901, 981, 9081,9801 \right \} y todos esos números son compuestos. Con esto termina este subcaso.

Caso 2: x termina en 9

Sea x=y9 (siendo y cualquier cadena de dígitos$). Si y contiene alguno de los dígitos del conjunto \left \{2,3,5,7 \right \} entonces x tiene una subsecuencia en M(S) y por tanto hemos terminado. Si 1\triangleleft y o si 8\triangleleft y entonces, respectivamente, 19\triangleleft x y 89\triangleleft x. Por tanto tenemos que y\in \left \{4,6,9 \right \} \left \{0,4,6,9 \right \}^*.

Si x no contiene ningún 4 entonces la suma de los dígitos de x es múltiplo de 3 y por tanto x no es primo. Si x contiene dos o más cuatros entonces 449\triangleleft x y terminamos. Por tanto podemos asumir que x contiene exactamente un cuatro.

Caso 2a: x comienza por 4

Entonces x=4z9. Si $9\triangleleft z$ entonces 499\triangleleft x y se termina. Si 0\triangleleft z entonces 409\triangleleft x y acabamos. Por tanto se tiene que x\in 46^*9. Pero entonces x es divisible por 7. Esto puede parecer complicado de ver pero en realidad es muy sencillo. Escribid la división: 46 \cdots 69:7. En el cociente ponemos un 6 y nos quedan 4, volvemos a poner otro 6 en el cociente y nos vuelven a quedar 4, y así sucesivamente sea cual sea el número de veces que aparece el 6. En el último paso nos quedará 49, que es divisible por 7, y terminamos. Con esto se completa este subcaso.

Caso 2b: x comienza por 6

Entonces x=6y4z9 (recordemos que x contiene exactamente un 4) con y,z\in \left \{0,6,9 \right \}^*. Si 6\triangleleft z entonces 6469\triangleleft x y terminamos. Si 0\triangleleft z entonces 409\triangleleft x y se acaba. Si 9\triangleleft z entonces 499\triangleleft x y se termina. Por tanto z no contiene ningún dígito. Si 9\triangleleft y entonces 6949\triangleleft x. Por estos dos últimos datos se tiene que x=6y49 con y\in \left \{0,6 \right \}^*. Si 06\triangleleft y entonces 60649\triangleleft x. Por tanto y\in 6^*0^*. Si 666\triangleleft y entonces 666649\triangleleft x. Si 00000\triangleleft y entonces 60000049\triangleleft x. Por todo esto se tiene que y\in \left \{ \epsilon,6,66 \right \} \left \{ \epsilon,0,00,000,0000 \right \}. Tenemos las siguientes posibilidades:

  • 649: no primo (divisible por 11)
  • 6649: no primo (divisible por 61)
  • 66649 no primo (divisible por 11)
  • 6049: no primo (divisible por 23)
  • 66049: no primo (divisible por 257)
  • 666049 no primo (divisible por 79)
  • 60049: no primo (divisible por 11)
  • 660049: no primo (divisible por 13)
  • 6660049: no primo (divisible por 11)
  • 600049: no primo (divisible por 17)
  • 6600049: no primo (divisible por 19)
  • 66600049: primo que ya está en la lista
  • 6000049: no primo (divisible por 11)
  • 66000049: primo que ya está en la lista
  • 666000049: no primo (divisible por 11)

Con esto terminamos este subcaso.

Caso 2c: x comienza por 9

Entonces x=9y4z9 donde y,z\in \left \{0,6,9 \right \}. Si 0\triangleleft y entonces 9049\triangleleft x y se acaba. Si 6\triangleleft y entonces 9649\triangleleft x. Si 9\triangleleft y entonces 9949\triangleleft x. Por tanto $y=\epsilon$, es decir, y es la cadena vacía. Si $0\triangleleft z$ entonces 409\triangleleft x. Si 9\triangleleft z entonces 499\triangleleft x. Por tanto $z\in 6^*$. Con todo esto se tiene que x\in 946^*9.

Si x contiene tres o más veces la cifra 6 entonces 946669\triangleleft x y se acaba. Por tanto x debe contener cero, uno o dos veces la cifra 6. Las tres posibilidades para x son 9469, 94669 y 946669 que son todos números compuestos. Con esto se termina este último subcaso y con ello concluye la demostración.

Extra

De una forma análoga podemos demostrar que también hay un conjunto generador de los números compuestos formados por 32 números:

Teorema 2

Si S=\left \{ compuestos \right \}, entonces:

\begin{matrix} M(S)= \{4,6,8,9,10,12,15,20,21,22,25,27,30,32,33,35,50,51,52,55,57,70,72,75,77,111, \\ 117,171,371,711,713,731 \} \end{matrix}

La demostración de este teorema es similar a la anterior. Si alguien quiere entretenerse puede intentarla y enviármela por mail y se la publico. Si yo tengo tiempo me pongo a desarrollarla.

Y podemos intentar buscar ese conjunto generador para cualquier otro conjunto clásico de números como por ejemplo el conjunto de los cuadrados perfectos, el de los cubos, etc.

Y como suele pasar en resultados relacionados con números primos no podían faltar las conjeturas. En este caso la encontramos con el conjunto generador del conjunto de las potencias de 2

Conjetura: conjunto generador de las potencias de 2

Sea S=\left \{ \mbox{potencias de }2 \right \}. Entonces:

M(S)=\left \{1,2,4,8,65536 \right \}

Parece ser que por ahora no se sabe si esta conjetura es cierta. Podemos intentar demostrarla o refutarla nosotros. Una ayuda, bastante evidente, es la siguiente: sería suficiente para demostrar esta conjetura que toda potencia de 2 mayor que 65536 contenga al menos una vez al 1, al 2, al 4 ó al 8. A ver si hay avances.

Fuentes:

  • Minimal Primes: archivo ps (convertible a pdf) donde se detalla la demostración (en inglés)
  • Microsiervos: en este post Alvy comentaba el resultado y daba el enlace al archivo ps con la demostración que he enlazado justo antes

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

17 Comentarios

  1. Pues sí, es muy sorpendente y si lo he podido entender, es que demasiado complicado no es 🙂

    ¿Con qué leéis documentos .ps?

    La lista de números M(S) está comprobada. Todos son primos, como no tengo Mathematica lo he hecho con mi programita web! (spam?) http://www.enric.es/php/primos

    Publica una respuesta
  2. La irregularidad de los números primos está producida por un patrón geométrico de curvas periódicas superpuestas. Cada curva representa a un divisor. Los números primos son los únicos interceptados por dos curvas. Puedes ver el diagrama en: http://www.polprimos.com

    Publica una respuesta
  3. Omar, he leido el documento de tu página web y es bonito ver esos gráficos, se ve que te lo has currado, enhorabuena en ese sentido.

    Desafortunadamente, para construir esas curvas periódicas necesitas conocer todos los números primos, lo cual hace que su utilidad sea nula.

    Es como que yo defina la función:

    $latex \displaystyle g(x,p) = \begin{cases}
    1, \ \ \ \mbox{si }p\ mod\ x = 0 \\
    0, \ \ \ \mbox{si }p\ mod\ x \ne 0
    \end{cases}$

    y diga que la siguiente función indica con un 1 dónde están todos los primos y con un 0 dónde no están:

    \displaystyle f(x) = \sum_{p = primos} g(x,p)

    De todas maneras te vuelvo a repetir que enhorabuena por tu trabajo.

    Publica una respuesta
  4. hmmm…muy interesante (le di una leida rapida) ,creativo muy creativo …cuanto camino habra recorrido? cuantas cosas habra imaginado?….

    Publica una respuesta
  5. En cuanto a los conjuntos generadores, tienen su miga pero creo que no es más que una curiosidad. Lo digo porque lo que es una conjetura en base 10 no es más que una trivialidad en otra base de numeración, por ejemplo base 2:

    Primos: M(S)={01,11}
    Potencias de 2: M(S) = {1}

    Y supongo que podemos seguir jugando así con otras bases de numeración y otros conjuntos de números, por eso digo que más que nada es una curiosidad, aunque tiene su complejidad.

    Publica una respuesta
  6. Asier:
    Gracias por el calificativo de “bonito”. No entiendo lo de “currado”. En cuanto a las curvas periódicas, te digo que si sólo se trazaran las que corresponden a los números primos entonces el diagrama sería una representación geométrica del método utilizado en la criba de Eratóstenes. Pero en este dibujo existe una curva por cada número natural, sea primo o compuesto. Y no hay que saber de antemano que curva trazar. Se trazan todas las curvas posibles. El diagrama representa la estructura de divisores de los números naturales. La cantidad de curvas que intercepta cada número es igual a la cantidad de divisores del número. Creo la imágen ayuda a entender porqué hay lagunas de primos. Es sólo una visualización. No te digo que sirva para algo. Un saludo y gracias.

    Publica una respuesta
  7. Entiendo lo que dices, Omar, me refería a que de alguna manera necesitas hacer el cálculo de todos los múltiplos de los números anteriores para saber si un número dado es primo, lo cual es equivalente a calcular los múltiplos de todos los números primos menores que el número dado y mirar si alguno coincide con el número dado. Es decir, para saber si por un número solamente pasan dos curvas es necesario calcular todas las anteriores.

    Que te lo has currado significa que te lo has trabajado, vamos, que se ve que le has dedicado tiempo y esfuerzo.

    Publica una respuesta
  8. Asier:
    Leí esta frase: La utilidad o inutilidad de las cosas, no depende las cosas en sí mismas, sino de la aplicación que se les quiera dar. ¿Estás de acuerdo con esto?. Y ahora va otra pregunta:
    ¿Puede una persona que lo único que sabe de números es contar hasta 2, determinar la posición de los números primos sobre la recta numérica? (No de todos, claro está). Un saludo grande.

    Publica una respuesta
  9. Hola Omar,
    creo que las cosas pueden ser muy útiles para algunas cosas y completamente inútiles para otras. Una pastilla de jabón es útil para lavar pero inútil para cortar un filete, por mucho que quiera darle esa aplicación. Ahora bien, siempre hay que dejar la puerta abierta para originales y novedosas utilidades.

    No entiendo bien la segunda pregunta… alguien qué solo sabe contar hasta 2… igual no sabe lo que es un número primo, ¿no? jeje, no sé a lo que te refieres exactamente.

    Publica una respuesta
  10. Supongo que Omar se refiere a que si hay infinitos primos, por muchos que tomemos nos serán insuficientes para encontrar un patrón. Ya responderá.

    Publica una respuesta
  11. hey necesito saber como se llama el conjunto de numeros que no es usual osea el q viene despues de los imginarios por resp rapidas q es pa mañanaa se lo agradesco

    Publica una respuesta
  12. Enric:
    En el problema de la persona que solo sabe contar hasta 2, no intervienen cuestiones sobre el infinito ni sobre el cálculo de probabilidades. Digamos, por ejemplo, que la persona tiene que determinar la posición de los primeros 10 números primos. Por supuesto que él (O ella) no sabe lo que es un divisor, ni un múltiplo, ni un número primo. Tampoco sabe multiplicar ni dividir. ¿Puede resolver el problema?

    Publica una respuesta
  13. Estimado Omar: no te dejes desanimar. La utilizacion de funciones periòdicas para la “visualización” del caracter de primalidad, es cierto que no ayuda a generar primos más allá de un cierto limite que viene dado por el numero inicial de primos generadores que emplees. Pero tambien es cierto que puede utilizarse para la implementaciòn de un algoritmo que genere sistematicamente todos los primos de forma ordenada. Llegas a una criba de Eratòstenes muy sofisticada. Ahora bien, que no sea “util” o que sí losea solo depende de lo que le pidas. Yo llevo investigando este asunto desde el 2005 y me ha ayudado a demostrar que la ubicaciòn de los primos dentro de la succesiòn de los enteros no solo no es aleatoria en absoluto sino que esta rigidamente determinada por un conjunto infinito de simetrías, cada una de las cuales incluye a las anteriores. Es algo realmente sorprendente, pero según en qué punto N de la recta real nos encontremos existirà un eje de simetria cercano a ese punto que determina las ubicaciones de todos los primos existentes entre N y 2N. y esto, para cualquier valor de N por alto qu sea. Si quieres lo comentamos.

    Publica una respuesta
  14. Mi muy respetado colega:

    Su “DETERMINACION geométrica de los Números primos y perfectos” ¡me ha encantado!
    Usted esta trabajando los dos modos diferentes de entender la didáctica de la matemática que plantea Bruno DÁmore en su libro Didáctica de la Matemática :
    A. Como divulgación de las ideas, fijando por lo tanto la atención en la fase de la enseñanza
    B. Como investigación empírica, fijando la atención en la fase del aprendizaje o epistemología del aprendizaje de la matemática.
    Le comparto que yo personalmente escribo fábulas matemáticas y cuando leí a Bruno DÁmore me di cuenta que lo que hago está enmarcado en esos dos modos de los que habla el escritor boloñès. Lo felicito, con la gráfica de la serie de la cantidad de divisores de los números naturales y la serie de los números primos, es posible que muchos de los estudiantes, fuera de aprender más sobre los números primos se hayan complacido con sus gráficas y posiblemente algunos mientras lo hacían viajaron y vieron su propio feto……aprendieron mucho, pasaron diferente un día de clase cualquiera. Lo felicito la lùdica està inmersa en su trabajo. Si algún día logro que me publiquen “El Planeta de los Nùmeros Primos” …le haré llegar a Argentina un ejemplar.

    Publica una respuesta

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *