## Geometric view of the Sieve of Eratosthenes

YouTube fast becomes a means of spreading math wonders. I was recently advised of a video posted at YouTube by Javier Torres Suárez. The video presents a step-by-step selection of dots in a triangular grid in such a manner that, wonderfully, the only rows of the grid that remain unchanged correspond to prime numbers.

The applet below provides an interactive simulation for the process. There is also extra functionality that may help explain the phenomenon.

The whole applet area clickable. The effect of pressing the left button while the cursor hovers over a dot depends on the combination of the three check boxes: *descendants*, *ancestors*, *siblings*. The meaning of the terms will be explained shortly. Pressing the button while the cursor is outside of the dots shows a triangular frame underlying a single step in the process associated with the row in which the button has been pressed.

The applet displays the final configuration obtained by the process of marking. Each step my be observed by clicking outside of any dot, as mentioned in the previous paragraph. Also, the inner dot markings can be **Clear**ed and the process recommenced with the **One step** button.

What if applet does not run? |

In the original video the process starts with an grid in which only the border dots are marked. On each step of the process a row is selected. That row is rotated 60° clockwise around its left end point and counterclockwise around its right end point. The row and its two rotations form an (upside down) equilateral triangle in which the legs inherit the dot configuration from the base. The process begins with row #2.

Dots in the grid may be affected by the dots above them. Thus a dot has a sequence of *ancestors* whose markings it receives. Each marked dot also passes the markings on to some dots - the descendants - below. Finally, some dots in a row are called siblings for a reason that will soon become clear.

To gain an insight into the workings of the algorithm, let's assign to each dot a pair of indices

The rotation of row #r around its left end point moves dot

(R) | L(r, k) = (r + k, k). |

This is because the dots (r, 0), (r, k), (r + k, 0), and

The counterclockwise rotation around the dot (r, r) is described by:

(L) | R(r, k) = (r + (r - k), r) = (2r - k, r). |

This is because the dots (r, k), (r, r), (2r - k, 2r - k), and

It may be worth noting that the lines parallel to the edges of the grid have the equations

{(r, k): k = const} and

{(r, k): r - k = const},

with the left and right edge being

One important property of the operators L and R is that they preserve the GCD - the greatest common divisor of the two components. Indeed,

GCD(r, k) = GCD(r + k, k) and

GCD(r, k) = GCD(r - k, r) and so also

GCD(r, k) = GCD(2r - k, r).

The *ancestor operators* are the inverses of L and R:

L^{-1}(r, k) = (r - k, k) and

R^{-1}(r, k) = (k, 2k - r).

So ancestors and descendants of a dot share the same GCD. The range of operator L^{-1} is

S_{L} = {(r, k): r - k ≥ k) = {(r, k): r ≥ 2k).

That of R^{-1} is given by

S_{R} = {(r, k): 0 ≤ 2k - r ≤ k) = {(r, k): k ≤ r ≤ 2k}.

The union of the two is the entire grid:

S_{R} ∪ S_{R} = {(r, k): k ≤ r}.

It would follow that all the dots on the grid have ancestors. The dots on the two edges have been marked from the outset and are thus of not interest. In particular, the three top dots - (0, 0), (0, 1), (1, 0) - are dropped from consideration. This is why in fact we have started from the row #2. Other than that there are no limitations: all other dots have ancestors. We are interested in finding the topmost progenitor(s) of a given dot

### Theorem

Let g = GCD(r, k). Then

- if g > 1, T(r, k) = { (0, g), (g, g) },
- if g = 1, T(r, k) = { (2, 1) }.

### Proof

The left ancestor operator L^{-1} applies to a dot ^{-1} applies whenever

In case where g = 1, we will be able to move further up unless

What this statement shows is that the dots

We define also *siblings* as the dots in a single row that have the same GCD. In practice this means that siblings come in the form

(r, nd), n = 0, 1, ...

where d is a divisor of r. The term seems natural but is not quite appropriate because the relation of being siblings in this sense is not transitive. For example in row 12 there are four groups of siblings. These are defined by GCD's equal to 2, 3, 4, 6. The dot (12, 6) belongs to three groups, biz., those with GCD 2, 3, 6 of which the first two have unrelated elements, e.g.,

The whole process is the Sieve of Eratosthenes in disguise. To see this imagine a modified process wherein we first apply the reflection steps to the even numbered rows, then to the rows with numbers divisible by 3, then those divisible by 5 and so on. The result will be exactly the same, except most of the marked dots will have been marked repeatedly.

## Related material
| |

## Sieves | |

| |

| |

| |

| |

| |

| |

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

64220328 |