We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive pseudonymised information about your use of our website.
Please click on "Accept cookies" if you agree to the setting of cookies. Cookies that do not require consent remain unaffected by this, see
cookie policy and privacy policy.
DECLINE COOKIES

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!

Guest Feb 21, 2019

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

Rom Feb 21, 2019