Apologies for asking something that's likely already been hashed out 100 years ago. I have a question that likely has an easy and obvious answer to members of this community, and I haven't been able to get a good answer anywhere else. I'm not a mathematician, nor am I involved in looking for prime numbers normally. In my work as a geotechnical engineer I often find myself looking for patterns in disordered data, and over the holidays my son and I engaged in a small project involving distribution of primes. This question stems from patterns that we saw emerge.

My question relates to patterns and symmetry in prime distribution associated with primorials, and does not deal with primorial primes, per se.

Are there any sieving techniques already established based on the patterns of possible prime numbers within primorial sets? If so, can you point me to a link? I'm simply interested in seeing if we've come up with something novel, which I fully expect is not particularly likely.

Cheers,

Pete

Let me elaborate. Please someone jump in and tell me if this is either already common knowledge or simply the equivalent of other existing methods.

For any primorial Pn#, there is a pattern of possible primes that repeats forward to infinity. For example, P2# (i.e. 3#, or 6), the repeating pattern is 6m +/-1.

We can find the possible prime repetition pattern for P(n+1)# by first repeating the Pn# pattern P(n+1) times, and then removing all prime products of Pn, using only other prime numbers greater than P(n+1) but less than Pn#.

For example, start with 1,0,0,0,1,0 as a series of possible primes for P2#. This is the P2# sieve. To get the P3# sieve, repeat the series 5 times:

1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0 (here 1 indicates a number in this position "may" be prime, and a 0 indicates the number is not prime)

