Criba de la Parábola

Descargar como Notebook

La criba de Eratóstenes es un método muy conocido para hallar los números primos menores que un cierto número K dado inicialmente. Su funcionamiento es muy sencillo :
Se comienza escribiendo los números desde el 2 hasta K.
Se marca el 2 como número primo y a continuación se tachan todos los múltiplos de 2.
Después se marca como primo el primer número no tachado que nos encontremos, el 3 en este caso, y se tachan todos los múltiplos de éste que no estuvieran tachados ya.
Y así sucesivamente.
Los números marcados son exactamente todos los números primos que hay entre 2 y K.

Veamoslo en esta criba creada por Stephen Wolfram y publicado en demonstrations.wolfram.com

Manipulate[
 ArrayPlot[Partition[Array[PrimeQ, n^2], n], Mesh -> mesh, 
  MeshStyle -> Green, 
  ColorRules -> {True -> Lighter[Red, .4], 
    False -> Lighter[Blue, .9]}, 
  Epilog -> 
   If[labs, 
    Table[Text[Style[(i - 1) n + j, 200/n], {j - 1, n - i} + 1/2], {i,
       n}, {j, n}], {}]],
 {{n, 10, "table size"}, 2, 50, 
  1}, Delimiter, {{labs, n < 20, "show numbers"}, {True, 
   False}}, {{mesh, True, "show mesh"}, {True, False}}]

 Pero esta criba no es ni mucho menos el único método de este tipo para encontrar los números primos más pequeños que un número dado. Existen otros métodos aritméticos, aunque es cierto que en ocasiones se tratan de variantes de la criba de Eratóstenes. Pero existe uno geométrico muy curioso e interesante, que podemos denominar la criba de la parábola. Los creadores de esta criba de la parábola fueron los matemáticos rusos Yuri Matiyasevich y Boris Stechkin, y el funcionamiento de la misma es el siguiente :
Representamos gráficamente una parábola cuyo eje sea el eje X, nos puede valer 2x=y^2:

Para cada número natural del 2 en adelante que sea un cuadrado perfecto (4, 9, 16, 25, \[Ellipsis]) marcamos los puntos en los que la recta perpendicular al eje X que pasa por él corta a la parábola. Hay uno por encima del eje X y otro por debajo.

Ahora unimos todos los puntos que han quedado marcados por encima del eje X con todos los de abajo, se afirma que los únicos valores enteros sobre el eje X por los cuales no pasa ningún segmento corresponden a los números primos.

En Mathematica

puntos = 10;
pa = Table[{n^2, Sqrt[2 n^2]}, {n, 2, puntos, 1}];
pb = Table[{n^2, -Sqrt[2 n^2]}, {n, 2, puntos, 1}];
ticks = Table[{Prime[i], Prime[i]}, {i, 30}];
puntoprimo = Table[{Prime[i], 0}, {i, 30}];
Show[Graphics[
  Line@Flatten[
    Table[{pa[[i]], pb[[j]]}, {i, 1, puntos - 1}, {j, 1, puntos - 1}],
     1], Axes -> True, Ticks -> {ticks, None}], 
 Graphics[{PointSize[Large], Pink, Point[puntoprimo]}], 
 ContourPlot[2 x == y^2, {x, 0, Prime[30]}, {y, -20, 20}], 
 ListPlot[pa, PlotStyle -> Directive[PointSize[Large], Red]], 
 ListPlot[pb, PlotStyle -> Directive[PointSize[Large], Red]]]

Propuesta

Demostrar la veracidad del funcionamiento de la criba de la parábola.