lunes, 13 de marzo de 2017

1420. A parabolic sieve

    Pepe Chapuzas was drawing the graph of the funcion  y = x2  with the following values:


    (Values for  x = –1  and  x = 1  were skipped.) First, Pepe drew the points (red dots), so he got a beautiful parabola... After this, he matched by straight lines the red points on the 1st quadrant with the red points on the 2nd quadrant... Every line crossed the parabola axis at a natural number. If we went on getting red points by giving integer values to  x  (different to –1 and 1), then all the natural numbers on the parabola axis would be crossed out by these lines except the primes. (Here, the number 1 would be included among the primes and wouldn't be crossed out.) This parabola worked as Eratosthenes' sieve!



    Dear Teacher:
    This is Matiyasevich and Stechkin's sieve. And it's easy to explain its functioning...
    For every  m  and every  n  (natural numbers greater than 1), the straight line passing through the points  N(–n, n2)  and  M(m, m2)  (points of the parabola on different quadrants) is


y  =  (m2–n2)/(m+n) · (x+n) + n2 
y  =  (m–n) · (x+n) + n2

    And the intersection point between the straight line and the parabola axis is 


x = 0
y =  (mn) · n + n2 = m·n

    But  y = m·n  is a natural number and is not a prime. So, all the natural numbers except the primes are crossed out and this parabola is an authentic sieve for the primes.

No hay comentarios:

Publicar un comentario