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

Part 1: https://brilliant.org/discussions/thread/how-many-numbers-do-a-given-set-of-primes-can/

In the previous post we showed that if you want to calculate how many numbers a given set of primes generate as a fraction of all natural numbers using a brute force methodology would result in an efficiency of $O(n!)$.

To understand how inefficient this method is, let's assume we have in our possession an exaflop computer (one of his kind has never been built yet), which can make a billion billion calculations per second. Then to get the answer to our question with a list containing all primes up to only the 33th prime, 137, would take us approximately the age of the universe, or almost 14 billion years.

In order to calculate the answer for the list we need to find a method by which we could simplify the process. Our previous solution was what is called in the school of computer science a Greedy Algorithm, in which we calculate each element of the solution separately, potentially doing the same calculations over and over again. As such the method we are going to use to solve it would be Dynamic Optimization (or Dynamic Programming).

As you may recall we reached the following equation to calculate our answer

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

First, we can do away with the denominator because it would always be $p_1\times p_2\times p_3...\times p_n$, seeing it is not influenced by the numerator we can calculate it separately.

So we are left only with $f_{n-1}(S)-f_{n-2}(S)+f_{n-3}(S)-f_{n-4}(S)+f_{n-5}(S)...\pm 1$

To really understand the solution we need to understand $f_m(S)$. For you convenience here are a few examples for it:

$f_2(2,3,5) = (2\times 3)+(2\times 5)+(3\times 5)$

$f_2(2,3,5,7) = (2\times 3)+(2\times 5)+(2\times 7)+(3\times 5)+(3\times 7)+(5\times 7)$

$f_3(2,3,5,7) = (2\times 3\times 5) + (2\times 3\times 7) + (2\times 5\times 7)+ (3\times 5\times 7)$

$f_1(2,3,5,7,11) =(2)+(3)+(5)+(7)+(11)$

$f_5(2,3,5,7,11) =(2\times 3\times 5\times 7\times 11)$

As we will see, the key to solving this problem is realizing that in it's essence $f_m(S)$ depends deeply upon the result of all $f_n(S)$ where $m>n$.

For starts, you can see I already replaced it with $1$ in the main equation, but the actual main equation does not end with $1$ but with $\boxed{f_{0}(S)=1}$ which would be our first equation.

Seeing we already found the solution for $f_{0}(S)$ we might as well go for another low hanging fruit and try to solve $f_{1}(S)$.

The definition of $f_m(S)$ is that it's the sum of all products of all permutations of size $m$ of $S$. But no matter which $S$ we would be given, all permutations of size $1$ would result in all the elements comprising $S$. Since we only need to add them together we can see that $\boxed{f_{1}(S)=S_{1}+S_{2}+S_{3}+S_{4}...+S_{L}}$ where $L$ is simply the length of $S$.

Another simple observation is that if we are given $f_L(S)$ where $L$ is simply the length of $S$ there is only $1$ permutation which fits. As such $\boxed{f_{L}(S)=S_{1}\times S_{2}\times S_{3}\times S_{4}...\times S_{L}}$ where $L$ is the length of $S$.

And so we are only left with the greatest obstacle: finding the solution for $f_n(S)$ where $n\neq 0,1,L$

Let's examine $f_2(2,3,5)$

We already showed that $f_2(2,3,5) = (2\times 3)+(2\times 5)+(3\times 5)$, but it can also be written as $2\times (3+5)+(3\times 5)$. In order for us to not jump into wrong conclusions right ahead let's examine $f_2(2,3,5,7)$ as well.

$f_3(2,3,5,7) = (2\times 3\times 5) + (2\times 3\times 7) + (2\times 5\times 7)+ (3\times 5\times 7) = 2\times ((3\times 5)+(3\times 7)+(5\times 7)) + (3\times 5\times 7)$.

And for good measures let's try $f_3(2,3,5,7,11)$ as well

