¿Cómo generar números primos, es posible generar un número primo mediante una función?

Seguimos con el interesante tema de los números primos, esta vez toca uno de las cuestiones que más ha quebrado la cabeza, y es la posibilidad de poseer una exótica función en la que entrando un valor, nos aparezca el número primo con el número de cifras que queramos, eso evidentemente sería el sueño de los criptólogos y criptografos, y de algún sombrero negro, pero estamos lejos de conseguirlo para todos ellos.

Existen algunas funciones polinomiales con valores límite, fuera de ellos, no se garantiza la primalidad.

En este enlace http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html

podemos encontrar una gran cantidad de polinomios generadores, todos tienen validez limitada, no hay un polinomio que genere para cualquier n, un entero primo sin limitación 

 Algunos son capaces de generar hasta 57 números primos, con n desde 0 a 56.

Podemos tener la tentación de tomar una serie de números primos, por ejemplo los 100 primeros números primos, y los representamos, obtenemos la siguiente grafica

 Se ha ha usado el siguiente código en Mathematica para el representación gráfica (los ejes están a distinta escala)

 data = Table[{n, Prime[n]}, {n, 100}]; (* primeros np numeros primos*)
 ListPlot[data, AxesLabel -> {n, numero primo}]

Y la segunda tentación es la creer que vemos un patrón, claramente, que podemos generar un polinomio con el que podamos calcular un número primo  ??? se nos dilatan las pupilas y se nos acelera el pulso.

Vamo a usar otra herramienta de Mathematica, la función Interpolation, y calculamos la función de interpolación a trozos usando el código:

f = Interpolation[data];
Show[ListPlot[data, PlotStyle -> Red], Plot[f[x], {x, 1, np}]]




obtenemos la siguiente gráfica

 

 Aquí es donde nos ponemos más nerviosos, ya se nos acelera mas el pulso y comenzamos a sudar.

¿ que pasa con valores fuera del rango con el que hemos realizado el cálculo??

Vamos a ir probando, como  somos muy pillines usaremos la función PrimeQ, para realizar el test de primalidad.

Probamos con los 10 siguiente ya fuera del rango

For[i = 100, i <= 110, i++,
 Print[f[i], "  ", PrimeQ[f[i]]]
 ]

541  True
601  True, que miedo esto funciona, soy el nuevo Bernhard Riemann
729  False, mi gozo en un pozo, al tercero, es decir n=102, la pifiamos
 La trampa está en que  necesitamos conocer los números primos del intervalo para calcular la función de interpolación, fuera es tierra incognita

evidentemente no iba a funcionar, pero es un interesante ejercicio que creo que todo/as hemos intentado alguna vez.

Ya tenemos el reto de buscar funciones con las que podamos calcular números primos

Supongo que os queda la duda de ¿ Cómo los calcula Mathematica??.











 Evidentemente continuará...

La Música de los Números Primos

Los números primos son un auténtico incordio: aparecen donde quieren, sin previo aviso, de una forma aparentemente caótica, y sin seguir ningún tipo de pauta. Y lo peor del caso es que no se pueden ignorar: son la esencia de la aritmética y, hasta cierto punto, de toda la matemática.

Seguimos con los números primos, pero esta vez os pongo los enlaces de un interesante documental de Marcus du Sautoy (1965) Catedrático de Matemáticas de la Universidad de Oxford, ha sido profesor invitado en el Colege de France y la Ecole Normale Superieure de París, en el Max Plank Institut de Bonn entre otras.

Es un divulgador de las Matemáticas que usa un lenguaje entendible y ameno, ha realizado varios programas de televisión y ha publicado varios libros, de ese tema ya hablaremos

Os dejo tres interesante vídeos sobre los números primos cuyo título es "La música de los números primos", título análogo al de uno de sus libros

Esta es la épica historia de 3.000 años de alegrí­a y desesperación matemática, de luz deslumbrante y callejones sin salida. Marcus du Sautoy, Catedrático de Matemáticas de la Universidad de Oxford y uno de los cientí­ficos más prestigiosos de Inglaterra nos acerca al fascinante mundo de las matemáticas, a su belleza y a sus secretos.

