User:Oluckyman/sandbox

Geometric model

Generating successive wheels up to $W_{3}$

At the heart of the sieve of Pritchard is an algorithm for building successive wheels. It has a simple geometric model as follows:

1. Start with a circle of circumference 1 with a mark at 1
2. To generate the next wheel:
   1. Go around the wheel and find (the distance to) the first mark after 1; call it p
   2. Create a new circle with p times the circumference of the current wheel
   3. Roll the current wheel around the new circle, marking it where a mark touches it
   4. Magnify the current wheel by p and remove the marks that coincide

Note that for the first 2 iterations it is necessary to continue round the circle until 1 is reached again.

The first circle represents $W_{0}=\{1\}$, and successive circles represent wheels $W_{1},W_{2},...$. The animation on the right shows this model in action up to $W_{3}$.

It is apparent from the model that wheels are symmetric. This is because $P_{k}-w$ is not divisible by one of the first $k$ primes if and only if $w$ is not so divisible. It is possible to exploit this to avoid processing some composites, but at the cost of a more complex algorithm.