Results 1 to 6 of 6
Like Tree1Thanks
  • 1 Post By SlipEternal

Math Help - counting multiples

  1. #1
    Member
    Joined
    May 2009
    Posts
    77

    counting multiples

    Hello everybody (Long time no see),

    is there a formula that allows us to count the multiples of $n$ prime numbers up to a number $S$.

    What i mean:

    For example we have three primes $(2,3,5)$. How many multiples (of these three numbers) are up to number $30$

    By sequentian steps we have that:

    ->There are 15 multiples of 2
    ->There are 10 multiples of 3. However numbers $6, 12, 18, 24, 30$ have been already counted as multiples of 2. So eventually there are 5 multipes of 3, that are not already counted.
    ->There are only 2 (new) multiples of 5 (5, 25)

    So total we have 15 (multiples of 2) + 5 (new multiples of 3) + 2 (new multiples of 5) = 22

    So, is there a quick formula for counting the multiples (once)?

    Thanks all for your time and you response
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,683
    Thanks
    615

    Re: counting multiples

    Hello, gdmath!

    Welcome back!


    For example, we have three primes $(2,3,5)$.
    How many multiples (of these three numbers) are up to number $30$

    Let's start with two numbers, say 2 and 3. .(These need not be primes.)
    Let S = 37.

    Let \left[\frac{S}{p}\right] be the "greatest integer" function.
    Defined simply, "divide and round down".

    We have: . \left[\frac{37}{2}\right] = 18 multiples of 2: m(2)
    . . . . . . . . \left[\frac{37}{3}\right] = 12 multipes of 3: m(3)
    . . . . . . . . \left[\frac{37}{2\!\cdot\!3}\right] = 6 multiple of 6: m(2\!\cdot\!3)


    The number of multiples of 2 or 3 is:

    . . m(2\text{ or }3) \;=\;mn(2) + m(3) - m(2\text{ and} 3)

    . . . . . . . . . . =\; 18 + 12 - 6 \;=\;24

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2009
    Posts
    77

    Re: counting multiples

    Hello Soroban,

    Thanks for your post and for your time (and ...time is valuable at Mundial period! ).

    Indeed, when we have two numbers $(a,b)$ and we want to find their multiples up to a number $S$, the formula is:

    (1):
    m(a, b)=m(a) + m(b)-m(a \cdot b)

    Where m(x) is giving us the total multiples of x up to number [/TEX]S[/TEX].
    Comma (,) means "or".

    This is a simple approach indeed.
    So when we have three numbers the formula (1) is becoming:

    (2):
    m(a, b, c)=m(a) + m(b) + m(c) - m(a\cdot b)- m(a \cdot c)

    right?

    For four numbers $a,b,c,d$ , the formula (1) is becoming:

    (3):
    m(a, b, c, d)=m(a) + m(b) + m(c) + m(d)-
      m(a \cdot b)- m(a \cdot c)- m(a \cdot d)-
      m(b \cdot c)- m(b \cdot d)-
      m(c \cdot d)-
      m(a \cdot b \cdot c)

    right?

    Thank you again.
    Last edited by gdmath; June 21st 2014 at 01:54 AM. Reason: LaTex Corrections
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,845
    Thanks
    320
    Awards
    1

    Re: counting multiples

    Testing

    -Dan
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    May 2009
    Posts
    77

    Re: counting multiples

    In Conlusion:

    If we want to count the multiples of given numbers a,b,c ..., up to a number S, we must:

    1. (optional)
    first factorize a,b,c ... at prime numbers p_1, p_2, p_3, ...,

    2.
    count the multiples of these primes (up to S), m(p_1)+m(p_2)+....

    3.
    substruct the multiples of the numbers composed by these primes ( p_1, p_2, p_3, ...): -m(p_1 \cdot p_2)-m(p_1 \cdot p_3)-....





    Thank you all for your time
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,795
    Thanks
    694

    Re: counting multiples

    Use Inclusion/Exclusion:

    The number of distinct multiples of p_1,p_2,\ldots, p_n no larger than S is

    \sum_{i=1}^n (-1)^{i+1}\left(\sum_{1\le a_1 < \cdots < a_i \le n}\left\lfloor \dfrac{S}{\displaystyle \prod_{k=1}^i p_{a_k}} \right\rfloor \right)

    So, with three primes, it would be:

    \begin{align*}& \left(\left\lfloor \dfrac{S}{p_1}\right\rfloor+\left\lfloor \dfrac{S}{p_2}\right\rfloor + \left\lfloor \dfrac{S}{p_3}\right\rfloor\right) \\ - & \left( \left\lfloor \dfrac{S}{p_1p_2}\right\rfloor + \left\lfloor \dfrac{S}{p_1p_3}\right\rfloor + \left\lfloor \dfrac{S}{p_2p_3}\right\rfloor\right) \\ + & \left( \left\lfloor \dfrac{S}{p_1p_2p_3}\right\rfloor \right)\end{align*}

    For your example with p_1=2, p_2=3, p_3=5,\text{ and }S=30, this is:

    \begin{align*} & \left(\left\lfloor \dfrac{30}{2}\right\rfloor+\left\lfloor \dfrac{30}{3}\right\rfloor+\left\lfloor \dfrac{30}{5}\right\rfloor\right) \\ - &  \left( \left\lfloor \dfrac{30}{6}\right\rfloor + \left\lfloor \dfrac{30}{10}\right\rfloor + \left\lfloor \dfrac{30}{15}\right\rfloor\right) \\ + & \left( \left\lfloor \dfrac{30}{30}\right\rfloor \right) \\ = & (15+10+6)-(5+3+2)+(1) = 22\end{align*}

    This gives the same answer as what you found.

    If there were four primes, it would be:

    \begin{align*} & \left(\left\lfloor \dfrac{S}{p_1}\right\rfloor+\left\lfloor \dfrac{S}{p_2}\right\rfloor+\left\lfloor \dfrac{S}{p_3}\right\rfloor + \left\lfloor \dfrac{S}{p_4}\right\rfloor\right) \\ - & \left( \left\lfloor \dfrac{S}{p_1p_2}\right\rfloor + \left\lfloor \dfrac{S}{p_1p_3}\right\rfloor + \left\lfloor \dfrac{S}{p_1p_4}\right\rfloor + \left\lfloor \dfrac{S}{p_2p_3}\right\rfloor + \left\lfloor \dfrac{S}{p_2p_4}\right\rfloor + \left\lfloor \dfrac{S}{p_3p_4}\right\rfloor\right) \\ + & \left( \left\lfloor \dfrac{S}{p_1p_2p_3}\right\rfloor + \left\lfloor \dfrac{S}{p_1p_2p_4}\right\rfloor + \left\lfloor \dfrac{S}{p_1p_3p_4}\right\rfloor + \left\lfloor \dfrac{S}{p_2p_3p_4}\right\rfloor \right) \\ - & \left( \left\lfloor \dfrac{S}{p_1p_2p_3p_4}\right\rfloor \right)\end{align*}

    Do you see the pattern?

    Another way to write the general form:

    The notation [n] is common in combinatorics. It means [n] = \{k \in \Bbb{Z} \mid 1 \le k \le n\} (it is the set of all positive integers up to n). The notation 2^{[n]} is the power set of that set (it is the set of all possible subsets of [n]. Then, you can write the formula for the inclusion/exclusion like this:

    \sum_{A \in (2^{[n]}-\{\emptyset\})}(-1)^{|A|+1}\left\lfloor \dfrac{S}{\displaystyle \prod_{a\in A} p_a}\right\rfloor
    Last edited by SlipEternal; June 23rd 2014 at 12:37 AM.
    Thanks from gdmath
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Multiples
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 30th 2009, 10:31 PM
  2. Multiples of 7 between 400&500
    Posted in the Algebra Forum
    Replies: 1
    Last Post: December 4th 2008, 03:27 PM
  3. Multiples
    Posted in the Algebra Forum
    Replies: 3
    Last Post: February 21st 2008, 04:13 PM
  4. sum of multiples from 3 to 99
    Posted in the Algebra Forum
    Replies: 1
    Last Post: February 5th 2007, 03:43 PM
  5. Multiples of 2, 3, 5, but not 7
    Posted in the Algebra Forum
    Replies: 2
    Last Post: April 11th 2005, 09:36 PM

Search Tags


/mathhelpforum @mathhelpforum