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!)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

fm(S)=f_m(S) = the sum of all products of all permutations of size mm of S

fn1(S)fn2(S)+fn3(S)fn4(S)+fn5(S)...±1p1×p2...×pn\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 p1×p2×p3...×pnp_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 fn1(S)fn2(S)+fn3(S)fn4(S)+fn5(S)...±1f_{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 fm(S)f_m(S). For you convenience here are a few examples for it:

f2(2,3,5)=(2×3)+(2×5)+(3×5)f_2(2,3,5) = (2\times 3)+(2\times 5)+(3\times 5)

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

f3(2,3,5,7)=(2×3×5)+(2×3×7)+(2×5×7)+(3×5×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)

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

f5(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 fm(S)f_m(S) depends deeply upon the result of all fn(S)f_n(S) where m>nm>n.

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

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

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

Another simple observation is that if we are given fL(S)f_L(S) where LL is simply the length of SS there is only 11 permutation which fits. As such fL(S)=S1×S2×S3×S4...×SL\boxed{f_{L}(S)=S_{1}\times S_{2}\times S_{3}\times S_{4}...\times S_{L}} where LL is the length of SS.

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

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

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

f3(2,3,5,7)=(2×3×5)+(2×3×7)+(2×5×7)+(3×5×7)=2×((3×5)+(3×7)+(5×7))+(3×5×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) = 2\times ((3\times 5)+(3\times 7)+(5\times 7)) + (3\times 5\times 7).

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

f3(2,3,5,7,11)=(2×3×5)+(2×3×7)+(2×3×11)+(2×5×7)+(2×5×11)+(2×7×11)+(3×5×7)+(3×5×11)+(3×7×11)+(5×7×11)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×((3×5)+(3×7)+(3×11)+(5×7)+(5×11)+(7×11))+(3×5×7)+(3×5×11)+(3×7×11)+(5×7×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 22 from f3(2,3,5,7)f_3(2,3,5,7), we get 2×f2(3,5,7)+2\times f_2(3,5,7) + some remainder. also, when we try factor f2(2,3,5)f_2(2,3,5) we get 2×f1(3,5)+2\times f_1(3,5) + some remainder.

We can see that for any SS, fn(S)f_n(S) where n0,1,Ln\neq 0,1,L will have the form of S1×fn1(SS1)S_1\times f_{n-1}(S-S_1)+some remainder

where SS1S-S_1 denotes the removal of the first item of SS.

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

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

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

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

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

As such our final equation is complete fn(S)=S1×fn1(SS1)+fn(SS1)\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 fm(S)f_m(S)

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

f1(S)=S1+S2+S3+S4...+SL\boxed{f_{1}(S)=S_{1}+S_{2}+S_{3}+S_{4}...+S_{L}} where LL is the length of SS.

fL(S)=S1×S2×S3×S4...×SL\boxed{f_{L}(S)=S_{1}\times S_{2}\times S_{3}\times S_{4}...\times S_{L}} where LL is the length of SS.

fn(S)=S1×fn1(SS1)+fn(SS1)\boxed{f_{n}(S)=S_1\times f_{n-1}(S-S_1) + f_{n}(S-S_1)} where n0,1,Ln\neq 0,1,L and SS1S-S_1 denotes the removal of the first item of SS.

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

f1(S)=S1×f0(SS1)+S2×f0(SS1S2)+S3×f0(SS1S2S3)...+SL×f0(0)=S1+S2+S3...+SLf_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 f1(S)f_1(S) is useful, but we really only need 3 equations

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

fL(S)=S1×S2×S3×S4...×SL\boxed{f_{L}(S)=S_{1}\times S_{2}\times S_{3}\times S_{4}...\times S_{L}} where LL is the length of SS.

fn(S)=S1×fn1(SS1)+fn(SS1)\boxed{f_{n}(S)=S_1\times f_{n-1}(S-S_1) + f_{n}(S-S_1)} where n0,Ln\neq 0,L and SS1S-S_1 denotes the removal of the first item of SS.

It seems like we are done, we would just have to run our program recursively over all fm(S)f_m(S) and calculate fn1(S)fn2(S)+fn3(S)fn4(S)+fn5(S)...±f0(S)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,7S=2,3,5,7

2357f0(2,3,5,7)f0(3,5,7)f0(5,7)f0(7)f1(2,3,5,7)f1(3,5,7)f1(5,7)f1(7)f2(2,3,5,7)f2(3,5,7)f2(5,7)f2(7)f3(2,3,5,7)f3(3,5,7)f3(5,7)f3(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 SS would be displayed above each column in red color.

Sk\color{#D61F06}S_k would symbolize SS1S2S3...SkS -S_1-S_2-S_3...-S_{k} where SSnS-S_n denotes the removal of the nnth item of SS.

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

SS1S2=S23=5,7S -S_1-S_2 = S -2-3 = 5,7

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

The table Final shape will be:

S0S1S2S301230(0,0)(0,1)(0,2)(0,3)1(1,0)(1,1)(1,2)(1,3)2(2,0)(2,1)(2,2)(2,3)3(3,0)(3,1)(3,2)(3,3)\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 Sn\color{#D61F06}S_n we will define:

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

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

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

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

fL(S)=S1×S2×S3×S4...×SL\boxed{f_{L}(S)=S_{1}\times S_{2}\times S_{3}\times S_{4}...\times S_{L}}

2,3,5,73,5,75,770123011111725×733×5×7\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

fn(S)=S1×fn1(SS1)+fn(SS1)\boxed{f_{n}(S)=S_1\times f_{n-1}(S-S{1}) + f_{n}(S-S{1})}

2,3,5,73,5,75,7701230111112×(0,1)+(1,1)3×(0,2)+(1,2)5×(0,3)+(1,3)722×(1,1)+(2,1)3×(1,2)+(2,2)5×732×(2,1)+(3,1)3×5×7\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:

01230(0,0)(0,1)(0,2)(0,3)1(1,0)(1,1)(1,2)(1,3)2(2,0)(2,1)(2,2)(2,3)3(3,0)(3,1)(3,2)(3,3)\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 SY\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 SY\color{#D61F06}S_Y and discard the rest such that out final table shape would be

235701230111112×(0,1)+(1,1)3×(0,2)+(1,2)5×(0,3)+(1,3)722×(1,1)+(2,1)3×(1,2)+(2,2)5×732×(2,1)+(3,1)3×5×7\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!

235701230111111715127210171353247105\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 fL1(S)fL2(S)+fL3(S)fL4(S)...±f0(S)f_{L-1}(S)-f_{L-2}(S)+f_{L-3}(S)-f_{L-4}(S)...\pm f_{0}(S)

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

Then

fL1(S)fL2(S)+fL3(S)fL4(S)...±f0(S)f_{L-1}(S)-f_{L-2}(S)+f_{L-3}(S)-f_{L-4}(S)...\pm f_{0}(S)

Translates to

(L1,0)(L2,0)+(L3,0)(L4,0)...±(0,0)(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,7S=2,3,5,7

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

So to calculate our final answer

2×3×5×7=2102\times 3\times 5\times 7 = 210

fL1(S)fL2(S)+fL3(S)fL4(S)p1×p2...×pn=\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} = 162210=81105=2735\frac{162}{210} = \frac{81}{105} = \frac{27}{35}

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

Note by Daniel Magen
3 years, 3 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

There are no comments in this discussion.

×

Problem Loading...

Note Loading...

Set Loading...