Results 1 to 5 of 5
Like Tree2Thanks
  • 1 Post By Plato
  • 1 Post By ChipB

Thread: Very prime like number

  1. #1
    Newbie
    Joined
    Mar 2017
    From
    INDIA
    Posts
    5

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,492
    Thanks
    2730
    Awards
    1

    Re: Very prime like number

    Quote Originally Posted by pankajprithyani View Post
    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$.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jun 2014
    From
    NJ
    Posts
    264
    Thanks
    91

    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.
    Last edited by ChipB; Mar 31st 2017 at 06:51 AM.
    Thanks from pankajprithyani
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Mar 2017
    From
    INDIA
    Posts
    5

    Re: Very prime like number

    Thanks

    Sent from my LS-5009 using Tapatalk
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Jun 2014
    From
    NJ
    Posts
    264
    Thanks
    91

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: Nov 16th 2016, 05:29 PM
  2. Replies: 0
    Last Post: Sep 24th 2011, 12:23 PM
  3. Replies: 1
    Last Post: Sep 2nd 2009, 09:31 AM
  4. prime number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Sep 23rd 2008, 06:02 PM
  5. Number theory, prime number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Sep 17th 2006, 09:11 PM

Search tags for this page

Click on a term to search for related topics.

/mathhelpforum @mathhelpforum