Wheel factorization

File:Wheel factorization-n=30.svg

Wheel factorization with n=2x3x5=30. No primes will occur in the yellow areas.

Wheel factorization is a method for performing a preliminary reduction in the number of potential primes from the initial set of all natural numbers 2 and greater; possibly prior to passing the result list of potential primes to the Sieve of Eratosthenes or other sieve that separates prime numbers from composites, but may further be used as a prime number wheel sieve in its own right by recursively applying the factorization wheel generation algorithm. Much definitive work on wheel factorization, sieves using wheel factorization, and wheel sieve, was done by Paul Pritchard in formulating a series of different algorithms. To demonstrate the use of the factorization wheel graphically, one starts by writing the natural numbers around circles as shown in the adjacent diagram. Prime numbers in the innermost circle have their multiples in similar positions as themselves in the other circles, forming spokes of primes and their multiples. Multiples of the prime numbers in the innermost circle form spokes of composite numbers in the outer circles.

Sample graphical procedure

1. Find the first few prime numbers to form the basis of the factorization wheel. They are known or perhaps determined from previous applications of smaller factorization wheels or by quickly finding them using the Sieve of Eratosthenes.
2. Multiply the base prime numbers together to give the result n which is the circumference of the factorization wheel.
3. Write the numbers 1 to n in a circle. This will be the inner-most circle representing one rotation of the wheel.
4. From the numbers 1 to n in the innermost circle, strike off all multiples of the base primes from step one as applied in step 2. This composite number elimination can be accomplished either by use of a sieve such as the Sieve of Eratosthenes or as the result of applications of smaller factorization wheels.
5. Taking x to be the number of circles written so far, continue to write xn + 1 to xn + n in concentric circles around the inner-most circle, such that xn + 1 is in the same position as (x − 1)n + 1.
6. Repeat step 5 until the largest rotation circle spans the largest number to be tested for primality.
7. Strike off the number 1.
8. Strike off the spokes of the prime numbers as found in step 1 and applied in step 2 in all outer circles without striking off the prime numbers in the inner-most circle (in circle 1).
9. Strike off the spokes of all multiples of prime numbers struck from the inner circle 1 in step 4 in the same way as striking off the spokes of the base primes in step 8.
10. The remaining numbers in the wheel are mostly prime numbers (they are collectively called "relatively" prime). Use other methods such as the Sieve of Eratosthenes or further application of larger factorization wheels to remove the remaining non-primes.

Example

File:Wheel factorization-n=6.svg

Wheel factorization with n=2x3=6

1. Find the first 2 prime numbers: 2 and 3.

2. n = 2 × 3 = 6

3.

 1  2  3  4  5  6

4. strike off factors of 2 and 3 which are 4 and 6 as factors of 2; 6 as the only factor of 3 is already stricken:

 1  2  3  4  5  6

5. x = 1.
xn + 1 = 1 · 6 + 1 = 7.
(x + 1)n = (1 + 1) · 6 = 12.
Write 7 to 12 with 7 aligned with 1.

 1  2  3  4  5  6
 7  8  9 10 11 12

6. x = 2.
xn + 1 = 2 · 6 + 1 = 13.
(x + 1)n = (2 + 1) · 6 = 18.
Write 13 to 18.
Repeat for the next few lines.

 1  2  3  4  5  6
 7  8  9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29 30

7 and 8. Sieving

 1  2  3  4  5  6
 7  8  9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29 30

9. Sieving

 1  2  3  4  5  6
 7  8  9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29 30

10. The resulting list contains a non-prime number of 25 which is 5². Use other methods such as a sieve to eliminate it to arrive at

2 3 5 7 11 13 17 19 23 29

Note that by using exactly the next prime number of 5 wheel cycles and eliminating the multiple(s) of that prime (and only that prime) from the resulting list, we have obtained the base wheel as per step 4 for a factorization wheel with base primes of 2, 3, and 5; this is one wheel in advance of the previous 2/3 factorization wheel. One could then follow the steps to step 10 using the next succeeding prime of 7 cycles and only eliminating the multiples of 7 from the resulting list in step 10 (leaving some "relative" primes in this case and all successive cases - i.e some not true fully qualified primes), to get the next further advanced wheel, recursively repeating the steps as necessary to get successively larger wheels.

