1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Note what you're doing is related to the Inclusion–exclusion principle, where the example section of Counting integers shows how it applies, although you would need to use $1$ minus their result divided by $n$ to get what you're specifically doing. $\endgroup$ Apr 25 '19 at 0:54
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Ah, so I was reinventing the wheel, it's good that I stopped at 3 inputs. Where does that formula otherwise pop up? I doubt it is for the same reasons as mine. $\endgroup$ Apr 24 '19 at 22:11
  • 1
    $\begingroup$ @Harry Svensson Check my edit for a somewhat informal motivation. I don't know if the formula "pops out" somewhere else, but it is very intuitive (if you look at it from the right perspective). $\endgroup$
    – Delfad0r
    Apr 24 '19 at 22:20
  • 1
    $\begingroup$ @HarrySvensson For the $a_i$ being the corresponding primes, i.e., $p_i = a_i$, then the formula for the product comes from Möbius inversion, such as at Möbius Function where it states that $\frac{\phi(n)}{n} = \sum_{d \mid n}\frac{\mu(d)}{d}$. Using $n$ being the primorial up to some value, plus the definition at Euler's totient function of $\varphi(n)=n\prod_{p\mid n}\left(1-{\frac {1}{p}}\right)$, gives the stated result. $\endgroup$ Apr 25 '19 at 0:46

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.