Experimento: Determinando números primos con eventos aleatorios

Seguimos con el cuento de los primos. Esta entrada no es tan teórica, es más experimental. Hace unos días hablamos acerca de generar primos usando funciones, vimos que con polinomios el asunto es bastante grave. Demostramos que existe una función exponencial (compuesta con la función parte entera) que siempre es primo. Sin embargo, vimos que las dificultades a la hora de calcular las constantes que tienen dicha función, nos dejan tan lejos como cuando teníamos nada.

Mientras escribía esa entrada, recordaba palabras de un profesor mío, en las cuales hablaba de la aleatoriedad que aparentan tener los números primos. Recordaba que él me decía que el teorema de los números primos parece decir que al escoger un número entre cero y un valor N, la probabilidad de ser un número primo es cercano al valor 1/\ln(N). Recordé además muchas cosas que me dijo acerca de la función \mu de Möbius y aleatoriedad. Sin embargo, lo que me vino a la mente fue eso acerca de que tiene probabilidad 1/\ln(N). Entonces me hice la pregunta.

Si determinamos un número primo usando el azar… ¿Qué podemos concluir?

Es decir, si para saber si 8237 es primo, lo que hacemos es lanzar una moneda y dependiendo del resultado decidimos si será o no un número primo. No busco hallar una correspondencia verdadera ni resultados verídicos. Es decir, al estar jugando con el azar, nos podría dar que 10 es un número primo. Además, partiendo del hecho que el teorema de los números primos nos indica que dicha probabilidad es de 1/\ln(N), usar una moneda (en la cual la probabilidad es de un medio) ya estamos en contra de la teoría. Lo único que busco es experimentar.

De este modo, realicé tres experimentos. El primero con una moneda, el segundo usando un programa que genera números aleatorios y el tercero lanzando tres dados.


Lanzando una moneda


El primer experimento, y del cual tengo las menor esperanza de que dé un resultado verídico, es con una moneda. El experimento consiste en ir recorriendo todos los números, desde el dos hasta el cien, por cada número se lanza una moneda. El criterio para decidir si dicho número es primo o no es el siguiente.

  1. Si la moneda cae cara, entonces dicho número es primo.
  2. Si la moneda cae sello, entonces dicho número es compuesto.

Nuestra moneda experimental es una moneda de mil pesos de Colombia. Es irrelevante como luce, pues es una moneda al fin, pero ahí va

exp2

Después de realizado el experimento obtuve los siguientes resultados.


Resultados del experimento


  • El número dos no es primo.
  • Tampoco lo es el 7, ni el 11, ni el 13, ni el 29, ni el…
  • El 4 sí es primo.
  • También es primo el 8, el 9, el 12, el 14, 15, 16 …
  • La cantidad de números primos menores a cien es 54.

Resultados pésimos para lo que es la realidad, pues la cantidad de números primos menores a cien es veinte y seis.


Generando números aleatorios con Java


Para este experimento, creé una clase en Java, para poder determinar la cantidad de primos menores que un número, dado por entrada. En el siguiente archivo puedes descargarlo: Generador.zip.

La manera en la clase determina si un número es primo o no es la siguiente. Se ingresa un parámetro N

  1. Se recorren todos los número a N.
  2. Para cada número, se genera un número aleatorio.
  3. Si el número es par, entonces es un número primo.
  4. Si el número es impar, entonces el número es compuesto.

El resultado se muestra en el siguiente vídeo.

Como era de esperarse, al determinar la cantidad de primos menores o iguales a un número dado, resulta ser un número muy cercano a la mitad. Esto dado al hecho que la probabilidad de que un número entero sea par es de 1/2. Al determinar un número primo de esta forma, simplemente se está diciendo que un número es primo con probabilidad 1/2. Usando algunos hechos de probabilidad podemos demostrar que el hecho de que sea un valor cercano a la mitad no es sorpresa

Sea N un entero positivo. Sea X_i con 1<i\leq N el evento X_i=1 si i es un número primo y cero en caso contrario, entonces la cantidad de primos menores que N es

\displaystyle\sum_{1<i\leq N}X_i.

Calculemos el valor esperado de esta suma,

E\left(\displaystyle\sum_{1<i\leq N}X_i\right)=\displaystyle\sum_{1<i\leq N}E\left(X_i\right).

El valor esperado de cada una de las variables aleatorias es

E\left(X_i\right)=1/2.