Analysis and computer implementation

Formally, the method makes use of the following insights: First, that the set of base primes unioned with its (infinite) set of coprimes is a superset of the primes. Second, that the infinite set of coprimes can be ennumerated easily from the coprimes to the base set between 2 and the base set product. (Note that 1 requires special handling.)

As seen in the example above, the result of repeated applications of the above recursive procedure from steps 4 to 10 can be a wheel list which spans any desired sieving range (to which it can be truncated) and the resulting list then includes only the multiples of primes higher than one past the last used base primes.

Note that once a wheel spans the desired upper limit of the sieving range, one can stop generating further wheels and use the information in that wheel to cull the remaining composite numbers from that last wheel list using a Sieve of Eratosthenes type technique but using the gap pattern inherent to the wheel to avoid redundant culls; some optimizations may be able to be made based on the fact that (will be proven in the next section) that there will be no repeat culling of any composite number: each remaining composite will be culled exactly once. Alternatively, one can continue to generate truncated wheel lists using primes up to the square root of the desired sieve range, in which case all remaining number representations in the wheel will be prime; however, although this method is as efficient as to never culling composite numbers more than once, it loses much time external to the normally considered culling operations in processing the successive wheel sweeps so as to take much longer. The elimination of composite numbers by a factorization wheel is based on the following: Given a number k > n, we know that k is not prime if k mod n and n are not relatively prime. From that, the fraction of numbers that the wheel sieve eliminates can be determined (although not all need be physically struck off; many can be culled automatically in the operations of copying of lesser wheels to greater wheels) as 1 - phi (n) / n, which is also the efficiency of the sieve.

Since it is known

$\lim\inf\frac{\varphi(n)}{n}\log\log n = e^{-\gamma}.$

where γ is Euler's constant,   γ = 0.577215665...,   e^−γ = 0.56145948... . Thus phi(n) / n goes to zero slowly as n increases to infinity and it can be seen that this efficiency rises very slowly to 100% for infinitely large n. From the properties of phi, it can easily be seen that the most efficient sieve smaller than x is the one where $n = p_1 p_2 ... p_i < x$ and $n * p_{i+1} >= x$ (i.e wheel generation can stop when the last wheel passes or has a sufficient circumference to include the highest number in the sieving range).

To be of maximum use on a computer, we want the numbers that are smaller than n and relatively prime to it as a set. Using a few observations, the set can easily be generated :

1. Start with $S_1 = \{1\}$, which is the set for $n=1$ with 2 as the first prime. This initial set means that all numbers starting at two up are included as "relative" primes as the circumference of the wheel is 1.
2. Following sets are $S_2 = \{1\}$ which means that it starts at 3 for all odd numbers with the factors of 2 eliminated (circumference of 2), $S_6 = \{1,5\}$ has the factors of 2 and 3 eliminated (circumference of 6) as for the initial base wheel in the example above and so on.
3. Let $S_n + k$ be the set where k has been added to each element of $S_n$.
4. Then $S_{n p_{i+1}} = F_{p_{i + 1}} [S_n \cup S_n + n \cup S_n + 2n \cup ... \cup S_n + n (p_{i+1} - 1)]$ where $F_x$ represents the operation of removing all multiples of x.
5. 1 and $p_{i+1}$ will be the two smallest of $S_n$ when $n > 2$ removing the need to compute prime numbers separately although the algorithm does need to keep a record of all eliminated base primes which are no longer included in the succeeding sets.
6. All sets where the circumference n > 2 are symmetrical around $n / 2$, reducing storage requirements. The following algorithm does not use this fact, but it is based on the fact that the gaps between successive numbers in each set are symmetrical around the half way point.

See also

• Sieve of Sundaram
• Sieve theory

External links

• Wheel Factorization
• Improved Incremental Prime Number Sieves by Paul Pritchard