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
Print Friendly, PDF & Email