Determination of position of non-primes and candidate primes


We have previously shown that within a given n-th primorial, Pn#, there are Nn “candidate primes” or “possible primes” left remaining under consideration pending further sieving by higher primes. We have defined Nn as shown in equation (1):

We can generalize this formula for candidate twin primes or higher k-tuple primes as shown in equation (2).

Drawing from the fact that sieving by all primes to Pn removes all non-primes to Pn^2, we have previously used these formulae to estimate the number of expected primes, twins or k-tuples less than Pn^2, as shown in equation (3) for the number of primes, pi, less than Pn^2.

And for the number of twin primes, pi_2 as shown in equation (4).

Similar formulae can be derived for all other feasible k-tuples. Plots of these formulae for expected numbers of primes, twins and k-tuples show that the formulae track along the same trends as actual counts, but represent an overestimate. Evidently, the average number of possible primes within primorials tends to be higher above Pn^2 than below Pn^2.

This finding led to a search for patterns in the distribution or spacing of possible primes and non-primes within primorials, to find an explanation for this discrepancy and the associated error in the predicted number of primes, twins and k-tuples.

Further study has revealed that not only ares the numbers of possible primes and non-primes within the n-th primorial predictable with successive sieving to Pn, the progressive distribution of possible primes and non-primes is similarly predictable, following a very simple recursive pattern.

The process may be described as follows. Start with an arbitrary n-th primorial, Pn#, after sieving by all primes to Pn. At this point, sieving will have removed a number of non-primes, leaving Nn numbers within Pn# as possible primes, all of those under Pn^2 which are known to be actual primes. The primes from 2 to Pn have at this point also been removed from the primorial as non-primes in repetitions of the primorial forward, but are in any event already known to be prime.

To obtain the possible primes within P(n+1)# after sieving by P(n+1)#, we first repeat the pattern of possible primes within Pn# a number (i.e. P(n+1)) of times, yielding a new set we can call A(n+1). We have already established that the number of possible primes within P(n+1)# will be N(n+1) = (P(n+1) – 1)*Nn. However, we can also know, deterministically, the positions of the possible primes to be removed from the P(n+1) repetitions of the set of possible primes in Pn#, as follows:

Take the set of “possible primes” within Pn#, which we can call PPn, and multiply each member of the set by P(n+1). This new set, which we will call B(n+1) can be removed from A(n+1) to yield PP(n+1).

Examples for the first few primorials:

2# = 2

After sieving with P1 = 2, we have eliminated all even numbers as non-prime, leaving all odd numbers remaining as candidate primes pending further sieving by higher primes. Define PP2 as the set of possible primes within every repetition of 2# = 2 in the set of natural numbers. Use the following convention:

PP2: 10

(Note I’ve gone back here to an earlier format I used – “0” means definite non-prime and “1” means “possible prime” so within every consecutive set of 2 natural numbers, the first – the odd one – could be prime, pending further sieving, and the second – the even one – cannot be prime)

3# = 6

To obtain possible primes and non-primes within all repetitions of the next primorial, 3# = 6, first repeat the pattern of possible primes from 2#, namely PP2, 3 times to obtain A3: 101010

Multiply each possible prime from 2#, identified as “1” within PP2, by 3 to determine which possible primes need to be removed by sieving with 3, obtaining B3: (001000)

Subtract B3 from A3 to obtain the possible primes within 3#, PP3: 100010

5# = 30

Repeat the pattern of possible primes from 3#, namely PP3, 5 times to obtain A5:
100010100010100010100010100010

Multiply each possible prime from 3#, identified as “1” within PP3, by 5 to determine which possible primes need to be removed by sieving with 5, obtaining B5: (000010000000000000000000100000)

Subtract B5 from A5 to obtain the possible primes within 5#, PP5: 100000100010100010100010000010

7# = 210

Repeat the pattern of possible primes from 5#, namely PP5, 7 times to obtain A7: 10000010001010001010001000001010000010001010001010001000001010000010001010001010001000001
01000001000101000101000100000101000001000101000101000100000101000001000101000101000100000
10100000100010100010100010000010100000100010100010100010000010

Multiply each possible prime from 5#, identified as “1” within PP5, by 7 to determine which possible primes need to be removed by sieving with 7, obtaining B7:
(0000001000000000000000000000000000000000000000010000000000000000000000000001000000000000
01000000000000000000000000000100000000000001000000000000000000000000000100000000000000000
0000000000000000000000010000000)

Subtract B7 from A7 to obtain the possible primes within 7#, PP7: 100000000010100010100010000010100000100010100010100010000010100000100010100010000010000010
100000100010100000100010000010000000100010100010100010000000100000100010000010100010000010
100000100000100010100010000010100000100010100010100000000010

And follow precisely the same process for all subsequent primes and primorials…

Since the positions of non-primes within each successive primorial can be obtained deterministically using this simple recursion, we should be able to develop a refined estimate of density of possible primes lower than Pn^2, which is identically equal to the number of actual primes less than Pn^2.

More to follow… 

About petequinn

I'm a Canadian geotechnical engineer specializing in the study of landslides. I started this page to discuss some mathematical topics that interest me, initially this involved mostly prime numbers, but more recently I've diverted focus back to a number of topics of interest in geotechnique, geographic information systems and risk. I completed undergraduate training in engineering physics at Royal Military College (Kingston, Ontario), did a masters degree in civil (geotechnical) engineering at University of British Columbia (Vancouver), and doctorate in geological engineering at Queen's University (Kingston). I was a military engineer for several years at the beginning of my career, and did design and construction work across Canada and abroad. I've worked a few years for the federal government managing large environmental clean up projects in Canada's arctic, and I've worked across Canada, on both coasts and in the middle, as a consulting geotechnical engineer. My work has taken me everywhere in Canada's north, to most major Canadian cities and many small Canadian towns, and to Alaska, Chile, Bermuda, the Caribbean, Germany, Norway, Sweden, Bosnia, and Croatia. My main "hobby" is competitive distance running, which I may write about in future.
This entry was posted in Prime Numbers, Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s