# Accuracy of approximation to inclusion-exclusion formula in prime sieve

This thing came up in a combinatorics course I am taking.

Choose a fixed set of primes $p_1,p_2,\dots,p_k$ and let $A_n$ be number of integers in $\{1,2,\dots,n\}$ which are not divisible by any of the $p_i$'s. $A_n$ is given by $n - \sum_{1\leq i_1 \leq k} \lfloor \frac{n}{p_{i_1}} \rfloor + \sum_{1\leq i_1 < i_2 < k} \lfloor \frac{n}{p_{i_1}p_{i_2}}\rfloor - \dots$. Now, if $n$ is divisible by each of the $p_i$'s then we have the simpler expression : $A_n = n \prod_{i=1}^{k}(1-\frac{1}{p_i})$(added later : note I am not assuming $n = \prod_{i=1}^{k}p_i$ here, this holds true whenever $n = c \prod_{i=1}^{k} p_i$ for some integer c, since each $\lfloor \frac{n}{p_{i_1} \dots p_{i_j}} \rfloor = \frac{n}{p_{i_1} \dots p_{i_j}}\ )$.

Another student pointed out that even if $n$ does not have $\prod_{i=1}^{k} p_i$ as a factor, the approximation $B_n = n \prod_{i=1}^{k}(1-\frac{1}{p_i})$ to $A_n$ is quite close in some specific cases. It is easy to see that $\lim_{n\to\infty}\frac{A_n - B_n}{n}=0$ as $\lim_{n\to\infty}\frac{1}{n}\lfloor \frac{n}{p_{i_1}p_{i_2}\dots p_{i_j}} \rfloor \to \frac{1}{p_{i_1}p_{i_2} \dots p_{i_j}},$ however that is not strong enough to imply that $A_n - B_n$ will be always close. Is there any way to analyze how well this approximation will perform in general? I am interested in the worst case for small to moderately sized $n$.

Just to give a feel of how close $A_n$ and $B_n$ can get, assuming the set of primes is $\{2,3,7\}$ we have (assuming my program is correct):

n     A(n)     B(n)
17    5    4.86
27    8    7.71
37    11      10.57
107   31      30.57
1111  318     317.43
3001  858     857.43
4007  1145    1144.86
5000  1429    1428.57 .

-
What if n is the product of the $p_i$ + 1? The n will be as far as possible from the number you are using to estimate $A_n$. Set n to "the product of the $p_i$ + 1" and maybe see what happens? –  futurebird Oct 24 '10 at 0:14
If $n = \prod_{i=1}^k p_i$ then $A_n = \varphi(n)$, the Euler totient function. –  Mike Spivey Oct 24 '10 at 5:35

To help with the notation I will change your $k$ to an $m$, so we have

$$A_n = n - \sum \lfloor \frac{n}{p_i} \rfloor + \sum \lfloor \frac{n}{p_i p_j} \rfloor - \sum \lfloor \frac{n}{p_i p_j p_k} \rfloor + \cdots,$$

where the summations are over distinct primes in our set $\lbrace p_1,p_2,\ldots,p_m \rbrace ,$ and

$$B_n = n \prod_{i=1}^m \left( 1- \frac{1}{p_i} \right).$$

Using $x \ge \lfloor x \rfloor > x – 1$ we have

$$A_n \ge n - \sum \frac{n}{p_i} + \sum \frac{n}{p_i p_j} - \binom{m}{2} - \sum \frac{n}{p_i p_j p_k} + \sum \frac{n}{p_i p_j p_k p_l} - \binom{m}{4} + \cdots.$$

Noting that $$\binom{m}{0}+\binom{m}{2}+\binom{m}{4} \cdots = 2^{m-1},$$

we obtain $A_n \ge B_n – 2^{m-1}.$ Similarly, we have $A_n \le B_n + 2^{m-1}$ and hence we can bound

$$\left| \frac{A_n – B_n}{n} \right| \le \frac{2^{m-1}}{n} = O(1/n).$$

However, if we take $n \equiv -1 \textrm{ mod } \prod_{i=1}^m p_i$ then we have

$$A_n – B_n = \prod_{i=1}^m \left( 1- \frac{1}{p_i} \right) = \text{a constant.} \quad (1)$$

So the difference is a constant infinitely often.

EDIT: Since the differences between the $\lfloor \frac{n}{p_i p_j \ldots} \rfloor$ and the $\frac{n}{p_i p_j \ldots}$ are a maximum when $n \equiv -1 \textrm{ mod } \prod_{i=1}^m p_i$ it appears we have

