Almost everyone will agree that literacy is essential - everyone should be able to read and write. In a modern society, basic math and science skills are just as important! This page offers a few resources and links in this area...
Patterns in primes
Enhancement of the Sieve of Eratosthenes
A short note describing simple patterns in prime numbers, which can be used to generate primes in a manner reminiscent of the Sieve of Eratosthenes.
Like many, I dabble occasionally in number theory, among other things with prime numbers. Recently, while working on a totally unrelated problem, I came across what appears to be a very simple pattern in the distribution of primes. Given the prime numbers through N, this pattern can be used to identify all primes lying between N and 2N.
While the method is quite simple, I have not seen it described elsewhere; hence, I hope it will be of interest. Without further ado, here is the method:
Choose N such that N is the product of powers of small primes (example: 22 * 3 = 12). Write the numbers from 1 to N across the page from left to right, identifying the primes. Then write the numbers from N+1 to 2N-1 across the page from right to left, so that N+1 appears underneath N-1.
All numbers in the second row that appear underneath primes in the first row are candidate primes. So too is the number 2N-1 appearing under the number 1. From these candidates, remove those numbers appearing underneath the prime factors of N. In the simplest case, all remaining numbers are prime. Here is an example using N = 12:
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
↓ |
× |
× |
↓ |
↓ |
↓ |
||||||
|
23 |
22 |
21 |
20 |
19 |
18 |
17 |
16 |
15 |
14 |
13 |
This shows rather neatly how primes become more widely spaced as their values increase; in this example, there is one fewer prime between 13 and 24 than there is between 1 and 12.
Now, let P be the smallest prime that is not a factor of N (in this example: 5). as long as P2 > 2N then this simple method works. Unfortunately, it quickly becomes impossible to meet this restriction. For example: N = 30 = 2 * 3 * 5, but 72 < 60. In this case, 49 will appears as a candidate prime, even though it is composite.
In general, we must add two new rules, one to add additional candidate primes and one to eliminate candidates. Let D be the product of powers of primes that are not factors of N.
- If D < N then the number appearing underneath D is a candidate prime.
- if D > N and D < 2N then D appears as a candidate prime, but is actually composite.
As an example, take N = 60 = 22 * 3 * 5. In this case, 7*7, 7*11, 7*13 and 7*17 are all less than 2N; hence all four must be dealt with using the two rules above. Here are the relevant sequences, with these four numbers in bold:
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
… |
28 |
29 |
30 |
31 |
… |
41 |
42 |
43 |
44 |
… |
48 |
49 |
50 |
… |
58 |
59 |
60 |
|
× |
× |
× |
× |
↓ |
× |
↓ |
↓ |
× |
↓ |
↓ |
||||||||||||||
|
119 |
118 |
117 |
116 |
115 |
114 |
113 |
… |
92 |
91 |
90 |
89 |
… |
79 |
78 |
77 |
76 |
… |
72 |
71 |
70 |
… |
62 |
61 |
Finally, to use this method to generate primes, one must define a sequence of values of N so that each value in the sequence Ni is less than or equal to twice its predecessor Ni-1. To reduce the number of exceptions, one wants to have as many prime factors as possible for each factor of N. This means that the sequence should contain, for example, 6 (2*3), 30 (2*3*5), 210 (2*3*5*7) and so forth, adding "filler" values as needed to keep successive values within a factor of 2 of each other. This is most simply done by adding powers of 2. Hence, one generates the sequence {3, 6, 12, 24, 30, 60, 120, 210, …}. At each step, one identifies all missing primes between 2Ni-1 and 2Ni.
How does this compare to the classic Sieve of Eratosthenes? With that method, one treats all numbers as candidate primes and then, as each prime is discovered, one eliminates all multiples of that prime as candidates. With this enhanced method, one proceeds segment-wise through the number space, has at each step only a limited set of candidates and applies a sieve using a restricted set of multiples.
Bradley Richards
Switzerland
December 1997