PIE in twisted manner

38 Views Asked by At

For a random number $n=1000$ we are interested to find the number of integers $\leq 1000$ co-prime to $3,5,7$ and $11$. How to find that out?

I am not getting any idea to find the value out. One way is to use the principle of inclusion exclusion but I am not going to use that. What if there had been more primes?

When you propose a method to do that, do tell how you big you expect the error to be during approximation? Show the error analysis, not actual difference in the actual and the approximated answer which one can get after some calculations.

1

There are 1 best solutions below

0
On

The approximation would be to assume that being divisible by each of $3,5,7,11$ is independent, so in any range we would expect the fraction of numbers coprime to all of those is $\frac 23 \cdot \frac 45 \cdot \frac 67 \cdot \frac {10}{11}=\frac {480}{1155}$ The fact that the denominator is larger than $1000$ would worry me. If you asked for numbers up to $10^9$, say, I would be sure this is very close. If you asked for numbers up to $1155$ I would be sure it was exact. I would expect this to be within a handful for any $n$.