1
$\begingroup$

Given a set of 10 integers $A = a_1, a_2, \cdots a_{10}$, is there an efficient algorithm which can tell me what's the probability a randomly chosen integer between $1$ and $10^{10}$ is NOT divisible by any member of this set.

I understand the Inclusion-Exclusion principle can be used to solve this problem but I can't figure out how to implement it so that it works efficiently.

Note: When I say "efficient", I mean polynomial time, yet I am not entirely sure what qualifies as polynomial time is this case as both variables are fixed.

$\endgroup$

1 Answer 1

2
$\begingroup$

Let $\mathbf x$ be a random number in the range $1,\ldots,N$, and let $E_i$ denote the event that $\mathbf x$ is divisible by $a_i$. You are interested in the probability that none of the events $E_1,\ldots,E_m$ happen (in your case, $m = 10$). Using the inclusion-exclusion principle, this reduces to computing the probability of the events of the form $E_{i_1} \land \cdots \land E_{i_k}$, that is, $\mathbf x$ is divisible by all of $a_{i_1},\ldots,a_{i_k}$. Since a $\mathbf x$ is divisible by a bunch of numbers iff it is divisible by their LCM, it suffices to determine the probability that $\mathbf x$ is divisible by $a$.

Among $1,\ldots,N$, the numbers divisible by $a$ are $$ a,2a,3a,\ldots,\lfloor N/a \rfloor a, $$ in total $\lfloor N/a \rfloor$ numbers. Hence the probability that $\mathbf x$ is divisible by $a$ is exactly $$ \frac{\lfloor N/a \rfloor}{N}. $$

$\endgroup$
6
  • $\begingroup$ Sorry, can you clarify what does the second subscript 1 to k mean? Is this just the notation for the inclusion-exclusion principle? $\endgroup$
    – Baksel
    Commented Apr 24, 2020 at 20:43
  • $\begingroup$ It's what you get when applying the inclusion-exclusion principle. If you work it out, you'll see what it means. $\endgroup$ Commented Apr 24, 2020 at 20:53
  • $\begingroup$ Ok, if I'm understanding correctly, this is basically just applying the inclusion-exclusion principle and then computing the probability for each of the resulting summands. This seems like it wouldn't be efficient though, it would run in exponential time, no? $\endgroup$
    – Baksel
    Commented Apr 24, 2020 at 21:18
  • $\begingroup$ That's right. It's exponential time in 10. But 10 is a small constant, and $2^{10}$ is only 1024. $\endgroup$ Commented Apr 24, 2020 at 21:22
  • $\begingroup$ I suppose that would be fine, yes, I am still curious if there is some optimization though $\endgroup$
    – Baksel
    Commented Apr 24, 2020 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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