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

Thread: 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 $\displaystyle $n$$ prime numbers up to a number $\displaystyle $S$$.

    What i mean:

    For example we have three primes $\displaystyle $(2,3,5)$$. How many multiples (of these three numbers) are up to number $\displaystyle $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
    12,028
    Thanks
    848

    Re: counting multiples

    Hello, gdmath!

    Welcome back!


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

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

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

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


    The number of multiples of 2 or 3 is:

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

    . . . . . . . . . . $\displaystyle =\; 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):
    $\displaystyle m(a, b)=m(a) + m(b)-m(a \cdot b)$

    Where $\displaystyle m(x)$ is giving us the total multiples of $\displaystyle 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):
    $\displaystyle 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):
    $\displaystyle m(a, b, c, d)=m(a) + m(b) + m(c) + m(d)-$
    $\displaystyle m(a \cdot b)- m(a \cdot c)- m(a \cdot d)-$
    $\displaystyle m(b \cdot c)- m(b \cdot d)-$
    $\displaystyle m(c \cdot d)-$
    $\displaystyle m(a \cdot b \cdot c)$

    right?

    Thank you again.
    Last edited by gdmath; Jun 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
    11,152
    Thanks
    731
    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 $\displaystyle a,b,c ...$, up to a number $\displaystyle S$, we must:

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

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

    3.
    substruct the multiples of the numbers composed by these primes ($\displaystyle p_1, p_2, p_3, ...$): $\displaystyle -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
    3,387
    Thanks
    1345

    Re: counting multiples

    Use Inclusion/Exclusion:

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

    $\displaystyle \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:

    $\displaystyle \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 $\displaystyle p_1=2, p_2=3, p_3=5,\text{ and }S=30$, this is:

    $\displaystyle \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:

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

    $\displaystyle \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; Jun 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: Oct 30th 2009, 10:31 PM
  2. Multiples of 7 between 400&500
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Dec 4th 2008, 03:27 PM
  3. Multiples
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Feb 21st 2008, 04:13 PM
  4. sum of multiples from 3 to 99
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Feb 5th 2007, 03:43 PM
  5. Multiples of 2, 3, 5, but not 7
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Apr 11th 2005, 09:36 PM

Search Tags


/mathhelpforum @mathhelpforum