5
$\begingroup$

Let $\pi(n)$ denote the number of primes not greater than $n$, and $p_k$ the $k$th prime, so that $p_{\pi(n)}$ denotes the largest prime not greater than $n$. I'm interested in the value of the following sum: $$S(n) = \left(1 - \frac12\right) + \left(1 - \frac12\right)\left(1 - \frac13\right) + \left(1 - \frac12\right)\left(1 - \frac13\right)\left(1 - \frac15\right) + \dots + \prod_{k = 1}^{\pi(n)}\left(1 - \frac1{p_k}\right)$$

The $m$th term of the series is the product of $\left(1 - \frac{1}{p}\right)$ for the first $m$ primes; there are $\pi(n)$ terms in the sum; the last term is the product of $\left(1 - \frac{1}{p}\right)$ over all primes $p \le n$. So to state it more precisely, $$S(n) = \sum_{m=1}^{\pi(n)} \prod_{k=1}^m \left(1-\frac{1}{p_k}\right)$$

Specifically, what are the asymptotics of $S(n)$ as a function of $n$?


Background: this comes up in the analysis of a naive algorithm for generating all primes up to $n$, which is to sequentially try dividing each number by all known smaller primes:

  • The most naive algorithm is for each $m \le n$, divide it (i.e. just find remainder) by each number $d \le m$, and declare $m$ prime if all those remainders are nonzero. This performs $\sim m$ arithmetic operations (finding remainders) for each $m$, so overall it would perform a number of remainder-operations proportional to $1 + 2 + \dots + m + \dots + n = \Theta(n^2)$.
  • Somewhat better is this algorithm, which for each $m \le n$, divides it by each prime $p \le m$ until a zero remainder is found: so all numbers $m$ are tried dividing by $2$, the numbers divided by $3$ would be those that survive (the odd numbers), the numbers divided by $5$ would be the numbers divisible neither by $2$ nor $3$ (thus $\left(1 - \frac12\right)\left(1 - \frac13\right)$ of the numbers), etc.
  • I'm fairly sure this would be worse than the Sieve of Eratosthenes, which does about $\left(\frac{n}{2} + \frac{n}{3} + \frac{n}{5} + \dots + \frac{n}{p_{\pi(n)}}\right) = \Theta(n \log \log n)$ arithmetic operations (none of them division operations actually).

(I'm also aware of various faster algorithms and simple ways to make this faster, but I'm interested in the analysis of this algorithm specifically.)

$\endgroup$
  • 1
    $\begingroup$ Is the typical term of the series $$\prod_{k = 1}^{\pi(n)}\left(1 - \frac1{p_k}\right),$$ as written at the end of the formula for $S_n$, or $$\prod_{k = 1}^{n}\left(1 - \frac1{p_k}\right),$$ as the third term of $S_n$ seems to indicate? $\endgroup$ – Did Apr 15 '16 at 16:51
  • $\begingroup$ @Did I'm afraid I don't understand the difference -- I put the final term of $S_n$ only to indicate that we stop at the largest prime $\le n$; otherwise the typical expression is the same, right? $\endgroup$ – ShreevatsaR Apr 15 '16 at 16:53
  • $\begingroup$ @user1952009 All the terms of the series are different; there is no weighting. I'm trying to understand the reason for the confusion... how could I make it clearer? $\endgroup$ – ShreevatsaR Apr 15 '16 at 16:54
  • 1
    $\begingroup$ @user1952009 I mean $S_N = \sum_{m=1}^{\pi(N)} \prod_{k=1}^m (1-\frac{1}{p_k})$ $\endgroup$ – ShreevatsaR Apr 15 '16 at 16:57
  • 2
    $\begingroup$ Just to give an idea of growth: $S_1=0.5,S_{10}=2.4,S_{100}=11.8,S_{500}=41.9,S_{1000}=74.4,S_{10000}=546.9$ $\endgroup$ – almagest Apr 15 '16 at 16:59
4
$\begingroup$

