Wheel factorization

Wheel factorization is an improvement of the trial division method for integer factorization.
The trial division method consists of dividing the number to be factorized successively by the first integers (2, 3, 4, 5, ...) until finding a divisor. For wheel factorization, one starts from a small list of numbers, called the "basis" — generally the first few prime numbers; then one generates the list, called the "wheel", of the integers that are coprime with all numbers of the basis. Then to find the smallest divisor of the number to be factorized, one divides it successively by the numbers in the basis, and in the wheel.
With the basis {2, 3}, this method reduces the number of divisions to of the number necessary for trial division. Larger bases reduce this proportion even further; for example, with basis {2, 3, 5} to ; and with basis {2, 3, 5, 7} to .
A typical example.
With a given basis of the first few prime numbers {2, 3, 5}, the "first turn" of the wheel consists of: 
The second turn is obtained by adding 30, the product of the basis, to the numbers in the first turn. The third turn is obtained by adding 30 to the second turn, and so on.
For implementing the method, one may remark that the increments between two consecutive elements of the wheel, that is
remain the same after each turn.
The suggested implementation that follows uses an auxiliary function div("n", "k"), which tests whether "n" is evenly divisible by "k", and returns "true" in this case, "false" otherwise. In this implementation, the number to be factorized is "n", and the program returns the smallest divisor of "n" returning "n" itself if it is prime.
 if div("n", 2) = true then return 2
 if div("n", 3) = true then return 3
 if div("n", 5) = true then return 5
 "k" := 7; "i" := 0
 while "k" * "k" ≤ "n" do
 if div("n", "k") = true, then return "k"
 "k" := "k" + inc["i"]
 if "i" &lt; 7 then "i" := "i" + 1 else "i" := 0
 return "n"
For getting the complete factorization of an integer, the computation may be continued without restarting the wheel at the beginning. This leads to the following program for a complete factorization, where the function "add" adds its first argument at the end of the second argument, which must be a list.
 factors := [ ]
 while div("n", 2) = true do
 factors := add(2, factors)
 "n" := "n" / 2
 while div("n", 3) = true do
 factors := add(3, factors)
 "n" := "n" / 3
 while div("n", 5) = true do
 factors := add(5, factors)
 "n" := "n" / 5
 "k" := 7; "i" := 0
 while "k" * "k" ≤ "n" do
 if div("n", "k") = true then 
 add("k", factors)
 "n" := "n" / "k"
 else
 "k" := "k" + inc["i"]
 if "i" &lt; 7 then "i" := "i" + 1 else "i" := 0
 if "n" &gt; 1 then add("n", factors)
 return factors
Another presentation.
Wheel factorization is used for generating lists of mostly prime numbers from a simple mathematical formula and a much smaller list of the first prime numbers. These lists may then be used in trial division or sieves. Because not all the numbers in these lists are prime, doing so introduces inefficient redundant operations. However, the generators themselves require very little memory compared to keeping a pure list of prime numbers. The small list of initial prime numbers constitute complete parameters for the algorithm to generate the remainder of the list. These generators are referred to as wheels. While each wheel may generate an infinite list of numbers, past a certain point the numbers cease to be mostly prime.
The method may further be applied recursively as a prime number wheel sieve to generate more accurate wheels. 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 visualize the use of a factorization wheel, one may start by writing the natural numbers around circles as shown in the adjacent diagram. The number of spokes is chosen such that prime numbers will have a tendency to accumulate in a minority of the spokes.
Example.
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.&lt;br&gt; "xn" + 1 = 1 · 6 + 1 = 7.&lt;br&gt; ("x" + 1)"n" = (1 + 1) · 6 = 12.&lt;br&gt; Write 7 to 12 with 7 aligned with 1.
 1 2 3 4 5 6
 7 8 9 10 11 12
6. "x" = 2.&lt;br&gt; "xn" + 1 = 2 · 6 + 1 = 13.&lt;br&gt; ("x" + 1)"n" = (2 + 1) · 6 = 18.&lt;br&gt; Write 13 to 18.&lt;br&gt; 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 52. 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 enumerated 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 &gt; 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.
It is known that
where is Euler's constant.
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 formula_2 and formula_3 (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 :