$$A_n – B_n \le \prod_{i=1}^m \left( 1- \frac{1}{p_i} \right), \quad (2)$$

with equality when $n \equiv -1 \textrm{ mod } \prod_{i=1}^m p_i.$ I do not have a proof of this latter claim, although I have a proof for (1), which I hope to be able to modify to prove (2).

EDIT2: I could not find a proof of (2) because, sadly, it's not true! However, (1) is exact for the given $n.$

EDIT3:

Here's a vast improvement on my previous comments, which I believe solves your problem completely.

Suppose $n \equiv -r \textrm{ mod } \prod_{i=1}^m p_i,$ where $0 \le r < \prod_{i=1}^m p_i$ then we have

$$A_n – B_n \le r \prod_{i=1}^m \left( 1- \frac{1}{p_i} \right).$$

I proved this simply by expanding $A_n – B_n$ and doing the summations. Also, I believe the exact formula to be

$$A_n – B_n = \delta + r \prod_{i=1}^m \left( 1- \frac{1}{p_i} \right) - \Phi_P(r),$$

where $\delta = 1$ when $r$ is coprime to all the $p_i$ and $0$ otherwise, and $\Phi_P(r)$ is the number of positive integers $\le r$ which are coprime to the $p_i.$

Note that when $n=711,$ $r=9,$ $\delta = 0$ and $\Phi_P(9) = 2,$ $P=\lbrace 2,3,5 \rbrace,$ so the above formula gives $$A_{711}-B_{711} = 9 \left( 1 - \frac{1}{2} \right) \left( 1 - \frac{1}{3} \right) \left( 1 - \frac{1}{5} \right) – 2 = 0.4$$ which agrees with your $190-189.6 = 0.4$

When $n=107,$ $r=19,$ $\delta = 1$ and $\Phi_P(19) = 6,$ $P=\lbrace 2,3,7 \rbrace,$ so we have $$A_{107}-B_{107} = 1 + 19 \left( 1 - \frac{1}{2} \right) \left( 1 - \frac{1}{3} \right) \left( 1 - \frac{1}{7} \right) – 6 = 0.42857\ldots,$$

which is also in agreement with the rounded figures you've given in the question.

Sorry, I do not have time to type up the full proof.

-
@acarchau If you mean $A_n$ to be something other than $\phi(n)$ or $B_n$ can you please clarify the situation in the question. Thanks. –  Derek Jennings Oct 24 '10 at 9:41
@Derek: $A_n$ need not be $\phi(n)$, we might choose the set of primes to be $2,3$ and $A_n$ will count how many numbers less than $n$ are not divisible by 2 or 3. –  ACARCHAU Oct 24 '10 at 16:03
@acarchau Ok. Here's my new answer in the light of your comment. –  Derek Jennings Oct 25 '10 at 11:28
@Derek, The actual accuracy seems to be much better than $2^{m-1}$ in general. For example, if n = 711, and the primes are 2,3,5 then (if my program is correct) $A_n = 190$ and $B_n = 189.6$, I wont be surprised if the change in signs leads to a lot of cancellation and using $x - 1 < \lfloor x \rfloor \leq x$ leads to an extremely pessimistic bound. –  ACARCHAU Oct 25 '10 at 15:38
@acarchau Yes, that's right. The first part of my answer is just a rough bound. It's the second part you really want, but I've proved (1) and only conjectured (2). If time permits... –  Derek Jennings Oct 25 '10 at 15:52

This might be slightly off tangent, but it's definitely in the spirit of your post, and is found at the beginning of most texts in sieve theory.

When your fixed set of primes is the first $k$ primes and $n = p_{k}^2$ then $B_{n}$ is the main term of the sieve of Eratosthenes-Legendre, which gives an approximation for the number of primes in the interval $[p_{k}, p_{k}^2]$. In this setting Merten's theorem gives an asymptotic for $B_{n}$. (It's called Merten's Third theorem in the Wikipedia page). However, an appeal to the prime number theorem shows that this is a reasonably bad approximation, and that $B_{n}$ overestimates the number of primes by a factor of $2e^{-\gamma}$ where $\gamma$ is the Euler-Mascheroni constant.

Terry Tao has a good blog posting on why repeated use of the inclusion-exclusion principle yields non-optimal results.

-
Terence Tao's blog post is excellent but somewhat long: the main relevant point is that inclusion-exclusion is useless once the number of primes is larger than about log N, where you're sieving over, say, [N, 2N]. –  Qiaochu Yuan Oct 26 '10 at 13:09