0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are there or's or and's in between $3, 5, 7, 11$? $\endgroup$ – Randall Mar 31 '18 at 3:38
  • $\begingroup$ AND's (let me clear that out) $\endgroup$ – tomtomtom Mar 31 '18 at 3:41
  • $\begingroup$ Isn't $x$ coprime to all if and only if it is coprime to $3 \times 5 \times 7 \times 11$? $\endgroup$ – Randall Mar 31 '18 at 3:43
  • $\begingroup$ Exactly! But how do you calculate that? Don't use PIE (Inclusion-Exclusion Principle). I am looking for an approximation with the error analysis instead of an actual way to yield the answer $\endgroup$ – tomtomtom Mar 31 '18 at 3:43
  • $\begingroup$ It's not clear to me what role $n=1000$ plays here. $\endgroup$ – Randall Mar 31 '18 at 3:44
0
$\begingroup$

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$.

$\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.