1
$\begingroup$

The sieve of Eratosthanes sequentially identifies primes by using smaller known primes to discard numbers from a list, eventually leaving behind only other primes. At the nth step, we use $p_n$ and remove from the list all multiples of $p_n$ larger than $p_n$. At this point there will remain many numbers larger than $p_n$ that have not been discarded. They are of two types: Primes, and composites that are destined to be removed in subsequent sieving steps. We can ask, What is the smallest composite (call it $c_m$) that has not yet been discarded?

Since it is composite, it has prime factors. But since every number with prime factors $\le p_n$ has been sieved out, the prime factors of $c_m$ must all be larger than $p_n$. Hence, $c_m>p_n^2$. Any number $<p_n^2$ not removed prior to sieving with $p_n$ must be a prime. In other words, $p_n$ only exerts a (distinct) sieving effect on numbers larger than $p_n^2$

It might be the case that for other simple sieves, the effect of each particular sieving element (i.e. what corresponds to $p_n$ in the sieve of Eratosthanes) also might not begin to exert its distinct effect in a range close to that element. In order to read and learn about this (assuming it is an appreciated behavior), I first have to know what it is called.

Simple question: Does this behavior (or property) have a name?

Added by edit: In the comments I was asked what other sieves I might have in mind. Not being proficient in sieve theory, I demurred. But there is one analogous sieving process that bears mentioning. With regard to the sieve of Eratosthanes, we sieve by discarding multiples of primes, $kp$, with the following constraints: I. $k>1$; II. There is no (necessary) upper bound on the list being sieved; III. Every prime is used; IV. We identify (as primes) the numbers that are not discarded.

We can sieve by discarding $kp$ using slightly modified constraints, viz: I. $k\ge 1$; II. The upper bound on the list is an integer $m$; III. We only use primes that divide $m$; IV. We count the numbers that are not discarded. In this case, what we obtain is the totient function, $\phi(m)$.

$\endgroup$
  • $\begingroup$ The smallest composite not yet sieved by the primes up to $p_n$ is exactly $p_{n+1}^2$. What other "simple sieves" are you thinking of? $\endgroup$ – Greg Martin May 3 at 2:10
  • $\begingroup$ @Greg Martin I am not a student of sieves, but I am aware that some sieves involve the use of complex formulas, so I used the word "simple" to distinguish from that type of sieve. I have no specific such sieves in mind. I had some faint hope that if this behavior (displacement of the action of the element) were general, reading about it might introduce me to other "simple" sieves. $\endgroup$ – Keith Backman May 3 at 3:09
  • $\begingroup$ So are any of the following sieves simple: Atkin, Sundaram, Lehmer, Euler ? $\endgroup$ – Roddy MacPhee May 3 at 12:38
  • $\begingroup$ A quick peek at Wikipedia articles suggests to me that Sundaram and Euler sieves, while not as simple as Eratosthanes, are reasonably simple, and Atkins is decidedly more complex in its theory, even if it may be more efficient in practice. For Lehmer, I could only find the description of a machine, no exposition on the mathematics driving it, so I can form no opinion. Sundaram is interesting in that the sieving step does not identify primes per se, but integers that can be doubled and augmented by $1$ to generate primes. $\endgroup$ – Keith Backman May 3 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.