+0  
 
+1
45
1
avatar

A positive integer is very quiteprime if it is not divisible by any prime less than 15. How many very quiteprime positive integers are there less than 90000?

 

I tried to start doing this out by finding the numbers that are divisible by primes less than 15, but it seems to be taking a long time. It would be very helpful if anyone has a quick solution for this?

 

Thanks for the help in advance!smiley

 Feb 21, 2019
 #1
avatar+4455 
+1

I suppose you could use the inclusion-exclusion principle.

 

\(\text{The primes less than 15 are 2, 3, 5, 7, 11, 13}\\ \text{Let }A_2=\{n:2 | n\},~A_3=\{n:3 | n\},\dots A_{13}=\{n:13|n\}\)

 

\(|A_2 \cup A_3 \cup \dots A_{13}| = \\ \phantom{+} \left(|A_2|+|A_3| + \dots + |A_{13}|\right)\\ -\left(|A_2 \cap A_3| + |A_3 \cap A_5| + \dots |A_{11}\cap A_{13}|\right)\\ +\left(|A_2 \cap A_3 \cap A_5| + \dots |A_7\cap A_{11} \cap A_{13}|\right)\\ -\left(|A_2\cap A_3 \cap A_5 \cap A_7| + \dots + |A_5\cap A_7 \cap A_{11} \cap A_{13}|\right)\\ + \dots \\ -|A_2 \cap A_3 \cap A_5 \cap A_7 \cap A_{11} \cap A_{13}|\)

 

\(\text{You can calculate the size of all these individual terms as for example}\\ |A_2| = \left \lfloor \dfrac{90000}{2}\right \rfloor\\ |A_3 \cap A_5 \cap A_7| = \left \lfloor \dfrac{90000}{3 \cdot 5 \cdot 7} \right \rfloor\\ |A_3 \cap A_5 \cap A_7 \cap A_{11} \cap A_{13} |= \left \lfloor \dfrac{90000}{3 \cdot 5 \cdot 7\cdot 11 \cdot 13} \right \rfloor\)

 

I'm going to leave all the grunt work to you.  You should get an answer of 17261.

 Feb 21, 2019
edited by Rom  Feb 21, 2019

18 Online Users

avatar
avatar
avatar