Now remove all multiples of five from this series. The only ones that remain involve a product of 5 with 1 and other primes greater than or equal to 5. In this case that means only 5 (since 5 x 7 is outside P3# and is therefore of no interest for this step), so we remove 5 and 25. The following represents the possible primes for every subsequent group of 30 integers:

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

Note, the values removed through this first sweep are symmetric about the mid-point of P3#. This seems to be the case for all primorial sets for the first pass of removal. Therefore, we only need to remove the prime multiples of 5 up to P3#/2, and then we can simply reflect the result about P3#/2 (e.g. reflecting 5 about 15 would give us 25 as expected).

This leaves the P3# sieve, which can be repeated forever as an indication of all possible future primes, but refined again at the next level (i.e. converted to a 7# sieve by repeating 7 times and then removing all products of 7 with 1, then primes from 7 to 30, including any products involving more than one other prime) to help us get the primes at subsequent levels.

The next step within P3#, to leave only prime numbers standing (the whole point, right?), is to remove all products of primes using only prime numbers greater than P3 (5 in this case). For Pn=5 there are no other products of primes greater than 5 less than 30, so this step makes no difference.

Note that for 1 to 30, this pattern is correct except for the primes already established up to P2#, which need to be retained in the list of known primes. In this stage we're ony interested in finding the primes between 6 and 30, as primes up to 6 were previously decided and recorded.

Note that as Pn increases, and we have more primes as factors in Pn#, the process attracts a little more complexity. Recall the sieve for the next higher primordial uses the following sequence:

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

but will be repeated 7 times:

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
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
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
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
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
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
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

To generate the sieve for the next primorial, remove all prime products of 7 as previously described, e.g. 7, 49, 77, 91, 119, 133, 161, 203. The distribution of these prime products involving 7 and one other number will be symmetric, so we could only find the first four, then reflect then about 105.

1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0
1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0
1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0
0,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
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,0,0
1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0
0,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0

We can duplicate this pattern 11 times to get the possible primes for every 2310 (11#) numbers.

However, we first want to identify all the prime numbers between 5# and 7# (30 and 210). To do this, we now need to remove all products of primes GREATER than 7 yielding a product of interest. This means if we delete 121 (11 x 11), 143 (11 x 13), 169 (13 x 13) and 209 (11 x 19), it will leave us with only prime numbers up to 210.

The process is the same for larger Pn#, except we need to consider products of a larger number of primes in the sieving within a given range from P(n-1)# to Pn#.

At first glance this might seem to boil down to an equivalent of the sieve of Erathosthenes, but I think it reduces to an exponentially smaller number of calculations as you are able to take advantage of the patterns, periodicity and symmetry embedded in the sequence of prime numbers.

This would be easier for me to explain with some of the graphs I used to visualize this.

I've only explained the general process of generating the sieves and focussing the search to eliminate the rest of the non-pimes, but it should be obvious that those other steps can also be described coherently.

Please note I tend to be a little careless with details, so it's quite possible (likely even!) there are some minor errors embedded in this post. I don't think they detract from what I've presented, but perhaps they do, and feel free to let me know.

I'm happy to receive criticism of the idea, friendly or harsh. If this is all sound and fury, I'm happy to be told so. If by some odd chance this might be novel, I'd be happy to hear that too.

Cheers,

Pete

Thanks for the feedback, I will try to absorb it and mull it over.

Here is where I think what I've proposed may differ from what you've just explained, to hopefully clarify what I'm getting at:

Using "around 32000" as a working example, let's consider 30030 (13#).

There is a symmetric pattern of possible primes within every group of 30030 numbers, and this pattern can be revealed fairly simply (as described before). This is the same as the 1,0,0,0,1,0 pattern for mod6, just based on mod 30030 instead. Let's call this the 13# sieve, or mod30030 sieve.

This pattern is useful for two reasons:

- first, we can use a relatively straightforward and focussed further sieving process to remove non-primes up to 30030 (recognizing that we previously already defined primes up to 2310 in the prior steps)
- second, we can repeat this pattern 17 times to give us the starting point to create the 17# sieve (mod510510 sieve), which we then obtain by removing the prime multiples of 17

Then there is a subsequent step to identify the primes to 510510 by removing all prime products remaining between 30030 and 510510 (these will involve primes greater than 17 only).

I think this is different (and more efficient) than what you have just described, but I recognize I may be missing some basic logic.

Cheers,

Pete

First, I can't say what I'm trying to improve, per se, because I don't specifically know what is already accepted practice, although your explanations do help in this regard, thanks.

I guess what I'm suggesting (perhaps somewhat naively) is that if we assume the sieving process is executed properly, then there is no need to check the remaining numbers that have been identified as prime (through the process of elimination of all non-prime numbers) are prime. They are known to be prime because the sieving process has already explicitly excluded all no-prime numbers (unless an error has been made).

This image may help explain what I'm blathering on about:



The top graph shows the distribution of all primes (up to the first 100,000) based on mod210. You can see there is a clear symmetric pattern of distribution of possible primes, represented by the vertical "bars" of accumulated primes. The green triangles on the bottom represent actual primes (up to 210).

The second graph zooms into a part of the upper graph - from 90 to 150 - to illustrate the distribution and concepts in a little more detail.

The third graph shows a run of 210 in a plot of mod 2310. If I zoom out to the entire range of 2310, you will see the distribution of possible primes is also symmetric. It also contains the same underlying pattern from the mod210 pattern, but with a few possibilities removed (all prime multiples of 13 from 210 to 2310).

Note the purple symbols represent the recurring pattern of the lower primorial sieve. A simple process serves to eliminate those values no longer valid at this scale (leaving the smaller symbols at the top), then a subsequent (also simple?) process serves to isolate the primes up to 2310 (i.e. green triangles).

OK, for kicks, here is the distribution of 100,000 primes (well, actually about a third of them) based on mod2310, plotted at a couple of different vertical scales:

Thanks for continuing to humour me.

Sadly, I lack the mathematical language to attempt to describe this properly, so I won't attempt that. Also, I don't have time to try to program this myself. I'm more than fully busy with the day job, and really shouldn't let this distract me any further. What I can do though is attempt to demonstrate the hypothesized symmetry through further visualization, which I recognize is not the same as a mathematical proof.

In the following series of graphs, I've taken all the primes as distributed in mod2310 and reflected those above 1155 about 1155, and placed them above those from 1 to 1155 for comparison. If the distribution is symmetric, then we should have a column of reflected primes above every lower column of unreflected primes.

The first graph shows the whole range, then each lower graph shows them in increments of 210 (and 105 for the last graph) to allow closer study.



Can you detect any evident absence of symmetry?

I recognize this is a brute force approach, and not particularly elegant from a purely mathematics perspective. This is how I roll. :-)

You seem to be repeating the same stuff without understanding what I have written.

Pete,

are you in fact sugegsting to follow your method continuously, and not do teh second step of "check the 'small' primes jst found against the (much much) larger candidate numbers"?

if so, the yes that is essentially "equivalent of the sieve of Erathosthenes" with a few shortcuts.
some shutcust that are already used include:
using bits to repersent odd numbers only (ie all multiples of 2 are completely ignored)
and covering sets (which might be closed to what you are suggesting)

i think a modern computer will still run out of ram/storage before being able to complete a sieve to a depth of the size you are suggesting.
(maybe rogue can comment on this.)

Cheers
shoelace

are you in fact sugegsting to follow your method continuously, and not do teh second step of "check the 'small' primes jst found against the (much much) larger candidate numbers"?

some shutcust that are already used include:
using bits to repersent odd numbers only (ie all multiples of 2 are completely ignored)

and covering sets (which might be closed to what you are suggesting)

i think a modern computer will still run out of ram/storage before being able to complete a sieve to a depth of the size you are suggesting.
(maybe rogue can comment on this.)

By stating "distribution of possible primes", then you are technically correct, but "possible prime" and "prime" are not the same.

There are no patterns to the distributions of actual primes.

I suggest you extend your method (as a thought experiment) and see what the effort is to determine if a 50 digit number is prime or not.

OK, so first I assume we already have a list of prime numbers up to P31#. It would be convenient to assume we also have the P31# sieve, or starting point for getting the primes up to P32#, but let's assume we don't, since one might like to try this from an already long list of known primes.

To make any headway, we need to get the P31# sieve. To do this, start by folding the list of known primes (to P31#) into itself P31 times (127 times). This will give us a distribution of primes that looks like the graphs I've already shown you, just with a much longer x axis! This is the P30# sieve. Now using that distribution of possible primes (p30# sieve), repeat it (unfold it, yielding a repetitive P30# sieve pattern) P31 times. This is the first step in getting the P31# sieve.

A - Now we need to remove all prime multiples of P31, starting with single multiples involving all the known primes up to P30# (a long list), and then, as necessary, using other primes greater than P30, but less than P30# (mostly much less - more on this later) in combination to yield products less than P31# (actually, we can focus the search to products less than P31#/2 due to symmetry, which I've claimed but not proven).

A lengthly list of combinations and permutations of prime products will be required, but some fairly simple math can be used to deduce this number (I think this should be evident but I can elaborate if necessary).

Once we've removed all possible products of P31 by other primes yielding products less than P31#/2, we can stop, reflect this pattern, and we now have the P31# sieve.

To get the primes to P32#, start by repeating the P31# sieve P32 times, the first step in building the P32# sieve. Then repeat the process started in A above, but for the relevant higher numbers.

To get the primes from P31# to P32# the next step is to remove all of the multiples of primes higher than P31 (but obviously less than P31#) that yield a product less than P32#. This step does not have symmetry to use to advantage unfortunately.

I recognize that a large number of steps are required. My feeling, though, is that by capitalizing on the distribution of possible primes at any given primorial (or, rather more correctly, capitalizing on the distribution of known non-primes), the process should be more efficient relative to other methods.

But this "feeling" is based on very little other than instinct and hope, I suppose, as I have absolutely no idea how you all look for these big prime numbers now.

However, someone has used the example of repeating odd/even patterns forward indefinitely as an easy first pass, and I know others use mod6 or mod 30 patterns to aid sieving. What I am suggesting follows in exactly the same vein, just using bigger patterns. If use of the smaller patterns yielded some form of efficiency, it seems to follow that use of the larger symmetric patterns should also yield efficiencies.

Cheers,

Pete

BTW - I feel like a grade schooler who's walked into a university class and marvelled out loud over his discovery of imaginary numbers, trying to pass it off as a new discovery. ;-) If someone would like to throw me a lifeline by directing me to prior work on this topic (like a high school text in my analogy), I'd be happy to take the reference and go away quietly.

Also, to give credit where due, there is at least one other person working with similar ideas:

http://primepatterns.wordpress.com/2010/06/12/6/

He seems to be aiming toward helixes, which I think is an essential difference, but he has recognized that patterns in the primorials may be used to some advantage. I assume it is likely that others have also.

Take a look at 131# (aka p(32)#): 525896479052627740771371797072411912900610967452630. The largest HDD can only store about 1000000000000 bytes of data. It should be easy to see that storing the pattern for that primorial is not physically possible.

Take a look at 131# (aka p(32)#): 525896479052627740771371797072411912900610967452630. The largest HDD can only store about 1000000000000 bytes of data. It should be easy to see that storing the pattern for that primorial is not physically possible.

Thanks for humouring me on here folks. I've tried to present the ideas a little more formally and concisely in the form of a draft paper, a rough version of which can be found here:

http://petequinnramblings.wordpress.com/2011/01/09/draft-paper-on-patterns-in-prime-numbers/

If anyone knows whether this representation of recurring symmetric patterns has been published elsewhere, I'd still appreciate hearing about it.

Cheers,

Pete

Just for completeness, here's the whole story in draft paper form. Hopefully the formatting will work OK.

Has anyone found this to be of any use or interest?

Cheers,

Pete

----------------------------------

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.

1. INTRODUCTION

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.

2. 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 . 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
1 2 2 1 2 1
2 3 6 3 5 2
3 5 30 10 29 8
4 7 210 46 199 48
5 11 2310 342 2309 480
6 13 30030 3248 30029 5760
7 17 510510 42331 510481 92160
Pattern:

Table 1. Growth of patterns of non-primes and possible primes

3. 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#.

4. CONCLUSIONS

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.

5. ACKNOWLEDGEMENTS

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.

REFERENCES

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
[img][/img]

Wee bit of follow up. Reading through the book Prime Numbers, a Computational Perspective, by Crandall and Pomerance, my son came across something similar to what we've described here (see their section 3.2.7). They refer to a paper by Pritchard, 1981 as the original source. There appear to be some key difference, first of which is the absence of any mention of symmetry in distribution of "non-primes" or "possible primes" (as we've defined them here) within a given primorial.

