+0

+1
45
1

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!

Feb 21, 2019

#1
+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