From Mertens' theorem we have $$\prod_{k\leq m}\left(1-\frac{1}{p_{m}}\right)\sim\frac{1}{\log\left(p_{m}\right)e^{\gamma}} $$ and so $$S\left(n\right)\sim\frac{1}{e^{\gamma}}\sum_{m\leq\pi\left(n\right)}\frac{1}{\log\left(p_{m}\right)}. $$ Now put $x=p_{\pi\left(n\right)} $. We can write the sum as $$\sum_{m\leq\pi\left(n\right)}\frac{1}{\log\left(p_{m}\right)}=\sum_{p\leq x}\frac{1}{\log\left(p\right)} $$ and so using Abel's summation we have $$\sum_{p\leq x}\frac{1}{\log\left(p\right)}=\frac{\pi\left(x\right)}{\log\left(x\right)}+\int_{2}^{x}\frac{\pi\left(t\right)}{t\log^{2}\left(t\right)}dt $$ and since from the Prime Number Theorem (PNT) holds $$\pi\left(x\right)\sim\frac{x}{\log\left(x\right)} $$ we have $$\sum_{p\leq x}\frac{1}{\log\left(p\right)}\sim\frac{x}{\log^{2}\left(x\right)}+\int_{2}^{x}\frac{1}{\log^{3}\left(t\right)}dt $$ $$=\frac{x}{2\log^{2}\left(x\right)}+\frac{\textrm{Li}\left(x\right)}{2}-\frac{x}{2\log\left(x\right)}+\frac{\log\left(2\right)+1}{\log\left(2\right)} $$ where $\textrm{Li}\left(x\right)$ is the logarithmic integral. Note the that from PNT we have $$p_{\pi\left(n\right)}\sim\pi\left(n\right)\log\left(\pi\left(n\right)\right)\sim n\left(1-\frac{\log\left(\log\left(n\right)\right)}{\log\left(n\right)}\right).$$ I added some details. Now since holds $$\textrm{Li}\left(x\right)=\frac{x}{\log\left(x\right)}\sum_{k=0}^{n}\frac{k!}{\log^{k}\left(x\right)}+O_{n}\left(\frac{x}{\log^{n+2}\left(x\right)}\right) $$ which can be proved iterating the integration by parts we can note that $$\frac{\textrm{Li}\left(x\right)}{2}-\frac{x}{2\log\left(x\right)}=\frac{x}{2\log^{2}\left(x\right)}+O\left(\frac{x}{\log^{3}\left(x\right)}\right)\sim\frac{x}{2\log^{2}\left(x\right)} $$ so $$\sum_{p\leq x}\frac{1}{\log\left(p\right)}\sim\frac{x}{\log^{2}\left(x\right)} $$ and note that $$n\left(1-\frac{\log\left(\log\left(n\right)\right)}{\log\left(n\right)}\right)\sim n $$ so finally $$S\left(n\right)\sim\frac{n}{e^{\gamma}\log^{2}\left(n\right)}.$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ What's the rate of convergence for Mertens's theorem? Does it have relative error $O(1/\log n)$ or something significantly sharper? $\endgroup$ – Erick Wong Apr 15 '16 at 20:18
  • $\begingroup$ @ErickWong We have $$\prod_{p\leq N}\left(1-\frac{1}{p}\right)=\frac{1}{e^{\gamma}\log\left(N\right)}+O\left( \frac{1}{\log^{2}\left(N\right)}\right).$$ $\endgroup$ – Marco Cantarini Apr 15 '16 at 20:28
  • $\begingroup$ Ah okay so then probably only the main term of the asymptotic expansion is accurate with regard to the original sum. $\endgroup$ – Erick Wong Apr 15 '16 at 20:30
  • $\begingroup$ Although I "accepted" this answer as it was the only one posted (thank you!), I still haven't figured out from this answer what the actual asymptotics of $S(n)$ are, in terms of $n$. $\endgroup$ – ShreevatsaR May 16 '16 at 17:33
  • $\begingroup$ @ShreevatsaR Have I to add some details? What did you not understand? $\endgroup$ – Marco Cantarini May 16 '16 at 17:49
1
$\begingroup$

Sorry I asked the question and then forgot to come back here… I figured out the asymptotics I cared about, to the level of detail I cared about, by simply thinking about the actual algorithm that inspired this question.

To recap the question, the algorithm is the following. Given $n$, we want to find all primes $\le n$:

  • Maintain a list of known primes (initially empty).
  • For each number $r$, where $2 \le r \le n$,
    • try dividing $r$ by each known prime $p < r$ (from the above list)
      • If you encounter a zero remainder, stop (move on to the next $r$).
    • Else (if all remainders are nonzero), then append $r$ to the list of known primes, and continue.

Note that in this algorithm,

  • for every number $r$ ($2 < r \le n$), we try dividing $r$ by $2$
  • for every odd number $r$ ($3 < r \le n$), we try dividing it by $3$ as well (so $1/2$ of the numbers greater than $3$)
  • for every number $r$ not divisible by $2$ or $3$ ($5 < r \le n$), we try dividing it by $5$ as well (so a fraction $(1-1/2)(1-1/3)$ of those numbers).
  • in general, we try dividing by a prime number $p_m$ all the numbers $r > p_m$ that are not divisible by any of the first $m-1$ primes, so a fraction $\prod_{k=1}^{m-1}(1-1/p_k)$ of them.

So the number of division operations the algorithm performs is, and the running time of the algorithm is asymptotically equal to, $$\sum_{m=1}^{\pi(n)}(n-p_m)\prod_{k=1}^{m-1}\left(1-\frac{1}{p_k}\right)$$ (slightly different from the one asked in the question, but I guess it should have the same asymptotics as multiplying the one in the question by $n$ throughout).


Now an obvious upper bound on the algorithm's running time is $n\pi(n)$: we divide each number $r$ by at most $\pi(n)$ primes.

And an obvious lower bound is $0 + 1 + 2 + \dots + (\pi(n) - 1) = (\pi(n)-1)\pi(n)/2$: to determine each prime we divide it by all smaller primes.

This puts the asymptotics as being between $\Theta(\pi(n)^2)$ and $\Theta(n\pi(n))$, so between $\frac{n^2}{\log n \log n}$ and $\frac{n^2}{\log n}$. Similarly, the quantity actually asked in the question should be between $\frac{n}{\log n \log n}$ and $\frac{n}{\log n}$.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.