It wasn't obvious to us why the distribution of possible primes within repeating primorial sets would be symmetric, so we've looked at that a little closer.

The process we've described for obtaining a primorial sieve (i.e. obtaining the "possible primes" and "non-primes" with repeating primorial sets) amounts to, basically, a more efficient version of the sieve of Erathosthenes (SoE for short). So let's look at that for a moment.

The first step in SoE is to remove all multiples of 2, e.g. all even numbers, or half of the set of all natural numbers. The second step is to remove all multiples of 3. This step would remove a third of all natural numbers, except all the even numbers have been removed, so it actually removes 1/6 of all numbers, given the even numbers have been previously removed. In fact, this step removes exactly one and the same possible position from every sequential set of six natural numbers (i.e. repetitions of P2#, or 6) - the third, or middle position within the group of six.

If we combine the "non-primes" removed by the multiples of 2 and 3, we see that every 2nd, 3rd, 4th and 6th possibility is removed, leaving only the 1st and 5th positions as possible primes.

Notice that the distribution of "non-primes" from the multiples of 2 and 3 were each symmetric within 6.

If we move up to P3#, or 30, and remove multiples of 5, the only positions remaining to eliminate as non-prime (i.e. that were not previously eliminated by the 2s and 3s) are 5 and 25. Again, this pattern is symmetric within 30.

If we move up to P4#, or 210, the possibilities removed by repetitions of 7, not already removed by 2, 3 or 5, is again symmetric within 210.

Each of the smaller repeating patterns of non-primes, being symmetric within smaller primorials that have been multiplied by odd (prime) numbers, remain symmetric within the larger primorials. Hence the summation of these "non-primes" remains symmetric.

Recall that these "non-primes" do not include all numbers that are not prime, they are simply positions with repeatable primorial sets that can never be prime. In order to obtain ALL non-primes, and by the process of elimination be left with only primes within a given primorial, it is necessary to remove all multiples of higher primes between Pn and sqrt(P(n+1)#).

It seems to be a general result (which I claim by observation, and not by mathematical proof), that for any given prime factor of a primorial, the distribution of possible primes removed by its repetition (either after or before removal of all possibilities by repetition of the smaller prime factors) makes a symmetric pattern within the primorial.

It's also entirely straightforward to calculate how many possible primes will be removed by one of a primorial's prime factors. Subtract all the possibilities removed by the smaller prime factors, and then divide the remainder by the prime under consideration.

By contrast, the possible primes removed by primes greater than Pn (and less than the square root of the next primorial) is by necessity NOT symmetric (but would become symmetic within a larger primorial that includes that prime as a factor). Hence the distribution of primes within a primorial is also NOT symmetric.

Turns out the symmetry in these primorial sieves is pretty simple to prove (I think).

Start with the smallest primorial, P1#, or 2#, which is 2. Eliminate all multiples of 2. This leaves you with a single possible prime in every repeated set of 2 - the first position, or every even number.

So if you repeat 10 off to infinity, where "1" represents a "possible prime" and "0" represents a certain non-prime, in other words repeat the P1# sieve off to infinity, then you've eliminated half of all natural numbers as potential primes (the even numbers).

Notice that 10 is symmetric within 2, or in other words its pattern reflects at 1 (mid-point from 0 to 2).

If we repeat 10 only up to the next primorial (6), the resulting pattern remains symmetric. This is because it started as a symmetric pattern and was repeated an odd number of times. In fact we can generalize this finding for all primorials... repeat the P1# primorial sieve up to any primorial, and the pattern will remain symmetric within that primorial (i.e. reflects about its mid-point), since all factors (other than 2) of all primorials higher than P1# are odd, hence the 10 pattern will always be repeated an odd number of times, and will therefore remain symmetric.

Now let's consider what happens when we start to project the next prime, 3, out to infinity, first ignoring what was already removed by 2. If we remove all multiples of 3 from 1 to 6, we are left with 110110 as possibilities, notwithstanding the even numbers, within all subsequent sets of 6 consecutive numbers (it may be more intuitive for some to consider the pattern from 0 to 6 instead, or 0110110).

This pattern is symmetic within 0 to 6, in that it reflects about 3.

The pattern from the even numbers from 1 to 6 is 101010. If we "combine" this (for a given position, if either pattern has a "1" the result is "1") with the pattern from the repeated 3s to leave "possible primes" and non-primes, we get 100010. This is again symmetric within 6, as it must be: the logical combination of two symmetric patterns must yield a symmetric pattern.

It can be seen quite easily that the repetition of any prime factor of a primorial up to the value of that primorial will always yield a symmetric pattern. Therefore, the pattern of repetition of each individual prime factor within the primorial will be symmetric. Since the primorial sieve is the result of a logical combination of the repetitive patterns from each prime factor, which are each symmetric, it must be symmetric.

I'm not sure if knowing where to find long strings with NO PRIMES would be of any interest, but the following seems to be true for the general case:

For any primorial, Pn#, or any multiple of that primorial, (Pn# + 1) and (Pn# - 1) are "possible primes," and all other numbers between (Pn# - Pn) and (Pn# + Pn) are NOT PRIME.

Therefore, for P11# = 31# = 200560490130, and any and all multiples of this value, there will be at least 30 sequential non-primes preceding and following, with the positions immediately preceding and following being possible primes.

I'm claiming this without proof, again from observation, but I think the proof is probably quite straightforward.

So if one felt they needed to, for example, find a string of at least 210 non-primes in a row, they would only need to go to P47# (211#), and look directly before and after. Or to any multiple of P47#. Of course that's a pretty big number. :-)

I think I've probably written just about enough. I'd like to follow up on rogue's input from early in the thread. The more I play with this, the more I recognize that the value of these primorial sieves is probably fairly limited. I get his point that the computational requirements increase quite dramatically as the size of the primorial sieve grows.

However, in the event anyone would like to try playing with this, the attached txt file includes the primorial sieve values from 1 to 30030:

http://www.qfpost.com/download.do?get=cbc1a908c50f19199ac9b675353d35be
One can go to any multiple of 30030 (say 3.0030 E+100 for example), and then start repeating this pattern as far as they like as a first pass sieve. This will leave behind 5760 "possible primes" out of every 30030, which obviously still leaves many/most primes undetected, with the actual proportion depending on how big a number you start at.

BTW - if someone wants to throw me a lifeline and tell me I'm prattling on at a pre-school level (if this seems to be the case) and save me further embarassment, I'll be cool with that.

In case anyone is interested, I extended this previous bit of numerical experimentation to twin primes, and found (perhaps unsurprisingly) some similar patterns. Some details here:

http://wp.me/p1h3oO-O

Was just playing around a bit to try to understand the bounds of the twin prime conjecture problem. No breakthroughs to share (surprise!) but I find the patterns and trends to be interesting, and help me, as a visual thinker, to put the challenge in perspective.

I've done a bit more numerical experimentation with twin primes, and extended the work to other k-tuples, including quadruples, quintuples, sexy primes and cousin primes, here:

http://petequinnramblings.wordpress.com/2011/11/05/prime-triples/

I recognize there's a significant probability I've made a grave error somewhere, but the analysis seems to confirm the set of twin primes is infinite, as are the other k-tuples considered.

sorry, URL:

http://petequinnramblings.wordpress.com/2011/11/05/prime-triples/

Thanks for the comment. I'm not sure I was necessarily looking for a Holy Grail, per se, really just exploring patterns and seeing what they yielded. This most recent exploration of patterns in k-tuples seems to lead to deterministic formulae for density of various k-tuples, which I think leads to defensible conclusions of their respective infinities. Of course, what "I think" and what are demonstrably proven may well be two very different things. :-)

Thought I'd float a trial balloon... anybody able to pop this one?

Consider the set of natural numbers, N. For any given natural number, n, every n-th natural number is a multiple of n, hence 1/n of N are multiples of n.

In the set of even numbers, E, every n-th number is also a multiple of n, hence 1/n of E are multiples of n.

We can generalize this statement that for the set of all multiples of any given prime number, Pn, and we will call this set Mn, every n-th member of this set is a multiple of n, hence 1/n of Mn are multiples of n.

If we remove E from N, and are left with with the set of odd numbers, O, then for any given n, 1/n of O are multiples of n.

Consider now the process of stepwise removal of all multiples of all primes, Pn, working from 2 toward infinity. Removal of the even numbers leaves 1/2 of N remaining under consideration as possible prime numbers.

Of the remaining half of N, 1/3 are multiples of 3, so further removal of composite numbers to eventually reveal the set of primes by stripping away remaining multiples of 3 removes 1/3 of the remaining half of N, or 1/3 of 1/2, leaving a rational number, 1/3, of N remaining under consideration as possible primes.

When we next remove the remaining products of 5, we strip away 1/5 of what was left prior, or 1/5 of 1/3, or 1/15, leaving 8/30 of N.

In progressive steps of sieving with each successive prime, we strip away a fraction of the candidate primes remaining after the prior sieving step, where this fraction is in all cases a rational number, this leaving a rational number as the fraction of N remaining as possible primes.

As this process proceeds toward infinity, the fraction of N remaining with candidate primes gets ever smaller, approaching but never reaching zero, remaining always a rational number. Since N is an infinite set, any rational fraction of N is also infinite. Hence the set of prime numbers is infinite.

We can use similar logic to show that the sets of twin primes and larger prime k-tuples are also infinite.

Consider again stripping away all even numbers, leaving O. At this stage, every remaining number, which remains to this point under consideration as a possible prime, is separated from another candidate prime by two, hence every odd number is a candidate twin prime, and half of N remain as possible twin primes. Let’s call the set of candidate twins after n sieving steps as TWn.

Twin prime pairs (the “normal” definition) are groups of two consecutive primes separated by two. Consider that every twin pair, or every candidate pair remaining after the n-th sieving stage, has a lower prime and an upper prime. Define the set of lower primes within the n-th sieving stage set of candidate twins as T_L and the set of upper primes as T_U. Within the set of candidate twins, half are in T_L and half are in T_U, and T_L and T_U are offset by two, with all members of T_U being equal to the corresponding member of T_L plus 2. We can therefore deduce that within both T_L and T_U, 1/Pj of each set are multiples of Pj where Pj are primes higher than Pn.

When we remove all primes P(n+1) in the next stage of sieving, we remove 1/P(n+1) from T_L and 1/P(n+1) from T_U. Every member of T_L or T_U thus removed eliminates one candidate twin pair from further consideration, and since any single repetition of P(n+1) cannot eliminate both primes in a single pair, 1/P(n+1) of TWn are removed from both T_L and T_U, or 2/P(n+1) of TWn is eliminated.

Thus we see that, while 1/Pn of all remaining prime candidates are removed at each sieving stage, 2/Pn of all remaining twin prime pair candidates are removed. And yet, following a similar logic as demonstrated for the sequential elimination of prime candidates, the proportion of N remaining as candidate twin primes is always a rational number, no matter how arbitrarily large Pn becomes. Hence, there are infinitely many twin primes.

Following precisely the same logic, we can show that for Pn > k, where k is the size of a prime k-tuple, each sieving stage removes k/Pn of the set of candidate k-tuples remaining after the previous sieving stage, and hence the sets of all k-tuples for finite k, where feasible k-tuples exist, are infinite.

Thanks rogue, this is where I've come to after fairly extensive numerical experimentation, which led to some interesting patterns, that got me wondering about the patterns and trying to understand them.

I think the logic in the preceding post, which has developed from trying to understand patterns, demonstrates the twin prime conjecture. But understanding that's a famous problem that's been under attack for a long time, I realize the likelihood I've proven it is slim. Yet I think this logic, while very simple, is tight. So I was throwing this out there to see if anyone could find a hole in it.

I already know that by programming this (which I've already done) I will see the results I'm claiming. I'm just wondering if the logic would fail at some point beyond which I've worked out numerically.

After reading most of the above I feel that the idea is a sieve after the pythagorous test.

The +-1(mod 6) was found about 2200 years ago, the proof goes :-

Any number can be written as n6+{-1,0,1,2,3,4},
as 6 is even n6 is even, and n6+{0,2,4} are even and not prime leaving n6+{-1,1,3}
as 6 is a multiple of 3 so is n6 and n6+{3} can be removed,

HENCE ALL PRIMES GREATER THAN 3 ARE A MULTIPLE OF 6 +- 1, ALL TWIN PRIMES ARE BALANCED ABOUT A MULTIPLE OF 6.

To sieve beyond this rapidly becomes pointless as this system (like all partial sieve systems) suffers from the problem that as the numbers increase the ratio of true primes to potential primes declines.

You will also reach the problem that the generation of the list of (sieved) possible primes will take longer than the determination of true primes would take using more direct prime/not prime methods that do not require a list of factors to the square root (such as the LLR test).

Finally, as said many times before, although it is possible to sieve to completion as a true prime test any number when the numbers get as big as we are using it is not practicle as the size of the list of primes to the square root becomes massive (many times the world hard drive capacity), such a file would take at least a few years (possibly lifetimes) to send to each user and the sieving would take millenia even on the fastest computers.

Partial sieving with just a few thousand known primes and then using the LLR test is still the best way that has been found to find Very Big Primes in the region of P>10E(10E5).


____________
Member team AUSTRALIA
My lucky number is 9291*2^1085585+1

Thanks Dave,

I had already acknowledged rogue's earlier comments in the thread about the impracticality of trying to implement what I was suggesting at the beginning of the thread. But I continued to investigate patterns, which led to what I've offered a few posts back as a possible "proof" of the twin prime conjecture. I'm really most interested at this time in seeing if anyone can drive a nail in the coffin of the logic I've presented.

Cheers,

Pete

I realize this may remain of limited interest to people hunting for very large primes, but we've recently picked up on another pattern in the distribution of non-primes and "possible primes" with the n-th primorial, Pn#, after sieving by the first n primes to Pn.

We've previously stated that the number of "possible primes" within the n-th primorial can be determined as:

Nn = product(i = 1 to n) [Pi - 1]

And if you like, you could calculate the density of possible primes within Pn# as Nn/Pn#. Further, you could estimate the number of primes to Pn^2 by calculating:

pi(Pn^2) ~ (Pn^2)*Nn/Pn#

It turns out that for large n this estimate overpredicts the actual number of primes by a small amount which we think to be equal to 1.1229, which is related to the Euler-Mascheroni constant, and is an error consistent with work done by Mertens in the late 1800s.

Similar formulae can be developed for twin primes and k-tuples that follow similar trends, and appear to have similar errors as associated with the number of primes.

All of this is mainly just background context. The main point is to extend our observations about symmetry within primorials during sieving by successive primes, to not only determine NUMBERS of eliminated non-primes and possible primes, but to also determine their POSITIONS on the basis of relatively little information.

It turns out that the positions of possible primes at the next primorial can be determined completely with only the set of possible primes within the current primorial and knowledge of the next prime.

If we know, for example, that within every successive set of 6 natural numbers, there is a possibility of the 1st and 5th being prime, with all others being definitely non-prime, we determine the possible primes within the next primorial, P3# = 5# = 30, as follows:

- first repeat the pattern of possible primes within 6 five (P3 = 5) times, so

100010

becomes the set A5:

100010100010100010100010100010

- now "stretch out" the pattern of possible primes within 6 by a factor of five to yield the set B5:

000010000000000000000000100000

- now eliminate these candidates, subtracting the set B5 from the set A5, to yield the set of "possible primes" within 30, which we will call PP5:

100000100010100010100010000010

This pattern can be similarly repeated 7 times and stretched by a factor of 7 to give A7 and B7, respectively, which can be used to obtain PP7, the set of possible primes within P4# = 7#, or 210.

Therefore if we've sieved to some arbitrary primorial, we can obtain non-primes and possible primes at the next primorial by repeating the pattern of possible primes P(n+1) times, and stretching it out by a factor of P(n+1), eliminating a faily significant amount of computation.

I realize this likely still isn't of partiular use for the search for extremely large primes, and also that I have not provided a proof to back up the claimed pattern. I just thought it might be of some interest to people who are interested in prime numbers.

Cheers,

Pete

Hi

I started out kinda like you and found some patterns as well in the primorial sieve. My start was actually the sieve of Eratosthenes. Your findings and conclusions so far are (IMHO) all based on the mother of all sieving methodes.

The reason for the symmetry can be explained by the nature of the primorial values. E.g. p3# (or 30) = 2 x 3 x 5.

The candidates in the first 30 numbers are the values that remain after sieving with 2, 3 and 5. At 30 (the product of 2, 3 and 5) the pattern starts again as you made visual in the graphs.

These candidates are symmetrical on 15 and 30. (p3# and p#3/2). The symmetry on the other values (p3#/3 and p3#/5) gets complicated really fast. The pattern of symmetry is independent of the sieve size and also goes for the larger primorials (p4#, ..., p10000# ...).

I have been looking for big gaps between primes a little (ahum, check TR Nicely's website if your interested) and first figured that the symmetry of pn#, would be an easy way to find prime gaps.

Note: pn# has candidates pn# +/- 1 and the next candidate after that is pn# +/- p(n+1). Actually all primes after that till p(n+1)^2 are candidates. After that the candidates are the larger primes and the products of the primes from p(n+1) on.

I personally like the symmetry of the candidates on pn#/2. But I will leave that to you to figure out.

The practical problem is that this way of approach still leaves too many candidates. The primorial candidates are growing way faster than the actual number of primes.

The number of candidates within a primorial interval can be calculated as:
P1# --> p1# * (2-1)/2 = 2 * 1/2 = 1
P2# --> p2# * (2-1)/2 * (3-1)/3 = 6 * 1/2 * 2/3 = 2
or 2 * 3 * (2-1)/2 * (3-1)/3 = (2-1) * (3-1) = 2
P3# --> (2-1) * (3-1) * (5-1) = 8
P4# --> (2-1) * (3-1) * (5-1) * (7-1) = 48
P5# --> 48 * (11-1) = 480
etc. etc.

You can use a spreadsheet to check for yourself that the number of primes untill a number x seem to follow the natural logarithm of x. This is the prime number theorem. From the primes pages (http://primes.utm.edu/howmany.shtml) you can compare the actual number of primes versus the number of candidates that remain in a primorial range.

I do believe that going back to the basis (SoE) gives insight. But there have been a lot of mathematicians over the ages who have been following this trail. For me, studying the SoE has helped me rediscover some findings done long ago. But it has also given me insight into where to look for prime gaps. What you have written so far matches my and maybe many other people's findings after studying the SoE. Somehow there does not seem to be any easily accessible books/articles/websites that start at introduction level. This is a pitty! It would have saved me a lot of time fiddling with spreadsheets ;-)

I think that the distinction between candidates and real primes is of the essence. Any theorem or postulate based on the primorials should take this into consideration. Proving prime for large numbers (a major point of interest for most members of this site) is a totally different ball game all together.

Regards
Michiel Jansen

Thanks for the comments Michiel.

I recognize that most people on here are interested in problems associated with very large numbers, and what I've written on here has very little evident relevance.

I also recognize that probably everyone on here knows much more about primes and number theory than me. For me, this has been a fun, late life intellectual diversion, unrelated to the day job. I don't pretend or expect to make any discoveries that have gone unnoticed by others far more qualified than me. But still, I've had some fun playing with some difficult challenges, in part to help stave off inevitable dementia. :-)

On this:

I personally like the symmetry of the candidates on pn#/2. But I will leave that to you to figure out.

Hi Pete,

First off, no need to apologize. The reason for me to reply to your posts was that I went through a similar proces over the last two years. The lack of intelligeble documentation on these patterns, the logical build up of the SoE and the feeling that there should be something in these patterns, gave me as much drive as I tasted from your posts, to stick with it, and for me also it has been (or is?) a nice diversion from my dayjob ;-)

But the more I started reading about it, the more I came to the conclusion that very smart people in the past, Fermat, Gauss and Riemann to name a few, used some of these ideas in a much more elaborate and sophisticated way.

The SoE can be used to create a list of all the small primes (say till 10^10 as I have done). As far as I can tell from my experiments, this is still the fastest method for obtaining the small primes. As soon as you want bigger primes you need something extra, as mentioned early on in this thread.

The cyclic patterns are used in so called "wheel factorization" (see also wikipedia), to get rid of the most obvious composite values in an interval. This is a method of partial seeving that for instance is used by http://www.ieeta.pt/~tos/hobbies.html. He (with help from other people) has been through all primes till 3,5 * 10^18 at least once. Remarkable!

PS I did not read any of your blog posts, so I missed your description of the pn#/2 pattern. And I thought I was the only one that had seen that ;-)

Stay curious,
Michiel Jansen