Removing every 2nd integer of all numbers, removes 50% of all numbers
Removing every 3rd integer of all numbers, removes ~33% of all numbers
Removing every 2nd and 3rd integer of all numbers, removes ~66% of all numbers
The equation I've come up with that takes two inputs and returns the ratio of numbers removed vs total is:
$$
\begin{align}
f(a,b)&=\frac{1}{a}+\frac{1}{b}-\frac{1}{ab}\\\\
f(2,3)&=\frac{1}{2}+\frac{1}{3}-\frac{1}{2\times3}\approx 66.6\%\\\\
\end{align}
$$
This equation has been verified with Octave (a Matlab clone) with the following equation code: 1-(sum(prod(!!mod([2:(N+1)],[a b]'))))/N where N has been large and a and b has been arbitrary numbers.
I've tried to envision the problem as overlapping circles, where you remove some parts and add the parts that gets removed twice, or "thrice".
My attempt at extending it to 3 inputs looks as follows:
$$
\begin{align}
f(a,b,c)&=\frac{1}{a}+\frac{1}{b}+\frac{1}{c}-\frac{1}{ab}-\frac{1}{bc}-\frac{1}{ac}+\frac{1}{abc}\\\\
f(2,3,5)&=\frac{1}{2}+\frac{1}{3}+\frac{1}{5}-\frac{1}{2\times3}-\frac{1}{3\times5}-\frac{1}{2\times5}+\frac{1}{2\times3\times5}\approx 73.3\%\\\\
\end{align}
$$
The equation above is verified yet again through the code above by just adding a c term.
I want to extend this equation further for more arguments (in the hundreds) so I can see how many numbers there are left after removing primes and all numbers containing those prime numbers.
This gets messy very fast as the number of inputs increases.
- Am I reinventing the wheel?
- Is there a better approach for finding the ratio when there are hundreds or even thousands of inputs to this equation?
- Is there a pattern that I cannot see, like $f(a,b,c) = f(a,c)\times f(b,c)\times f(a,b)$? (this isn't it)
Please edit this question if you think it has bad tags or text or title.
Best Answer
The formula you are looking for is this: $$ f(a_1,a_2,\ldots,a_n)=1-\left(1-\frac{1}{a_1}\right)\left(1-\frac{1}{a_2}\right)\cdots\left(1-\frac{1}{a_n}\right), $$ but only if $a_1,\ldots,a_n$ are pairwise coprime (which seems to be the case, given your motivations).
Here's some intuition as to why that formula holds. Pick a random integer $k$: the probability that $k$ is not a multiple of $a_i$ is $1-\frac{1}{a_i}$. You can convince yourself that these events are independent (if the $a_i$'s are coprime, that is), so the probability that $k$ is not a multiple of any of the $a_i$'s is simply the product of the probabilities, i.e. $\left(1-\frac{1}{a_1}\right)\left(1-\frac{1}{a_2}\right)\cdots\left(1-\frac{1}{a_n}\right)$. Now take the complement and you are done.