martes, 24 de mayo de 2011

Fórmulas que atraen primos

Quienes somos aficionados a los números aprendemos pronto que no hay fórmulas elementales que engendren números primos, a pesar de que muchas mentes valiosas las buscaron. No obstante, hay fórmulas que, al aplicarlas, sus resultados presentan más probabilidad de ser primos que los elegidos al azar. Podemos pensar en las fórmulas clásicas, que después resultaron fallidas, como n2 + n + 17 y n2 - n + 41.

Si engendramos un conjunto de números con estas fórmulas y contamos los primos, nos resulta un nivel destacable. Lo hemos programado con hoja de cálculo, obteniendo:
Para n2 + n + 17:
Números primos en los primeros 500 resultados: 213, con una proporción del 43%
Números primos en los primeros 500 naturales: 95, un 19%
Para n2 - n + 41:
Números primos en los primeros 500 resultados: 326, con una proporción del 65%

¡Quienes inventaron estas fórmulas no iban muy descaminados!

Acabo de leer otra en Futility Closet: x2 – 2999x + 2248541 produce 80 primos desde x = 1460 a 1539.

En realidad, todas estas fórmulas y otras similares están contenidas como diagonales en la Espiral de Ulam. En esta dirección puedes divertirte un poco con algunas consideraciones sobre ella:
http://hojamat.es/sindecimales/divisibilidad/propuestas/rutas/htm/ulam.htm

La imagen representa el conjunto de los resultados de n2 + n + 17 en dicha espiral. Los números primos son los elementos de color verde, que son los que predominan.

Como ejercicio y tema de reflexión propondremos otra fórmula que aumenta bastante la probabilidad de encontrar primos entre sus resultados:

Toma dos números a y b primos entre sí y mayores que 2. Con ellos forma la expresión (a-1)*(b-1)-1 ¿Qué podemos decir de los factores primos de esa expresión?

Cuando lo averigües intenta generar muchos pares del tipo a y b y cuenta cuántos primos se engendran con la fórmula. Unas veces se producirán y otras no:

Si a=39 y b=55, primos entre sí, resulta (39-1)(55-1)-1 = 2051 que no es primo, sino semiprimo.
Pero si a=15 y b=64, resulta 881 que sí es primo.

¿Será alta la proporción? ¿Por qué?

Te dejamos unas estadísticas para convencerte. Hemos elegido pares de coprimos y les hemos aplicado esta fórmula. Después comparamos con la lista de números naturales, mediante la función “primos hasta N”

Cota para a y b
Pares resultantes
Primos encontrados
Proporción
Proporción en naturales
50
700
362
0,52
0,18
100
2895
1265
0,44
0,14
200
11933
4416
0,37
0,12

Se comprueba que la proporción es del orden del triple de la usual entre números no sometidos a ninguna fórmula.

Queda para tu estudio la causa de esto.

Si cambiáramos la expresión (a-1)*(b-1)-1 por (a-1)*(b-1)+1 las estadísticas siguen siendo buenas, aunque del orden del doble de lo normal. Otra cuestión que puedes intentar explicar.

Cota para a y b
Pares resultantes
Primos encontrados
Proporción
Proporción en naturales
50
700
362
0,52
0,18
100
2895
1265
0,44
0,14
200
11933
4416
0,37
0,12

En vista de estos resultados nos podíamos animar a buscar primos gemelos con las dos expresiones y compararlos con la función “Primos gemelos hasta N”. También es destacable el incremento de la proporción.

Cota para a y b
Pares resultantes
Primos encontrados
Proporción
Proporción en naturales
50
700
362
0,52
0,18
100
2895
1265
0,44
0,14
200
11933
4416
0,37
0,12


Si se te ocurren otras expresiones similares nos lo puedes contar.