Vídeo 1/3

Vídeo 2/3

Vídeo 3/3

Con respecto a su libro "La música de los números primos", en la introducción de la traducción al Castellano podemos leer:

"A los niños les enseñan en la escuela que los números primos sólo pueden dividirse por sí mismos y por la unidad. Lo que no les enseñan es que los números primos representan el misterio más fascinante al que nos enfrentamos en nuestra búsqueda del conocimiento. ¿Cómo predecir cuál va a ser el siguiente número primo de una serie? ¿Existe alguna fórmula para generar números primos?En 1859, el matemático alemán Bernhard Riemann planteó una hipótesis que apuntaba a la solución del antiguo enigma. Pero no consiguió demostrarla y el misterio no hizo más que aumentar. En este libro asombroso, Marcus du Sautoy nos cuenta la historia de los hombres excéntricos y brillantes que han buscado una solución para revolucionar ámbitos tan distintos como el comercio digital, la mecánica cuántica y la informática. El relato de Du Sautoy constituye una evocación maravillosa y emocionante del mundo de las matemáticas, de su belleza y sus secretos."

Es el libro que actualmente estoy leyendo y es asequible a un lector con conocimienos básicos de Matemática de Bachillerato, de vez en cuando te entran ganas de  tener a mano una calculadora (aunque no imprescindible para la lectura), es muy recomendable.

Por si os interesa os dejo un par de enlaces con información del libro

Acantilado

Casa del Libro

Os dejo también una entrevista que le realizó Eduard Punset en su programa Redes

Redes - Las simetrías del universo

NUMEROS PRIMOS EN BÚSQUEDA Y CAPTURA II

No hace mucho puse un post sobre el problema que puede ocasionar en USA, el disponer de un determinado número primo, el motivo por el que escribo esta entrada es uno de los problemas que posiblemente nos plantearan en nuestra vida académica, y ese problema es el de estimar la cantidad de números primos menores o iguales que uno dado.

Las primeras estimaciones nos remontan a Gauss y Legendre, que en su momento generaron controversia sobre quien fue el primero de los dos en estudiar la distribución de primos en un determinado intervalo.

Fue Gauss el primero en definir una fórmula para estimar dicho valor, con la siguiente expresión:

 

esta expresion no daría una estimación del número de primos menores o iguales a n, para n grandes se aleja de los datos reales, dando valores menores, se puede usar como cota inferior ¿?

Posteriormente Legendre publicó otra expresión similar:

menos elegante que la anterior, pero en su medida efectiva, se acerca más que la primera expresión de Gauss.

Posteriormente Gauss perfeccionó el método con la siguiente expresión para un número n.

 

Pero Gauss desarrolló otra expresión que denominó logaritmo integral Li(x), que tiene una expresión (integral claro) similar a la anterior

 

 y nos queda Riemann que nos da para otra entrada

 O dejo el código en MatLab de una función que realiza los cálculos, el código está lleno de comentarios explicativos, no se ha incluido el método del logaritmo integral.

 function [ gauss,legendre,gauss_2 ] = numeroprimos( n )
%numero de primos menores o iguales que n
%   nos da un valor aproximado, no es un valor exacto
clc % borrado de pantalla
% control del valor de la entrada del número
    if fix(n)~=n || n<=1
       fprintf('El valor introducido no es valido \n')
       fprintf('Introducir un valor entero positivo mayor que uno\n')
       return
    end
% calculos
gauss=fix(n/log(n)); % segun Gauss
legendre=fix(n/(log(n)-1.08366)); % segun Legendre
% segundo criterio de Gauss o de los logaritmos
gauss_2=0; % valor inicial
for i=2:n
   gauss_2= gauss_2+1/log(i);
end

% impresion de resultados
fprintf('Para el primer criterio de Gauss \n')
fprintf('Numero de primos menores o iguales a %d es %d \n',n,gauss)
fprintf('Para el segundo criterio de Gauss \n')
fprintf('Numero de primos menores o iguales a %d es %d \n',n,fix(gauss_2))
fprintf('Para el metodo de Legendre \n')
fprintf('Numero de primos menores o iguales a %d es %d \n',n,legendre)
 
end