Sieve of Locke - A continuous infinite prime sieve

There are mainly two ways of finding prime numbers, sieves and trial division. Sieves are started from the lowest known prime. By removing composites, multiples of the known primes, new primes are reveiled. With trial division it is possible to investigate any natural number by checking if there are any smaller number that can divide the investigated one. There are also algorithms using some combination of sieve and trial division. One such algorithm is wheel factorization that first reduces the amount of possible prime candidates by pointing out composites and then uses trial division on remaining candidates.

With the above in mind Sieve of Locke is a sieve and nothing else.

Basic sieves, as Sieve of Eratosthenes find primes up to any given limit . The limit is needed for the algorithms to work. For Sieve of Locke no such limit is needed. By using the pattern each prime creates Sieve of Locke operate continuously on one prime at a time without any upper limit.

Overview

A prime number is a natural number that has exactly two distinct natural number divisors: the number 1 and itself. These are the steps to find prime numbers with Sieve of Locke:

First uninvestigated number is a prime, c (current prime)
Remove composites for c by
1. add c to list of active primes
2. for each active prime, a,
  within the pattern of a,
  remove composites with respect to c
Repeat from 1

Primorial: Primorial is the product of all prime numbers up to a specified prime (p) and denoted p#.
Pattern: Each prime (p) creates a pattern that starts from p + 1 and ends at p + p#.
Active primes: A prime (a) is active for current prime (c), meaning that a and c as factors will produce a product that is a valid composite in the pattern of a, within a <= c <= previous a# + 1.
Removal of composites: Composite in the pattern of a is the product from any combination of active primes where as a is the smallest prime and c is one of the factors and the product is <= a + a#.

The main idea is, for each prime, remove composites with respect to the newly found prime. That way the next number is prime. When all composites for a pattern is found, the corresponding prime is no longer active and thues removed from the calculation. This ensures that composites are only found once.

Primorial

Primorial is the product of all primes up to a specified prime. OEIS, the on-line encyclopedia of integer sequences, has two different definitions;

A002110: Primorial numbers (first definition): product of first n primes. Sometimes written prime(n)#.
A034386: Primorial numbers (second definition): n# = product of primes <= n.

Sieve of Locke uses the second definition which specifies the highest prime to include. Example:

7# = 1 * 2 * 3 * 5 * 7 = 210

Prime patterns

Each prime (p), one at a time, creates a pattern. The pattern starts at p + 1 and ends at p + p#. Composites within the pattern are, partly composites found related to previous patterns, and partly composites found as products of p together with itself and/or higher primes. When the composites are removed the pattern can be seen as the distance between remaining uninvestigated numbers.

Examples of the first short patterns:

Pattern 2: 3, 4, (5, 6,) ...

Pattern 3: 4, 5, 6, 7, 8, 9,
        ( 10, 11, 12, 13, 14, 15,) ...

Pattern 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, 31, 32, 33, 34,
             35, ( 36, 37, ...

For pattern 2, (2 * 2) 4 is marked as composite. The distance between remaining uninvestigated numbers are 2. This it true for the pattern of 2 infinitely.

For pattern 3, (3 * 3) 9 is marked as composite. The distance between remaining uninvestigated numbers are 2 and 4. This is true for the pattern of 3 infinitely.

For pattern 5, (5 * 5) 25 and (5 * 7) 35 are marked as composites. Note that 35 is marked as composite due to 5 * 7, as 7 will become a prime. From a strict sieve point of view it is still not known whether 7 actually is a prime or not. For larger patterns this will become an issue that needs to be addressed. To investigate values with trial division before using them for composite calculation would break the idea of a sieve. Instead the concept of active primes is added.

Active primes

Composites related to a prime pattern for a specific prime (p) has a limited number of possible factors. One factor is always p itself and by that the highest factor to multiply with without exceeding the patterns top boundery will be previous p# + 1.

p * x <= p + p#
x <= (p + p#) / p
x <= 1 + previous p#

This means that previous p# + 1 is the highest possible factor for a pattern. Examples:

Pattern 2: 1# + 1 = 2
Pattern 3: 2# + 1 = 3
Pattern 5: 3# + 1 = 7

That is, factors for composites related to the pattern of prime (p) must be within the span p to previous p# + 1. With this knowledge composites can be calculated after the point when a number is known to be prime.

Finding composites

Composites related to the pattern of current prime (c) will have two or more factors in the range

a <= c <= previous a# + 1

whereas a is always one of the factors. Calculating composites for the complete pattern of c would require the knowledge of all primes up to previous a# + 1 at time for calculation. As stated is section prime patterns that is not known standing at c. What is known is that when composites are removed, using all primes up to and including c, the next uninvestigated number is a prime. The purpose of active primes is to know which primes are needed as factors to calculate composites only once.

Here is a step by step example with more thouroughly explanations starting at 2:

c = 2. 2 is prime. Add 2 to active primes.

2 * 2 = 4

Composite 4 found. Pattern top for 2 (4) is reached. Therefor 2 is no longer an active prime.

c = 3. 3 is prime. Add 3 to active primes.

3 * 3 = 9

Composite 9 found. Pattern top for 3 (9) is reached. Therefor 3 is no longer active.

c = 5. 5 is prime. Add 5 to active primes.

5 * 5 = 25
5 * 5 * 5 = 125

Composite 25 found. 125 exceeds pattern top (35), so all possible combinations within the pattern of 5 this far are handled.

c = 7. 7 is prime. Add 7 to active primes. Now both 5 and 7 are listed as active primes. Investigate if 5 is still active. 3# + 1 (7) = 7, so 5 is still active.

7 * 5 = 35

Composite 35 for pattern 5 is found. Pattern top for 5 (35) is reached. Therefor 5 is no longer active.

7 * 7 = 49
7 * 7 * 7 = 343

Composite 49 found. 343 exceeds pattern top (217)

c = 11. 11 is prime. Active primes 7 and 11. 5# + 1 (31) > 11, so 7 is still active.

11 * 7 = 77

Composite 77 for pattern 7 is found. Other combinations of 7 and 11 will exceed pattern top for 7 (217).

11 * 11 = 121
11 * 11 * 11 = 1331
11 * 11 * 11 * 11 = 14641

Composites 121 and 1331 found. 14641 exceeds pattern top (2321)

c = 13. 13 is prime. Active primes 7, 11, and 13. 5# + 1 (31) > 13, so 7 is still active.

And so on...

First prime number

While most modern literature on prime numbers states that 1 is not prime, some older definitions actually refer to 1 as prime. (Help with referenses are appreciated.) Sieve of Locke includes the complete range of natural numbers and claims that 1 is a prime.


    c = 1 =>

    pattern start: p + 1; 1 + 1 = 2

    pattern stop: p + p# ; 1 + 1 = 2

    remove composites: 1 is active as c <= previous p# + 1; 1 <= 2.

    1 * 1 = 1; 1 is not within the pattern of 1, so no composites removed.

Contact

For questions, please feel free to send an email to primes@locke.se.

Version: 0.0.1