Concluimos que

E\left(\displaystyle\sum_{1<i\leq N}X_i\right)=\displaystyle\sum_{p\leq N}\frac{1}{2}=\frac{\pi(N)}{2}.

Tal vez te estés preguntando el por qué separo el caso en el cual determino un número primo usando una moneda, y en el cual lo determino usando la paridad de un número seleccionado al azar. La razón por la cual lo hago es que lanzar una moneda si es azar, generar un número primo en una computadora me genera dudas. ¿Como así? Empieza por hacerte esta pregunta

Si una computadora es un autómata, que sigue instrucciones dadas en su código ¿Como puede generar algo aleatorio?

Esa fue la pregunta que me hice al pensar en generar números aleatorios por computadora, razón por la cual inicié una investigación acerca del tema, llegando a toda una discusión acerca de como generar números aleatorios, en los cuales hasta la constante \pi estaba envuelta. Es una discusión muy interesante, sin lugar a dudas, tal vez en otro momento trataré este tema, por ahora, solo diré que la clase Random de Java, genera número pseudo-aleatorios usando un método llamado “Generadores de congruencia lineal”. Dicho método parte de una semilla y otras constantes más, de modo que, por medio de congruencias genera números.


Resultados del experimento


  • Para los primeros diez números dio como resultado cinco primos. En realidad hay cuatro.
  • Para los primeros cien números dio como resultado cuarenta y nueve. En realidad hay veinte y cinco.
  • Para los primeros mil números dio como resultado quinientos siete. En realidad hay ciento sesenta y ocho.
  • Para los primeros diez mil números dio como resultado cinco mil sesenta y siente. En realidad hay mil docientos  veinte y nueve.
  • Para los primeros cien mil números dio como resultado cuarenta y nueve mil novecientos noventa y cuatro. En realidad hay nueve mil quinientos noventa y dos.

Lanzando tres dados


Tal y como indicaba al principio, el teorema de los números primos, dice que si escogemos un número desde cero hasta N, la probabilidad de que sea primo es aproximadamente 1/\ln(N). Para este último experimento, quiero recrear una situación en la cual, la probabilidad de ser primo, esté dada por dicha expresión 1/\ln(N). Es decir, en los casos pasados la probabilidad de que un número sea primo 0.5, en este caso, quiero que la probabilidad sea 1/\ln(N) o un valor muy cercano. Para esto, debemos partir de el valor de N. En este experimento tomé N=100, sería preferible tomar un valor mucho más grande, pero en este caso trabajaremos con este valor. Nuestro siguiente paso es buscar un experimento que tenga un evento cuya probabilidad de suceso sea

\boxed{1/\ln(100)\approx 0.217147}

Después de reflexionar un rato, decidí hacerlo con dados, de modo que empecé por cacular la probabilidad de cada evento para dos dados, sin embargo, no logré una combinación que se aproximara a dicho valor. Intenté entonces con tres dados, obteniendo lo siguiente

Al determinar el total de casos posibles, da como resultado un total de 6\times 6\times 6=216. Escriba

P(X=a)=b.

como la probabilidad (b) de que la sumatoria de los números al lanzar los tres dados de a (X=a). De modo que lo que determinará si un número es primo o no, será la suma de los tres números dados por cada dado.

  • Las posibilidades de obtener 3 es 1 en 216. P(X=3)=0.00462963
  • Las posibilidades de obtener 4 son 3 en 216. P(X=4)=0.01388888
  • Las posibilidades de obtener 5 son 6 en 216. P(X=5)=0.02777777
  • Las posibilidades de obtener 6 son 10 en 216. P(X=6)=0.04629629
  • Las posibilidades de obtener 7 son 15 en 216. P(X=7)=0.06944444
  • Las posibilidades de obtener 8 son 21 en 216. P(X=8)=0.097222222
  • Las posibilidades de obtener 9 son 25 en 216. P(X=9)=0.11574074
  • Las posibilidades de obtener 10 son 27 en 216. P(X=10)=0.125
  • Las posibilidades de obtener 11 son 27 en 216. P(X=11)=0.125
  • Las posibilidades de obtener 12 son 25 en 216. P(X=12)=0.11574074
  • Las posibilidades de obtener 13 son 21 en 216. P(X=13)=0.097222222
  • Las posibilidades de obtener 14 son 15 en 216. P(X=14)=0.06944444
  • Las posibilidades de obtener 15 son 10 en 216. P(X=15)=0.04629629
  • Las posibilidades de obtener 16 son 6 en 216. P(X=16)=0.02777777
  • Las posibilidades de obtener 17 son 3 en 216. P(X=17)=0.01388888
  • Las posibilidades de obtener 18 es 1 en 216. P(X=18)=0.00462963

