How many numbers do a given set of primes generate as a fraction of all natural numbers Part 1

Let's say you want to know how you might represent all the multiples of the number $2$ as a fraction of all natural numbers. You simply observe that the multiples of the number $2$ "cover" only half of all natural numbers, and conclude that this number is simply $\frac{1}{2}$.

You wonder if instead of being given only the number $2$, you would have been given the numbers $2,3$ and were asked the same question what would the answer be? you try the same approach as before, all the multiples of $2$ cover $\frac{1}{2}$ of all numbers, and all the multiples of $3$ cover $\frac{1}{3}$ of all numbers. so is the answers simply $\frac{1}{2}+\frac{1}{3}=\frac{5}{6}$?

You can see by creating a simple table that you only need to check all the numbers up to $2\times3$ because the multiples of $2$ and $3$ create a unique pattern of size $2\times3$ that constantly repeats itself. Another way to look at it is to see that after $2\times3$ all the numbers you would get would be simple multiplications of the numbers you already got, and as such would not add any further information, but would keep the ratio of covered numbers to non-covered numbers.

So you create a simple table of all the numbers up to $2\times3=6$ to test your hypothesis and check if this is indeed the answer.

and you notice that contradictory to what you expected, only $\frac{4}{6}$ of the numbers ended up covered, and you can already see where you made the mistake, you marked $6$ twice. so you update your answer to be $\frac{1}{2}+\frac{1}{3}-\frac{1}{2\times3} = \frac{4}{6} = \frac{2}{3}$

You try taking it a bit further and ask what would the answer be if you would have been given $2,3,5$? learning from past experience you confidently say that the answer must be $\frac{1}{2}+\frac{1}{3}+\frac{1}{5}-\frac{1}{2\times3}-\frac{1}{2\times5}-\frac{1}{3\times5} = \frac{21}{30}$ but just to be sure you make up another table just like before up to $2\times3\times5=30$

But you notice that 22 numbers are covered and not 21 as you predicted. You soon notice that the only number which stand out from the bunch is the number $30$ and you notice that while it was marked 3 times at the start, you also took it down 3 times by unmarking it 3 times with $-\frac{1}{2\times3}-\frac{1}{2\times5}-\frac{1}{3\times5}$ leaving it with 0 markings even thought it is by all means a multiple of (2,3,5). So the correct equation is $\frac{1}{2}+\frac{1}{3}+\frac{1}{5}-\frac{1}{2\times3}-\frac{1}{2\times5}-\frac{1}{3\times5}+\frac{1}{2\times3\times5} = \frac{22}{30}=\frac{11}{15}$

But you don't think this is enough and want to generalize your equation so that it would fit any sequence of primes you could throw on it.

You start by laying out all the equations you already have:

For $2$ you have $\frac{1}{2}$

For $2,3$ you have $\frac{1}{2}+\frac{1}{3}-\frac{1}{2\times3}$

And for $2,3,5$ you have $\frac{1}{2}+\frac{1}{3}+\frac{1}{5}-\frac{1}{2\times3}-\frac{1}{2\times5}-\frac{1}{3\times5}+\frac{1}{2\times3\times5}$

It seems pretty obvious.

Given a set of primes $S=p_1,p_2,p_3,p_4,p_5...p_n$, you simply add all number which has $1$ as their numerator and $p_x$ as their denominator.

Then you subtract from the resulting sum by the sum of all the numbers which has $1$ as their numerator and a permutation of size $2$ of the set $S$ as their denominator.

Then you add to the resulting sum the sum of all the numbers which has $1$ as their numerator and a permutation of size $3$ of the set $S$ as their denominator.

And so on until you reach a permutation of size $n$, at which point if $n$ is even you subtract $\frac{1}{p_1\times p_2...\times p_n}$ and if it's odd, you add it.

A more formal way of putting it is

Given a set of primes $S=p_1,p_2,p_3,p_4,p_5...p_n$, the corresponding equation would be

$(\frac{1}{p_1}+\frac{1}{p_2}+\frac{1}{p_3}...+\frac{1}{p_n}) - (\frac{1}{p_1\times p_2}+\frac{1}{p_1\times p_3}...+\frac{1}{p_1\times p_n}+\frac{1}{p_2\times p_3}+\frac{1}{p_2\times p_4}...+\frac{1}{p_2\times p_n}...+\frac{1}{p_{n-1}\times p_n})+(\frac{1}{p_1\times p_2\times p_3}+\frac{1}{p_1\times p_2\times p_4}...+\frac{1}{p_1\times p_{n-1}\times p_n}+...+\frac{1}{p_{n-2}\times p_{n-1}\times p_n})...\pm \frac{1}{p_1\times p_2...\times p_n}$

This equation can be rearranged as

$f_m(S) =$ the sum of all products of all permutations of size $m$ of S

$\frac{f_{n-1}(S)-f_{n-2}(S)+f_{n-3}(S)-f_{n-4}(S)+f_{n-5}(S)...\pm 1}{p_1\times p_2...\times p_n}$

Confident in your equation you write a simple program that would calculate this equation value for you , and give you trusty computer a order to run it on the set of the first 500 primes. Your computer seems to keep working and working on it, but days on it still hasn't found a solution! checking to see if you got something wrong you remember that the equation for k-permutations of n is $\frac{n!}{(n-k)!}$ and you soon realize that due to the enormous nature of the numbers you get, in order to solve this equation your computer has to run for many times the age of the universe in order to calculate the answer even for the first 500 primes!

So what would you do next?

Well from here on I'll guide you on how to reach to a solution that has a computational efficiency of $O(n^2)$ instead of $O(n!)$

I challenge you to solve it for yourself, this problem is not as easy as it looks at first sight, and not as hard as it looks at second sight $:$)

update: posted the answer to the list containing the first 500 primes. If you managed to reach the answer yourself congrats! The Answer

Part 2