We say that a positive integer is quiteprime if it is not divisible by 2, 3, or 5. How many quiteprime positive integers are there less than 100? Less than 1000? 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? Without giving an exact answer, can you say approximately how many very quiteprime positive integers are less than 10^10? Less than 10^100? Explain your reasoning as carefully as you can.
Answers
Answer:
A number isn't divisible by any of the "small primes" {2,3,5,7,11,13}{2,3,5,7,11,13} if it is coprime to the product 2∗3∗5∗7∗11∗13=300302∗3∗5∗7∗11∗13=30030. The Euler's totient function counts these, so the amount of very quite prime numbers less than 3003030030 is
ϕ(30030)=(2−1)(3−1)(5−1)(7−1)(11−1)(13−1)=5760
ϕ(30030)=(2−1)(3−1)(5−1)(7−1)(11−1)(13−1)=5760
Now we want to count upto 9000090000. If we count upto 90090=3∗3003090090=3∗30030 we get three times the same numbers mod30030mod30030, and coprimeness to 3003030030 depends on a number only mod30030mod30030. Hence we get 3∗5760=172803∗5760=17280 very quite prime numbers less than 9009090090. But we have overcounted the very quite prime numbers in the range 90000,90001,…,9009090000,90001,…,90090. Make a Erasthothenian sieve to find how many there are. You can leave even numbers out to begin with (leave numbers ending in 55 to help the "stepping process"). That is, make nine columns with the ending digits (I put these so that you read column-wise):
010305070911131517192123252729313335373941434547495153555759616365676971737577798183858789
011121314151617181031323334353637383051525354555657585071727374757677787091929394959697989
Remember, these nubers represents 900..900.. with the corresponding ending digits, but I left the 900..900.. part out for notation.
Now start striking out the multiples of 33. Find the first one (it is 0303) and then strike out every third one (notice the even ones are taken out evenly, so this works). Then do the same for all other small primes and see how many are left. This is the number you have over counted and must subtract from 3∗57603∗5760 to get the answer. It turns out to be 1919, so the answer is
3∗5760−19=17261
3∗5760−19=17261
Answer:
Here is your answer ll
Hope it helps you
