*** March 2012 Update ***
This particular post on prime numbers seems to attract a fair bit of casual interest. It was written very early in my naive investigation of prime numbers (which remains fairly naive and perhaps a bit inept). People who stumble across this particular post might find some of the more recent work to be fairly interesting. Here are some of the more current posts:
A Postulate about Patterns, Symmetry and Periodicity in
the Distribution of non-primes and Possible Primes
Pete Quinn, BGC Engineering Inc., Victoria, BC, Canada
John Quinn, Carleton University, Ottawa, ON, Canada
ABSTRACT. This paper suggests that recurring patterns of non-primes and possible primes exist for all primorials, Pn#, where Pn is the nth prime. Further, it is suggested that the pattern of non-primes and possible primes is symmetric within Pn#. The process for determining the pattern of non-primes and possible primes is explained. These recurring symmetric patterns can be used to isolate all primes to Pn#, representing a significant advance on existing simple sieving techniques.
The distribution of prime numbers has been a topic of considerable interest to mathematicians throughout history. In recent years, the topic has gained particular practical importance, as modern public key encryption methods rely on use of very large prime numbers, and the difficulty in discovering them directly. Various methods are available to look for prime numbers, including simple sieving techniques such as the sieve of Erasthothenes. Prior research has identified and exploited patterns in non-prime distribution evident in small primorials, such as 6, where 6 = P2# = 3#. Visualization efforts reveal that similar recurring patterns exist for larger primorials, and are postulated to exist for all primorials. Further, these recurring patterns are all symmetric within the primorial, and this symmetry can be used to advantage. This paper proposes a new sieving method that capitalizes on observed recurring symmetric patterns in the distribution of non-primes and possible primes within every primorial grouping.
- OBSERVED PATTERNS
All prime numbers other than 2 conform to the infinitely repeating distribution 1,0, where “1” implies a number may be prime (i.e. is a “possible prime”) and “0” implies that a number cannot be prime. This is the same as saying that, apart from the special case of 2, all even numbers are not prime, all prime numbers are odd, and, in the absence of further information, all odd numbers are candidates to be checked for primacy. This rule may be used to screen out potential candidates when looking for prime numbers. It is simple, easy to propagate forward, and easy to accept as a given. However, on its own it is not particularly helpful in isolating primes, particularly as Pn grows large, since it leave 50% of all numbers as possible primes to be checked or ruled out by other means.
It is similarly well known that a six number pattern, 1,0,0,0,1,0, possesses a similar recurrence to infinity; in every group of six numbers, the 2nd, 3rd, 4th and 6th are automatically excluded as primes, and the 1st and 5th represent the position of possible primes. All prime numbers must conform to this rule, so all prime numbers fall as the 1st or 5th numbers in a series of six; however, not all of the 1st and 5th numbers are prime.
The literature also includes references to patterns involving repetitions of 30 number sequences, or 1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0. A common thread between these three sets of repetitive patterns is that they are based on groups of numbers defined by the first three primorials, or products of successive prime numbers: P1#, P2# and P3#, or 2, 6 and 30, where the primorial for Pn is defined as .
A second common thread is that all three patterns are symmetric about Pn#/2. For example, 1 is symmetric about 1 (P1#/2), the 6 number pattern 1,0,0,0,1,0 is symmetric about 3, and the 30 number sequence is symmetric about 15.
A third common thread is that each pattern of non-primes and possible primes within recurring groups of Pn# successive integers is based on the Pn repetition of the Pn-1 pattern (or Pn-1 sieve, for convenience), followed by removal of all prime products of Pn between Pn-1# and Pn#. This will involve products of Pn with prime numbers between Pn and Pn-1#; however, one can take advantage of symmetry, obtain the prime products up to Pn#/2, and then reflect the result.
It is postulated here, but not proven, that these same essential common elements continue for all Pn. The following paragraphs and Figures illustrate the observed patterns for the first several values of Pn. The subsequent section illustrates how these patterns might be exploited for finding primes.
Figure 1 presents the distribution of the first 18 prime numbers within successive groups of six consecutive whole numbers. In this graph and all the similar graphs, the coordinates have been obtained by determining (N mod Pn#) for the x-value, and truncating (N/Pn# + 1) for the y-value.
Figure 2 shows the distribution of the first 100,000 prime numbers according to the same representation. Other than 2 and 3, the two primes involved in obtaining P2#, the remaining primes all fall in two possible locations, which are symmetric about P2 (i.e. 3), 1 or 5. This simple pattern represents the very simple fact that, apart from 2 and 3, no prime may be even (a multiple or two) or a multiple of 3.
Figure 1. First 18 prime numbers distributed through (mod 6)
Figure 2. First 100,000 prime numbers distributed through (mod 6)
Figures 3 and 4 illustrate similar patterns for the distribution of prime numbers within groups of 30, P3#. For comparison, the possible prime locations inferred from P2#, or the P2# sieve, are shown repeating across groups of 6, and actual primes up to 30 are shown along the bottom. One can see that the periodicity developed for P2#, with primes possible at 1st and 5th positions with groups of 6, is preserved, but additional possibilities have been removed. The P2# pattern, or P2# sieve, can be used as a starting point to identify possible primes within P3#. By careful inspection, one can determine that the newly removed possibilities, 5 and 25, represent the complete set of prime multiples of 5, P3, between P3 and P3#. Deleting these from the recurring P2# sieve yields the full set of possible primes for P3#, providing the P3# sieve. In this unique case, removing the P3 prime products also removes all non-primes up to 30. For subsequent Pn#, it is necessary to remove prime products of primes higher than Pn to remove all non-primes to Pn#.
Figure 3. First 45 primes distributed through (mod 30)
Figure 4. First 100,000 primes distributed through (mod 30)
Figure 5 shows the first 100,000 primes distributed through (mod 210), or within groups of P4#, or 7#. The (mod 30) sieve is also repeated across the top for comparison, along with actual primes up to 210 along the bottom, for comparison. All possible primes within repetitions of 210 fall within the possibilities suggested by the (mod 30) sieve; however, selected possibilities have again been removed. In this case, the following possibilities no longer exist: 7, 49, 77, 91, 119, 133, 161 and 203. These represent multiples of 7 by 1, 7, 11, 13, 17, 19, 23 and 29, or 1 plus all primes from P4 to P3#.
By inspection, the distribution of possible primes remains symmetric about P4#/2. Since the 7-fold repetition of the symmetric P3# sieve must also be symmetric about P4#/2, it follows that the possible primes removed to obtain the P4# sieve must also be likewise symmetric.
The P4# sieve, once developed as described above, may now be repeated P5 times as the first step in identifying the distribution of possible primes within repeating groups of P5#, or 2310. First however, one could examine the distribution of actual prime numbers to 210, which in this case differs from the possible primes within P4# groups, or the P4# sieve. The following additional numbers have been removed from the P4# sieve to leave only prime numbers to 210: 121, 143, 169 and 209. These are all products of prime numbers higher than 7, yielding products less than 210. Note there is no evident symmetry in the distribution of these numbers, nor is there symmetry in the distribution of prime numbers to 210. The obvious recurring symmetric patterns are limited to non-primes and possible primes.
Figure 5. First 100,000 primes distributed through (mod 210)
Similar distributions of prime numbers can be generated for any larger Pn# following the same general processes, yielding symmetric patterns of possible primes and non-primes that can be further vetted to leave only prime numbers through a simple generation of all possible combinations of prime products less than Pn# involving prime numbers larger than Pn.
Figure 6 shows the distribution of primes for P5#, or 2310. A simple check reveals that the distribution of possible primes and non-primes remains symmetric. Obtaining the P5# sieve from the 11-fold repetition of the P4# sieve requires the removal of all prime products of 11. In this case, products of more than two primes are required, but for obtaining the P5# sieve, all of these prime products must include 11 at least once. Recalling symmetry, this step can be simplified by only obtaining prime products of 11 up to 1155, and then reflecting the result about 1155.
The graphs for larger Pn# values are not presented, as the existing patterns are not visibly apparent at practical plotting scales; however, the same symmetry exists in the distribution of non-primes and possible primes, and the same simple processes can be used to obtain this distribution and to then obtain the primes up to Pn#. Note that in obtaining the primes to Pn#, it is accepted that the primes to P(n-1)# have already been confirmed, and so the methodical process of removing additional prime products seeks to identify new primes from P(n-1)# to Pn#.
Figure 6. First 100,000 primes distributed through (mod 2310)
The development of new patterns with increasing Pn follows predictable patterns as illustrated in Table 1. The number of possible primes grows with Pn following a predictable progression defined by the product of all values of (Pn -1) up to Pn. In other words, when a given primorial sieve for Pn# is repeated P(n+1) times as the starting point for determining the P(n+1)# sieve, a total of P(n+1) unique prime products of P(n+1) are eliminated to obtain the higher sieve.
|Ordinal, n||nth prime, Pn||nth primorial, Pn#||Number of primes to Pn#||Largest prime to Pn#||Possible Primes from Pn# sieve|
Table 1. Growth of patterns of non-primes and possible primes
- EXPLOITING THE OBSERVED PATTERNS – FINDING PRIME NUMBERS
It should now be evident that the process for isolating prime numbers on the basis of recurring symmetric patterns within groups of successive numbers Pn# long is straightforward, as has been explained for Pn# up to 2310 in the preceding section. To obtain the primes for some arbitrary larger Pn#, it is necessary first to know all primes up to P(n-1)#. It would be convenient to also have the P(n-1)# sieve, but not necessary as this can be obtained from the primes to P(n-1)#.
To obtain the P(n-1)# sieve, take the list of primes to P(n-1)# and collapse it onto itself P(n-1) times to a single list of possibilities within P(n-2)#, from which we can directly infer the P(n-2)# sieve. Recall now that the process for obtaining the P(n-1)# sieve is to simply repeat the smaller sieve P(n-1) times, then remove all prime products of P(n-1) that fall between P(n-2)# and P(n-1)#. Recall again that we only need remove the prime products to P(n-1)#/2, and can then reflect these about P(n-1)#/2 to obtain the complete list of relevant prime products of P(n-1).
With the P(n-1)# sieve established, we now generate the Pn# sieve in the same fashion, first repeating the P(n-1)# sieve Pn times, then removing all prime products of Pn. The final step to obtain the primes to Pn# is to remove the additional prime products of primes greater than Pn less than Pn#.
This paper has described the existence of recurring symmetric patterns in the distribution of non-primes and possible primes based on primorials. The observed patterns have been used to develop a simple technique for isolating all prime numbers up to a given primorial value.
As Pn# becomes arbitrarily large, this process becomes progressively more cumbersome; however, it is believed to represent a substantial simplification of more basic sieving techniques such as the sieve of Erathstothenes. The potential differences in computational complexity are beyond the scope of this paper, but may be of interest to others to check. It is believed that a mathematical description of the described recurring symmetric patterns, which is left for others, may lead to other simplifications of existing techniques for identifying very large primes.
This work was first inspired by a lecture on cryptography given during a visit to the University of Waterloo, attended by the second author, resulting in an interest in the distribution of primes. The first author developed an interest after stumbling across Ulam’s Spiral in The Math Book by Clifford Pickover. The patterns were discovered by accident when programming Ulam’s spiral in a spreadsheet proved more than a few minute job, so instead the primes were plotted in successive circles, with 360 possibilities for each circle. Since 360 is a multiple of a primorial, 30, a beautiful pattern appeared, leading to a search for further patterns.
Ayres and Castro, 2005, Hidden Structure in the randomness of Prime Number sequence?
Cattani, 2010, Fractal Patterns in the Prime Number Distribution
Gibbs, 2008, The Double-Helix Pattern of Prime Number Growth
Grainville, 2008, Prime Number Patterns
Pickover, 2010?, The Math Book