# Thread: counting multiples

1. ## 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

2. ## 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$

3. ## 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.

Testing

-Dan

5. ## 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

6. ## 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$