A Geometric Sieve for the Prime Numbers

In the time before computers (BC) various ingenious devices were invented for aiding the extensive calculations required in astronomy, navigation and commerce. In addition to calculators and logarithms, several nomograms were devised for specific applications, for example in meteorology and surveying.

MS-Sieve-Detail

A Nomogram for Multiplication

The graph of a parabola ${y=x^2}$ can be used as a nomogram to aid in the multiplication of two numbers. Suppose we wish to multiply ${x_1}$ by ${x_2}$ . We proceed thus:

• Mark the points ${(-x_1,x_1^2)}$ and ${(+x_2,x_2^2)}$ on the graph.
• Draw the straight line joining these points.
• The ordinate where this line crosses the ${y}$ -axis is ${x_1 x_2}$ .

Parabola y=x^2 serves as a nomogram for multiplication.

The proof of this assertion is simple, involving only the equation for a straight line. The line through two points ${(-x_1,x_1^2)}$ and ${(+x_2,x_2^2)}$ is

$\displaystyle \frac{y-x_1^2}{x_2^2-x_1^2} = \frac{x+x_1}{x_2+x_1}$

Setting ${x=0}$ in this equation gives us ${y = x_1 x_2}$ , the required product. Thus, armed with the nomogram we can, in principle, find the product of any two numbers.

Another application of the parabolic nomogram is to find the geometric mean of two numbers. Normally, this involves calculation of a square root, but the answer can easily be read off the diagram. Given two numbers ${m}$ and ${n}$ , draw the horizontal lines through the points ${(0,m)}$ and ${(0,n)}$ . They will intersect the parabola at ${(\pm\sqrt{m},m)}$ and ${(\pm\sqrt{n},n)}$ , The line between opposite points of intersection then cuts the ${y}$ -axis at the point ${y=\sqrt{mn}}$ , the required geometric mean.

Find Prime Numbers with the Nomogram

Image of the MS Sieve, from the website of Yuri Matiyasevich

It is clear that if ${m = x_1}$ and ${n= x_2}$ are whole numbers, their product is also an integer. For any ${m}$ and ${n}$ there is a line from ${(-m,m^2)}$ to ${(n,n^2)}$ that passes through the point ${(0,mn)}$ . Taking all numbers ${m,n\in\mathbb{N}}$ with ${m\ge2}$ and ${n\ge2}$ , all the composite numbers in ${\mathbb{N}}$ are picked out by this process. The only points that are not on any of the lines are the prime numbers. The resulting diagram is a sieve, a geometric diagram eliminating all the composite numbers and isolating all the primes.

The image of the sieve in the Figure above is taken from the website of mathematician Yuri Matiyasevich. The geometric diagram is called the Matiyasevich-Stechkin sieve. Yuri Matiyasevich devised it and credited his teacher Boris Stechkin for devising the multiplication nomogram, although this must have been well known centuries ago.

By convention, the parabola in the MS-Sieve is turned clockwise through 90 degrees and we draw ${x=y^2}$ or ${y=\pm\sqrt{x}}$ . Now we use the idea of the Sieve of Eratosthenes. For all integers ${n}$ greater than ${2}$ or less than ${-2}$ , we mark the points ${(n^2,n)}$ and ${(n^2,-n)}$ on the parabola. Joining ${(2^2,2)}$ to all ${(n^2,-n)}$ , all the even numbers greater than 2 are crossed out. Next, joining ${(3^2,3)}$ to all ${(n^2,-n)}$ with ${n\ge3}$ , all the multiples of 3 are crossed out.