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 22 as a fraction of all natural numbers. You simply observe that the multiples of the number 22 "cover" only half of all natural numbers, and conclude that this number is simply 12\frac{1}{2}.

You wonder if instead of being given only the number 22, you would have been given the numbers 2,32,3 and were asked the same question what would the answer be? you try the same approach as before, all the multiples of 22 cover 12\frac{1}{2} of all numbers, and all the multiples of 33 cover 13\frac{1}{3} of all numbers. so is the answers simply 12+13=56\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×32\times3 because the multiples of 22 and 33 create a unique pattern of size 2×32\times3 that constantly repeats itself. Another way to look at it is to see that after 2×32\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×3=62\times3=6 to test your hypothesis and check if this is indeed the answer.

numbers123456
multiples of 2246
multiples of 336
multiples of both2346

and you notice that contradictory to what you expected, only 46\frac{4}{6} of the numbers ended up covered, and you can already see where you made the mistake, you marked 66 twice. so you update your answer to be 12+1312×3=46=23\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,52,3,5? learning from past experience you confidently say that the answer must be 12+13+1512×312×513×5=2130\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×3×5=302\times3\times5=30

numbers123456789101112131415161718192021222324252627282930
multiples of 224681012141618202224262830
multiples of 336912151821242730
multiples of 551015202530
multiples of all2345689101214151618202122242526272830

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 3030 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 12×312×513×5-\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 12+13+1512×312×513×5+12×3×5=2230=1115\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 22 you have 12\frac{1}{2}

For 2,32,3 you have 12+1312×3\frac{1}{2}+\frac{1}{3}-\frac{1}{2\times3}

And for 2,3,52,3,5 you have 12+13+1512×312×513×5+12×3×5\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=p1,p2,p3,p4,p5...pnS=p_1,p_2,p_3,p_4,p_5...p_n, you simply add all number which has 11 as their numerator and pxp_x as their denominator.

Then you subtract from the resulting sum by the sum of all the numbers which has 11 as their numerator and a permutation of size 22 of the set SS as their denominator.

Then you add to the resulting sum the sum of all the numbers which has 11 as their numerator and a permutation of size 33 of the set SS as their denominator.

And so on until you reach a permutation of size nn, at which point if nn is even you subtract 1p1×p2...×pn\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=p1,p2,p3,p4,p5...pnS=p_1,p_2,p_3,p_4,p_5...p_n, the corresponding equation would be

(1p1+1p2+1p3...+1pn)(1p1×p2+1p1×p3...+1p1×pn+1p2×p3+1p2×p4...+1p2×pn...+1pn1×pn)+(1p1×p2×p3+1p1×p2×p4...+1p1×pn1×pn+...+1pn2×pn1×pn)...±1p1×p2...×pn(\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

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}

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 n!(nk)!\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(n2)O(n^2) instead of O(n!)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

Note by Daniel Magen
3 years, 4 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...