$f_3(2,3,5,7,11) = (2\times 3\times 5) + (2\times 3\times 7) + (2\times 3\times 11) + (2\times 5\times 7) + (2\times 5\times 11) + (2\times 7\times 11) + (3\times 5\times 7) + (3\times 5\times 11) + (3\times 7\times 11) + (5\times 7\times 11)$ $=2\times ((3\times 5)+(3\times 7)+(3\times 11)+(5\times 7)+(5\times 11)+(7\times 11))+(3\times 5\times 7) + (3\times 5\times 11) + (3\times 7\times 11) + (5\times 7\times 11)$

We can notice right away that when we try to factor our resulting equation by extracting $2$ from $f_3(2,3,5,7)$, we get $2\times f_2(3,5,7) +$ some remainder. also, when we try factor $f_2(2,3,5)$ we get $2\times f_1(3,5) +$ some remainder.

We can see that for any $S$, $f_n(S)$ where $n\neq 0,1,L$ will have the form of $S_1\times f_{n-1}(S-S_1)$+some remainder

where $S-S_1$ denotes the removal of the first item of $S$.

So all we left to do is to find what this "remainder" will be.

For $f_2(2,3,5)$ the reminder is $(3\times 5)$ $= f_2(3,5)$

For $f_3(2,3,5,7)$ the reminder is $(3\times 5\times 7)$ $= f_3(3,5,7)$

For $f_3(2,3,5,7,11)$ the reminder is $(3\times 5\times 11) + (3\times 7\times 11) + (5\times 7\times 11)$ $= f_3(3,5,7,11)$

So we can clearly see that the reminder takes the form of $f_{n}(S-S_1)$, where again $S-S_1$ denotes the removal of the first item of $S$.

As such our final equation is complete $\boxed{f_{n}(S)=S_1\times f_{n-1}(S-S_1) + f_{n}(S-S_1)}$

We finally covered all possible outcomes of $f_m(S)$

$\boxed{f_{0}(S)=1}$

$\boxed{f_{1}(S)=S_{1}+S_{2}+S_{3}+S_{4}...+S_{L}}$ where $L$ is the length of $S$.

$\boxed{f_{L}(S)=S_{1}\times S_{2}\times S_{3}\times S_{4}...\times S_{L}}$ where $L$ is the length of $S$.

$\boxed{f_{n}(S)=S_1\times f_{n-1}(S-S_1) + f_{n}(S-S_1)}$ where $n\neq 0,1,L$ and $S-S_1$ denotes the removal of the first item of $S$.

Actually we can see from our newest definition of $f_n(S)$ that we can deduce $f_1(S)$without having a specific equation for it.

$f_1(S) = S_1\times f_0(S-S_1) + S_2\times f_0(S-S_1-S_2) + S_3\times f_0(S-S_1-S_2-S_3)... +S_L\times f_0(0) = S_1+S_2+S_3...+S_L$

The equation for $f_1(S)$ is useful, but we really only need 3 equations

$\boxed{f_{0}(S)=1}$

$\boxed{f_{L}(S)=S_{1}\times S_{2}\times S_{3}\times S_{4}...\times S_{L}}$ where $L$ is the length of $S$.

$\boxed{f_{n}(S)=S_1\times f_{n-1}(S-S_1) + f_{n}(S-S_1)}$ where $n\neq 0,L$ and $S-S_1$ denotes the removal of the first item of $S$.

It seems like we are done, we would just have to run our program recursively over all $f_m(S)$ and calculate $f_{n-1}(S)-f_{n-2}(S)+f_{n-3}(S)-f_{n-4}(S)+f_{n-5}(S)...\pm f_{0}(S)$.

However running our program that way is too brute, there is a simpler more elegant way of doing it. since we can build up our equation from the bottom up we can visualize it in this way:

$S=2,3,5,7$

