Description
For a chosen number (usually no larger than 4 or 5), the first ' primes determine the specific way to generate a sequence of natural numbers which are all known in advance to be coprime with these primes; that is, they are all known to not be multiples of any of these primes. This method can thus be used for an improvement of the trial division method forIntroduction
Natural numbers from 1 and up are enumerated by repeated addition of 1: : Considered by spans of two numbers each, they are enumerated by repeated additions of 2: : Every second number thus generated will be even. Thus odds are generated by the repeated additions of 2: : Considered by spans of three numbers each, they are enumerated by repeated additions of 23 = 6: : Every second number in these triplets will be a multiple of 3, because numbers of the form 3 + 6k are all odd multiples of 3. Thus all the numbers coprime with the first two primes (2 and 3) will be generated by repeated additions of 6, starting from : : The ''same'' sequence can be generated by repeated additions of 235 = 30, turning each ''five'' consecutive spans, of ''two'' numbers each, into one joined span of ''ten'' numbers: : Out of each ten of these 6-coprime numbers, two are multiples of 5, thus the remaining eight will be 30-coprime: : This is naturally generalized. The above showcases first three wheels: * (containing 1 = 2 − 1 number) with the "circumference" of 2 for generating the sequence of 2-coprimes by repeated addition of 2; * (containing 2 = (2 − 1)(3 − 1) numbers) with the "circumference" of 23 = 6, for generating the sequence of 6-coprime numbers by repeated additions of 6; * (containing 8 = (2−1)(3−1)(5−1) numbers) with the "circumference" of 235 = 30, for generating the sequence of 30-coprime numbers by repeated additions of 30; etc. Another representation of these wheels is by turning a wheel's numbers, as seen above, into a ''circular list'' of the ''differences'' between the consecutive numbers, and then generating the sequence starting from 1 by repeatedly adding these increments one after another to the last generated number, indefinitely. This is the closest it comes to the ''rolling the wheel'' metaphor. For instance, this turns into , and then the sequence is generated as : ''n''=1; ''n''+6=7; ''n''+4=11; ''n''+2=13; ''n''+4=17; ''n''+2=19; ''n''+4=23; ''n''+6=29; ''n''+2=31; ''n''+6=37; ''n''+4=41; ''n''+2=43; etc.A typical example
With a given basis of the first 3 prime numbers , 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 , which tests whether is evenly divisible by , and returns ''true'' in this case and ''false'' otherwise. In this implementation, the number to be factorized is , and the program returns the smallest divisor of returning 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'' < 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 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'' < 7 then ''i'' := ''i'' + 1 else ''i'' := 0 if ''n'' > 1 then add(''n'', factors) return factorsAnother presentation
Wheel factorization is used for generating lists of mostlySample graphical procedure
# 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 theExample
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 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 through 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. 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) 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 cull 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 , we know that is not prime if and 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 , which is also the efficiency of the sieve. It is known that : where is Euler's constant. Thus goes to zero slowly as increases to infinity, and it can be seen that this efficiency rises very slowly to 100% for infinitely large . From the properties of , it can easily be seen that the most efficient sieve smaller than is the one where and (that is, 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 and relatively prime to it as a set. Using a few observations, the set can easily be generated: # Start with , which is the set for 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. # The following sets are , which means that it starts at 3 for all odd numbers with the factors of 2 eliminated (circumference of 2), has the factors of 2 and 3 eliminated (circumference of 6) as for the initial base wheel in the example above, and so on. # Let be the set where has been added to each element of . # Then , where represents the operation of removing all multiples of . # 1 and will be the two smallest of when , 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. # All sets where the circumference are symmetrical around , 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 halfway point.See also
* Sieve of Sundaram * Sieve of Atkin * Sieve of Pritchard *References
External links