CTK Insights

22 Oct

The Parabolic Sieve of Prime Numbers

Parabola y=x^2 has an easily verifiable property.

The segment joining points (-a,a^2) and (b,b^2) crosses y-axis in point (0,ab).

The equation of the segment is (y-a^2)/(b^2 -a^2)=(x+a)/b+a), from which y(0)=ab.

This may be a curious fact in its own right. What does it say? Taken at a face value, it simply shows a way to obtain the product of two numbers in the presence of a graph of parabola. But Yu. B. Matiyasevich and B. S. Stechkin have recognized that, if we restrict the consideration to the integers, the number so obtained will be composite (excluding of course the case where one of a or b equals 1.) It follows that by joining all points (-a,a^2) and (b,b^2), where a,b\gt 1, the only integer points (0,p) on y-axis that won't be crossed correspond to prime numbers p. (See also Etudes, and Catching Primes.)

A parabolic sieve of prime numbers - who would have thought!?

9 Responses to “The Parabolic Sieve of Prime Numbers”

  1. 1
    Dave Radcliffe Says:

    This article has caused me to realize something else about parabolas. If the point (-a,a^2) is fixed, and the point (b,b^2) moves at a constant horizontal speed, then the point (0, a*b) also moves at constant speed.

    So let's imagine that I'm a baseball player in the outfield, and the batter has hit a ball towards me. The ball is too far away for me to judge the distance. But if I am standing in the flight path of the baseball, then the ball should appear to be rising at a constant speed. Knowing this fact would help me to catch the ball. Am I thinking correctly?

  2. 2
    admin Says:

    While what you say is true for all parabolas and all view planes, the ability to catch the ball depends on your skills and - to be fully developed - may require years of exercise. There is one caveat though: for an inverted parabola, the ball will rise at constant speed, yes. But then at some point will reverse its direction and will be moving with a constant speed downwards. For your estimates, you may probably need to know when this reversal of direction takes place. Matiyasevich and Stechkin are mum on this point.

    This said, that the perceived vertical speed of a ball is constant is rather surprising.

  3. 3
    Dave Radcliffe Says:

    Here is a better way to phrase it. In order to make the catch, the outfielder should position himself so that the ball appears to be going straight up and the slope is increasing at a constant rate. Note that the slope continues to increase at the same rate as the ball is descending. I conjecture that this geometric fact is part of the mechanism that humans (and other animals?) use to predict the motion of projectiles.

  4. 4
    admin Says:

    Oops, David, you are right of course. Up to the point where you see the stars (and, perhaps, this is why you'll see them) the ball will appear rising. Beautiful.

  5. 5
    Matrix67: My Blog » Blog Archive » 用抛物线筛选质数 Says:

    [...] http://plus.maths.org/content/catching-primes http://www.mathteacherctk.com/blog/2011/10/the-parabolic-sieve-of-prime-numbers/ Posted in Brain Storm Tags: 质数, 函数, 数论Trackback: [...]

  6. 6
    Michael Hoppe Says:

    One may also notice that angle((-a,0), (0, ab), (b, 0)) is 90 degree.


  7. 7
    admin Says:

    Yes, indeed. Interesting.

  8. 8
    Carnival of Mathematics #83 - Teach Beside Me Says:

    [...] Bogomolny presents The Parabolic Sieve of Prime Numbers | CTK Insights posted at CTK [...]

  9. 9
    piazza biagio Says:

    Mentre i fisici sono alla ricerca della teoria del tutto: tutto spiegato da una singola formula; e i matematici non riescono ancora a dimostrare la congettura di Riemann, stabilire cioè una regola matematica che dimostri la logica nella distribuzione dei numeri primi, nella terra di Archimede un ingegnere ritiene di averla identificata, in maniera molto elementare. La scoperta non consiste nell’ avere trovato una formula o un’equazione capace di generare tutti i numeri primi e/o determinare la loro posizione (cardinalità) , ma un crivello molto più potente di quello di Eratostene che ha chiamato il crivello dell’ingegnere. Detto crivello consiste nello scrivere tutti i numeri interi in successione in una tabella le cui colonne ne contengono trenta; nelle 15 colonne pari (2, 4 ……,30) si scorgono tutti i numeri pari (8/30=50%); tra le 15 colonne dispari si individuano: quattro colonne (3a,9a,21a,27a) dove sono sistemati i composti del 3 (4/30=13,33%); tre colonne (5a,15a,25a) dove sono distribuiti i composti del 5 (3/30=10,00%); otto colonne (7a,11a,13a,17a,19a,23a,29a, dove si dispongono tutti i numeri primi ed i loro composti (8/30=26,67%), ad eccezione del 2, del 3 e del 5. (vedi tabella dei numeri naturali) L’algoritmo consente di trovare in maniera semplice i numeri composti che stanno sulle otto colonne e quindi, per esclusione ottenere i primi. Gli elementi costituenti ciascuna colonna sono in progressione aritmetica di ragione 30 e quindi coprimi. Queste otto colonne possono essere scritte sotto forma di progressioni aritmetiche del tipo 7+30k, in perfetta linea con il teorema di Dirichlet che afferma che una progressione aritmetica contiene infiniti numeri primi se e solo se la sua ragione e il suo primo valore sono coprimi (due numeri si dicono coprimi se non hanno fattori comuni); l'aritmetica dei Sumeri (IV sec. a.C.) aveva due cardini: il 10=2+3+5 e il 30=2*3*5.

Leave a Reply

4 + = twelve

© 2015 CTK Insights | Entries (RSS) and Comments (RSS)

Powered by Wordpress, design by Web4 Sudoku, based on Pinkline by GPS Gazette