$\begin{array}{|c|c|c|c|c|} \hline 2&3&5&7\\ \hline f_{0}(2,3,5,7)&f_{0}(3,5,7)&f_{0}(5,7)&f_{0}(7)\\ \hline f_{1}(2,3,5,7)&f_{1}(3,5,7)&f_{1}(5,7)&f_{1}(7)\\ \hline f_{2}(2,3,5,7)&f_{2}(3,5,7)&f_{2}(5,7)&f_{2}(7)\\ \hline f_{3}(2,3,5,7)&f_{3}(3,5,7)&f_{3}(5,7)&f_{3}(7)\\ \hline \end{array}$

Bare with me for a second because I'm going to do things that seem counter intuitive but I would explain why they are that way in a bit.

I will use (X,Y) notation do denote a location in this table. both X and Y will start from 0 and would be colored green for sake of clarity. The value of X will denote distance from the top, and Y would denote distance from the left.

The corresponding values from $S$ would be displayed above each column in red color.

$\color{#D61F06}S_k$ would symbolize $S -S_1-S_2-S_3...-S_{k}$ where $S-S_n$ denotes the removal of the $n$th item of $S$.

So for example in $S=2,3,5,7$, $\color{#D61F06}S_2$ would give us

$S -S_1-S_2 = S -2-3 = 5,7$

it's Important to note that $\color{#D61F06}S_0 = S-0=S$

The table Final shape will be:

$\begin{array}{|c|c|c|c|c|} \hline &{\color{#D61F06}S_0} & {\color{#D61F06}S_1} & {\color{#D61F06}S_2} & {\color{#D61F06}S_3}\\ \hline &{\color{#20A900}0} & {\color{#20A900}1} & {\color{#20A900}2} & {\color{#20A900}3}\\ \hline {\color{#20A900}0}&(0,0) & (0,1) & (0,2) & (0,3)\\ \hline {\color{#20A900}1}&(1,0) & (1,1) & (1,2) & (1,3)\\ \hline {\color{#20A900}2}&(2,0) & (2,1) & (2,2) & (2,3)\\ \hline {\color{#20A900}3}&(3,0) & (3,1) & (3,2) & (3,3) \\ \hline \end{array}$

Now for the fun and (hopefully) easier part

Using our definition of $\color{#D61F06}S_n$ we will define:

(X,Y) = $f_{X}(\color{#D61F06}S_{Y})$

So for example (1,2) would represent $f_{1}(\color{#D61F06}S_{2}) = f_{1}(5,7) = 5+7$

We would insert simplest the values we know of first, that is

$\boxed{f_{0}(S)=1}$

$\boxed{f_{L}(S)=S_{1}\times S_{2}\times S_{3}\times S_{4}...\times S_{L}}$

$\begin{array}{|c|c|c|c|c|} \hline &{\color{#D61F06}{2,3,5,7}} & {\color{#D61F06}{3,5,7}} & {\color{#D61F06}{5,7}} & {\color{#D61F06}7}\\ \hline &{\color{#20A900}0} & {\color{#20A900}1} & {\color{#20A900}2} & {\color{#20A900}3}\\ \hline {\color{#20A900}0}&1 & 1&1 & 1\\ \hline {\color{#20A900}1}& & & & 7\\ \hline {\color{#20A900}2}& & & 5\times 7& \\ \hline {\color{#20A900}3}&& 3\times 5\times 7 & & \\ \hline \end{array}$

Now we insert

$\boxed{f_{n}(S)=S_1\times f_{n-1}(S-S{1}) + f_{n}(S-S{1})}$

$\begin{array}{|c|c|c|c|c|} \hline &{\color{#D61F06}{2,3,5,7}} & {\color{#D61F06}{3,5,7}} & {\color{#D61F06}{5,7}} & {\color{#D61F06}7}\\ \hline &{\color{#20A900}0} & {\color{#20A900}1} & {\color{#20A900}2} & {\color{#20A900}3}\\ \hline {\color{#20A900}0}&1 & 1&1 & 1\\ \hline {\color{#20A900}1}& 2\times (0,1) + (1,1)& 3\times (0,2) + (1,2) & 5\times (0,3) + (1,3) & 7\\ \hline {\color{#20A900}2}& 2\times (1,1) + (2,1) & 3\times (1,2) + (2,2) & 5\times 7& \\ \hline {\color{#20A900}3}&2\times (2,1) + (3,1)& 3\times 5\times 7 & & \\ \hline \end{array}$

Where the table is of the form:

$\begin{array}{|c|c|c|c|c|} \hline &{\color{#20A900}0} & {\color{#20A900}1} & {\color{#20A900}2} & {\color{#20A900}3}\\ \hline {\color{#20A900}0}&(0,0) & (0,1) & (0,2) & (0,3)\\ \hline {\color{#20A900}1}&(1,0) & (1,1) & (1,2) & (1,3)\\ \hline {\color{#20A900}2}&(2,0) & (2,1) & (2,2) & (2,3)\\ \hline {\color{#20A900}3}&(3,0) & (3,1) & (3,2) & (3,3) \\ \hline \end{array}$

We can see immediately that in order to calculate the value of a cell we only need to take the first value in $\color{#D61F06}S_Y$ that correspond to the cell column, multiply it by the value of the cell above it to the right, and add to it the value of the cell to the right.

So we keep only the first value in $\color{#D61F06}S_Y$ and discard the rest such that out final table shape would be

$\begin{array}{|c|c|c|c|c|} \hline &{\color{#D61F06}{2}} & {\color{#D61F06}{3}} & {\color{#D61F06}{5}} & {\color{#D61F06}7}\\ \hline &{\color{#20A900}0} & {\color{#20A900}1} & {\color{#20A900}2} & {\color{#20A900}3}\\ \hline {\color{#20A900}0}&1 & 1&1 & 1\\ \hline {\color{#20A900}1}& 2\times (0,1) + (1,1)& 3\times (0,2) + (1,2) & 5\times (0,3) + (1,3) & 7\\ \hline {\color{#20A900}2}& 2\times (1,1) + (2,1) & 3\times (1,2) + (2,2) & 5\times 7& \\ \hline {\color{#20A900}3}&2\times (2,1) + (3,1)& 3\times 5\times 7 & & \\ \hline \end{array}$

Now we can even do the calculation by hand! we only need to go from right to left and from up to down to get all the values we need!

$\begin{array}{|c|c|c|c|c|} \hline &{\color{#D61F06}{2}} & {\color{#D61F06}{3}} & {\color{#D61F06}{5}} & {\color{#D61F06}7}\\ \hline &{\color{#20A900}0} & {\color{#20A900}1} & {\color{#20A900}2} & {\color{#20A900}3}\\ \hline {\color{#20A900}0}&1 & 1&1 & 1\\ \hline {\color{#20A900}1}& 17& 15 &12 & 7\\ \hline {\color{#20A900}2}& 101 & 71 &35 \\ \hline {\color{#20A900}3}&247 & 105 & & \\ \hline \end{array}$

Now finally we get to calculate $f_{L-1}(S)-f_{L-2}(S)+f_{L-3}(S)-f_{L-4}(S)...\pm f_{0}(S)$

since (X,Y) = $f_{X}(\color{#D61F06}S_{Y})$

Then

$f_{L-1}(S)-f_{L-2}(S)+f_{L-3}(S)-f_{L-4}(S)...\pm f_{0}(S)$

Translates to

$(L-1,0)-(L-2,0)+(L-3,0)-(L-4,0)...\pm(0,0)$

In other words we only need to look at the first column!

For $S=2,3,5,7$

$(3,0)-(2,0)+(1,0)-(0,0) = 247-101+17-1 = 162$

So to calculate our final answer

$2\times 3\times 5\times 7 = 210$

$\frac{f_{L-1}(S)-f_{L-2}(S)+f_{L-3}(S)-f_{L-4}(S)}{p_1\times p_2...\times p_n} =$ $\frac{162}{210} = \frac{81}{105} = \frac{27}{35}$

Finally, since we only need to create a table of size $L^2$ where $L$ is the length of $S$ and go over it once to get to our answer, our computational efficiency is $O(n^2)$ instead of the original $O(n!)$