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.)
Best Answer
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)}.$$