# Thread: Very prime like number

1. ## Very prime like number

positive integer is very prime-like if it is not divisible by any prime less than 15. How
many very prime-like positive integers are there less than 90000? Without giving an
exact answer, can you say approximately how many very prime-like positive integers
are less than 10^10? less than 10^100? Explain your reasoning as carefully as you can.

Sent from my LS-5009 using Tapatalk

2. ## Re: Very prime like number

Originally Posted by pankajprithyani
positive integer is very prime-like if it is not divisible by any prime less than 15. How
many very prime-like positive integers are there less than 90000? Without giving an
exact answer, can you say approximately how many very prime-like positive integers
are less than 10^10? less than 10^100? Explain your reasoning as carefully as you can.
Sent from my LS-5009 using Tapatalk
If you do not understand the inclusion/exclusion principle do not read this post. It will only confuse you.

There are six prime numbers less than fifteen: $2,3,5,7,11,13$
The number of multiples of two less than $\left\lfloor {\dfrac{9\cdot 10^4-1}{2}} \right\rfloor$ see here

The number of multiples of three & thirteen less than $\left\lfloor {\dfrac{9\cdot 10^4-1}{3\cdot 13}} \right\rfloor$ SEE HERE

The number of multiples of the primes here less than $\left\lfloor {\dfrac{9\cdot 10^4-1}{2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13}} \right\rfloor$ SEE HERE

Although the last answer is two, that is not an answer to this question. far from it.

We must find the total number that are divisible by at least one of these primes.
Now here is the problem: Some multiples of 2 are also multiples of 3 & 13, so we overcount.
So the inclusion/exclusion principle takes care that overcount.
We add all six taken one at a time
substract 15 taken two at a time.
add back 20 taken three at at a time
subtract 15 taken four at a time
add back six taken five at a time
substract 1 taken six at a time.
That is sixty-three operations, and we are still not done.

To finish we need to subtract that grand total from $9\cdot 10^4-1$.

3. ## Re: Very prime like number

I would approach this in a simpler-to-understand way:

The product of 2x3x5x7x11x13 is 30030. Which means if we can determine how many very prime-like numbers exist in the range 1-30,030 the same number of very prime-like numbers will appear in the range 30,031 - 60,060, and in the range 60,061 - 90,090, etc.

Among the first 30,030 numbers half are multiples of 2, or 15,015. Subtract 15,015 from 30,030, leaving 15,015. This is the quantity of numbers in the range 1- 30,030 that are not a multiple of 2. One third of these remaining numbers are multiples of 3, which is 5005, and because we've already subtracted out all the numbers that are multiples of 2 we aren't double counting multiples of 6. So we subtract 5,005 from 15,015 to get 10,010 - this is the quantity of numbers in the range 1-30,300 that are not multiples of either 2 or 3.

Continuing on:

10010/5 = 2002, 10,010-2002 = 8,008 numbers that are not multiples of 2, 3, or 5
8008/7 = 1144, 8008-1144 = 6864 numbers that are not multiples of 2, 3, 5, or 7
6864/11 = 624, 6864-624 = 6240 numbers that are not multiples of 2, 3, 5, 7 or 11
6240/13 = 480, 6240-480 = 5760 numbers that are not multiples of 2, 3, 5, 7, 11 or 13

Hence there are 5760 very prime-like numbers in the range 1 - 30,030.

We can estimate the number of very prime-like numbers in the range 1-90000 as approximately (90000/30,030) x 5760 = 17265 (plus or minus). This may not be exact, because 90,000 is not a multiple of 30,030. With a little extra work we could determine how many very prime-like numbers exist in the range 90,001 - 90,090; let's call that number P. Then the exact number of very prime-like numbers would be 90090/30030 x 5760 - P = 17280-P.

For the other larger ranges you can get an estimate by multiplying the number by 5760/30030.

**EDIT - However, the number 1 is included in these calculations as being "very prime-like." Normally 1 is not considered to be prime, but is it very prime-like? Per the definition given for very prime-like, "a positive integer is very prime-like if it is not divisible by any prime less than 15," the number 1 would seem to fit the definition. In any event you need to decide whether 1 belongs or not - if not, subtract 1 from the final results.

4. ## Re: Very prime like number

Thanks

Sent from my LS-5009 using Tapatalk

5. ## Re: Very prime like number

You're welcome. Please note that I added a postscript regarding how to treat the number 1 in these calculations.