Esto quiere decir, que la probabilidad de que al lanzar los dados, el número sea doce, trece o dieciocho, es

P(X=12)+P(X=13)+P(X=18)=0.11574074+0.097222222+0.00462963=0.21759259.

El cual difiere de la probabilidad deseada por

0.00044559.

De modo que el evento que decide si un número es primo o no es: Si al lanzar tres dados, la suma es doce, trece o diez y ocho, entonces es primo.


Sí, lancé tres dados cien veces

Los resultados se encuentran en esta enorme imagen. Si haces clic la puedes ver completa.

Resultados de el experimento

Hacer clic para ver la imagen completa.


Resultados del experimento


  • El primer número primo es el cero y el segundo es diez.
  • Muchos números que no son primos ni en los bordes.
  • La cantidad de primos menor a cien es veinte. La verdadera cantidad es veinte y seis.

Este experimento es el que mas se acomodó a la realidad y era de esperarse, pues el teorema de los números primos nos dice eso. Si hacemos el ejercicio de calcular la esperanza obtenemos lo siguiente

Sea N un entero positivo. Sea X_i con 1<i\leq N el evento X_i=1 si i es un número primo y cero en caso contrario, entonces la cantidad de primos menores que N es

\displaystyle\sum_{1<i\leq N}X_i.

Calculemos el valor esperado de esta suma,

E\left(\displaystyle\sum_{0<i\leq N}X_i\right)=\displaystyle\sum_{0<i\leq N}E\left(X_i\right).

El valor esperado de cada una de las variables aleatorias es

E\left(X_i\right)=1/\ln N.

Concluimos que

E\left(\displaystyle\sum_{0<i\leq N}X_i\right)=\displaystyle\sum_{0<i\leq N}\frac{1}{\ln N}=\frac{N}{\ln N}.

Que es lo que nos indica el teorema de los números primos.


Conclusiones


Se puede hacer cualquier cantidad de experimentos, con los cuales se puede decidir si un número es primo o no, en esta entrada solo he mostrado tres, dos de los cuales son muy parecidos por no considerar que son el mismo. La idea de esta entrada es ser mas ilustrativo, salir de la teoría y verla en la práctica, con este fin, nos dimos cuenta que comparando los tres experimentos, quien dio un valor mas aproximado al verdadero fue el tercero, experimento en el cual se utilizó el conocimiento previo del teorema de los números primos.

Viene a mi mente esta situación. Un uso más útil para este teorema puede ser el siguiente: Al tener un número, digamos entre cero y un millón, deseamos saber si es primo o no, sin usar muchas herramientas. Cuando digo sin usar muchas herramientas, me refiero, por ejemplo a que no disponemos de una computadora, o celular, o Internet. Por mucho una calculadora con las operaciones básicas (no una calculadora científica). A priori nos queda complicado determinar si es un número primo o no, pero podríamos hacer esto.

  1. Revisar si es par: Mirando si el último dígito es cero o un número par.
  2. Revisar si es divisible entre tres: Mirando si la suma de todos sus dígitos es divisible entre tres.
  3. Revisar si es divisible entre cinco: Mirando si su último dígito es cinco.
  4. Revisar si es divisible entre siete: Toma la última cifra, la multiplica por dos, y resta este número al original, si el resultado es cero o es divisible entre siete, entonces el número inicial es divisible entre siete.
  5. Revisar si es divisible entre once: Mirando si la suma de los dígitos en posición par, menos la suma de los dígitos en posición impar da como resultado cero o es divisible entre once.
  6. Si ha pasado todos estos test, realizar un evento aleatorio cuya probabilidad de suceso sea \displaystyle\frac{1}{\ln 1000000}=0.07238241365. De este modo, correspondiente a el resultado obtenido, podrías decir que no sabes si es primo, pero es probable que sí, o es probable que no.

Bueno, es solo idea mía. A decir verdad, hoy dia tenemos muchas fuentes de información como para dejarlo al azar.

Deja un comentario.

Tu dirección de correo no será publicada.

*


A %d blogueros les gusta esto: