Elaboration of the Recursive Pattern in Developing the Primes


In earlier posts, for example this one:
http://www.petequinnramblings.wordpress.com/2011/12/13/a-more-efficient-implementation-of-eratosthenes-sieve/
(sorry I can’t figure out how to insert hyperlinks)

I have described a recursive pattern that captures the mechanics of the sieve of Eratosthenes in apparently much simpler form, leading to a symmetric pattern of non-primes and “possible primes” within successive primorials. Let me attempt to elaborate and hopefully also simplify.

Consider the set of natural numbers, N, and imagine the process of successively stripping out multiples of the smallest primes, working progressively toward higher primes.

N can be subdivided into E and O, the sets of even and odd natural numbers. Within 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.

In the first stage of sieving we remove all prime numbers. This removes E from N, leaving O, the set of odd natural numbers, as candidate primes. Let’s call this set PC_1, or the set of prime candidates after sieving by P_1 = 2. Let’s call the set of confirmed non-primes NP_1.

The set E contains all multiples of 2 within the set of natural numbers. The set O, or PC_1, contains all primes greater than 2, plus all multiples of all primes greater than 2, or all composite numbers whose lowest prime divisor is greater than 2. After sieving by 2 then, we are left with 1/2 of all natural numbers as candidate primes in the set PC_1.

In the second stage of sieving, we wish to remove all multiples of 3 from the candidate primes left after sieving by 2, or from PC_1, or O, the set of odd natural numbers. This removes 1/3 of O, leaving 1/3 of 1/2 of N, or 1/6 of N, after sieving by 2 and 3. Therefore PC_2 contains 1/6 of N, and NP_1 contains 5/6 of N. If we follow the same logic for subsequent stages of sieving, it leads us to conclude that the number of candidate primes after n stages of sieving, or the number of members in the set PC_n, is equal to:

Nn = N x {product for i = 1 to n [(Pi – 1)/Pi]} — eqn (1)

This gives us the NUMBER of candidates within the set of candidate primes after n stages of sieving (which is, strictly speaking, the set of primes plus all non-primes whose lowest prime divisor is greater than Pn), but says nothing about the POSITION of non-primes removed at each stage. We have claimed a deterministic pattern in prior posts, but without substantiation. On reflection, the basis for determination of position is straightforward and obvious (with the benefit of hindsight admittedly), and simple, as it should be.

First, recall the pattern, which has been described in previous posts but can be summarized as follows:

{PC_(n+1)} = {PC_n} – P(n+1) x {PC_n} — eqn (2)

In other words, take each member of PC_n, multiply it by P(n+1) and delete the resulting set from PC_n to yield PC_(n+1).

I’ve described this recursive pattern before within the framework of successive individual, growing, primorials, but we can easily generalize to the complete set, PC_n, which is simply an endless repetition of the pattern that first appears within the first Pn# numbers. In practical terms, working with the entire sets as just described is essentially the same as the sieve of Eratosthenes and offers no particular logistical advantage. Focussing on stepwise recursion within the individual primorials removes a large number of computational steps.

But I digress… back to the basis for this evolving recursive pattern.

Within PC_n, we have a set that includes all prime numbers greater than Pn, and all composites with lowest prime divisor greater than Pn. What we do NOT have in this set, but is rather contained in NP_n, are composite numbers whose lowest prime divisor is less than or equal to Pn.

In the (n+1)-th stage of sieving, we are looking to remove all multiples of P(n+1) that have not already been removed by prior sieving by lower primes, or in other words we are looking for all composite numbers whose lowest prime divisor is EQUAL to P(n+1). Since PC_n contains no numbers with lowest prime divisor less than P(n+1), multiplication of each member of this set will yield a set of numbers with least prime divisor equal to P(n+1). Since all the natural numbers other than those in PC_n, contained in NP_n, are known to be composite numbers with lowest prime divisor less than or equal to Pn, multiplication of any member of that set will yield a new composite number with lowest prime divisor less than or equal to Pn, and will NOT yield a new member for PC_(n+1).

Hence the described pattern embedded in the recursion described by eqn (2) is valid.

————————–

The reason I set out to understand this pattern is to try to understand why my naïve estimate from the count of primes less than Pn^2 has a systematic error, which I’ve now shown through numerical experimentation to be equivalent to:

PQ(n) = Pn^2 x {product for i = 1 to n [(Pi – 1)/Pi]} ~ pi (Pn^2) x 1.1229…

Now that the pattern is understood, I may make some progress in understanding the source of this error.

My naïve estimate is based on the expectation of relatively uniform density of candidate primes within any given {PC_n}, and more specifically the assumption that this density, calculated by rearranging eqn (1) as Nn/N to give Dn = Nn/N = {product for i = 1 to n [(Pi – 1)/Pi]}, is a legitimate representation of the density of candidate primes less than Pn^2. These candidate primes lower than Pn^2 after n stages of sieving are, by definition, all prime. Unfortunately, this estimate overpredicts the true number of primes as just stated.

This overprediction tells us that the density of non-primes after n stages of sieving (composites of primes up to Pn) from 0 to Pn^2 is greater than the average density of NP_n, and that this is systematically true for all stages of sieving after the first few, with the ratio of densities converging at 1.1229…. as n –> infinity. It’s still not particularly obvious to me why this should be the case. Maybe it will come to me on a run someday…

————————————–

I thought it would be worthwhile to explore this pattern a bit to see whether there is any real computational advantage conferred by the recursive pattern. I’ll save that for another day.

———————

(I will include this snapshot in the more complete summary I am also working on, to be posted in the next day or two)

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.

3 Responses to Elaboration of the Recursive Pattern in Developing the Primes

  1. satish kumar singh says:

    Every big prime twings gives smaller prime twings. Ex 11,13…3,5 and 5,7 Ex 17, 19…….3,5 & 5,7 & 11,13……

  2. satish kumar singh says:

    Every big prime twings gives smaller prime twings .
    Ex 11,13… ( 3,5 and 5,7 )
    Ex 17, 19……. (3,5 & 5,7 & 11,13 )
    Ex 29, 31……. (3,5 & 5,7 & 11,13 & 17,19 )
    Ex 41, 43……. (3,5 & 5,7 & 11,13 & 17,19 & 29,31 )

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