I am reading Cojocaru and Murty's Introduction to Sieve Methods and their Applications. They wait until Chapter 5 to discuss the Sieve of Eratosthenes for finding primes - and their version of it is not very algorithmic. She writes the inequality:

$$ \#\{ n \leq x : n \text{ not divisible by }p< z \} \approx x \prod_{p < z}\left( 1 - \frac{1}{p} \right) + O(...)$$

This makes sense the number of primes should be proportional to the residue classes which you left out upon sieving. The textbook spends a lot of time estimating the main $\prod_{p < z}\left( 1 - \frac{1}{p} \right)$ and the error term $O(...)$.

How do we turn this equation into an algorithm?

Knowing the sieve algorithm already I remember to keep the smallest prime, and we sieve accordingly.

The other example in that chapter focuses on twin primes. They given an approximation like so:

$$ \#\{ n \leq x : n \not \equiv 0,-2 \text{ for }p< z \} \approx x \prod_{p < z}\left( 1 - \frac{2}{p} \right) + O(...)$$

The book says, unfortunately, these are not the twin primes - I don't understand why. It says the number of twin primes is less than

$$ \#\{ \text{ primes }p < z \} + \#\{ n \leq x : n \not \equiv 0,-2 \text{ for }p< z \} = \pi(z)+ x \prod_{p < z}\left( 1 - \frac{2}{p} \right) $$

If this were an algorithm I take it to mean you still have to compute primes up to a certain point, but not all of the primes up to $x$ in order to find the twin primes.

The book is not very clear in many places, so I have put in my - possibly wrong - interpretation of the equations in certain spots. Maybe someone among you has the book or knows the Sieve of Eratoshenes very well.

My main complaint about the book is that it doesn't provide algorithms, just estimates.

  • $\begingroup$ this all has been somewhat revolutionized by Zhang's recent results. nobody seems to have converted his findings into algorithms yet but presumably there are basic algorithms derivable from the new analysis. $\endgroup$ – vzn Aug 15 '14 at 14:59
  • $\begingroup$ @vzn unrelated : what would be the uses of finding large twin primes, or finding them quickly? $\endgroup$ – john mangual Aug 15 '14 at 15:49
  • $\begingroup$ are you asking for applications? a completely different question... fyi there are multiple such algorithms related to twin primes that one could imagine/ formulate, eg compute the nth twin prime pair, find large pairs, etc... so maybe/ probably your question needs to be more specific to have an answer... $\endgroup$ – vzn Aug 15 '14 at 16:15
  • 4
    $\begingroup$ In view of the last sentence of your question, I can’t help the feeling that you misunderstand what the term “sieve theory” means. It’s a subfield of number theory whose goal is to prove estimates, it has nothing to do with algorithms. $\endgroup$ – Emil Jeřábek Aug 16 '14 at 11:12
  • 1
    $\begingroup$ Anyway, the algorithm suggested by your last equation is to first compute the list of all primes below $z$, output those that are twinned, take a second list containing numbers below $x$, and for each $p$ on the first list, sieve out all multiples of $p$ and their twins from the second list. The result will be accurate only if $z\ge\sqrt x$ or so, otherwise you’ll get a superset of twin primes. As far as I can see, it is computationally more efficient to just employ the usual sieve of Eratosthenes and weed out non-twin primes upon output. $\endgroup$ – Emil Jeřábek Aug 16 '14 at 12:08

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.