Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Divisibility homework help

  1. Aug 13, 2010 #1
    In a set of integers from 250 to 380, inclusive, how many are multiples of both 2 and 7?

    Please tell me if I'm correct:

    floor((380-250+1)/(7*2)) = 9

    And in general is it always the floor of [cardinality]/[LCM]?
     
  2. jcsd
  3. Aug 13, 2010 #2

    Mark44

    Staff: Mentor

    Re: Divisibility

    I get 10.
    On problems of this nature, the best course is to do a sanity check on your formula to see if it gives the right results.
     
  4. Aug 13, 2010 #3
    Re: Divisibility

    What formula do you use to get 10?
     
  5. Aug 13, 2010 #4

    Mark44

    Staff: Mentor

    Re: Divisibility

    I didn't use a formula. The numbers in this set have to be multiples of 14, so I listed all multiples of 14 between 250 and 380.
     
  6. Aug 13, 2010 #5
    Re: Divisibility

    Is there a more efficient way than brute force?

    Also, what would you do if one of the numbers wasn't prime; search for multiples of the LCM in a given set?
     
  7. Aug 13, 2010 #6

    Mark44

    Staff: Mentor

    Re: Divisibility

    Here's a formula that gives the correct result:
    [tex]\frac{378 - 252}{14} + 1[/tex]

    252 is the smallest multiple of 14 that is greater than 250. 378 is the largest multiple of 14 that is less than 280.

    This would also work:
    [tex]floor(\frac{380 - 250}{14}) + 1[/tex]
     
  8. Aug 13, 2010 #7
    Re: Divisibility

    Thanks

    Can you tell me whether your formulas are generalizable and whether the divisor is always the LCM of the two given numbers?
     
  9. Aug 13, 2010 #8

    Mark44

    Staff: Mentor

    Re: Divisibility

    Probably. But brute force is superior to using a poorly-understood or incorrect formula that gives incorrect results.

    This was a simple problem that took me all of a minute or two to list the numbers in the set, and count them. After I knew how many numbers there were I was able to come up with a formula that gave the same result.
    That seems reasonable.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook