[Math] Finding the amount of numbers less than another number which are multiples of a set

arithmeticcombinatorics

An Example To Illustrate

  • Find the amount of numbers less than 30 that are multiples of the set of numbers [2,3,5]

  • Clearly we can find the number of multiples of a number less than another number through this equation:
    $$ numberOfMultiplesLessThan =\Big\lceil\frac {numberToFindMultiplessLessThan}{numberToFindMultiplesOf}\Big\rceil – 1 $$
    So in this case we have:

    1. Number of Multiples of 2: $\frac {30} 2 – 1 = 15 -1 = 14$
    2. Number of Multiples of 3: $\frac {30} 3 – 1 = 10 -1 = 9$
    3. Number of Multiples of 5: $\frac {30} 5 – 1 = 6 – 1 = 5$

  • But now we have to check for cases in which a number is a multiple of more than one of these numbers:

    1. Number of Multiples of 2 & 3: $\frac {30} {2*3} – 1 = 30/6 – 1 = 5 – 1 = 4$
    2. Number of Multiples of 2 & 5: $\frac {30} {2*5} – 1 = 30/10 – 1 = 3 – 1 = 2 $
    3. Number of Multiples of 3 & 5: $\frac {30} {3*5} – 1 = 30/15 – 1 = 2 – 1 = 2 $

Luckily,since $2*3*5 = 30$ there is no number less than thirty that is a multiple of all three, so we don't have to check that set. Unfortunately, for larger sets (and depending on the number that is chosen to be less than) there may be many set intersections to check for.

Anyway, we can now find the amount of numbers that are less than 30 and are multiples of either 2, 3, or 5:

  1. $\text{Multiples Less than 30} = \text{Number of Multiples of 2} + \text{Number of Multiples of 3} + \text{Number of Multiples of 5} – \text{Number of Multiples of 2 & 3} – \text{Number of Multiples of 2 & 5} – \text{Number of Multiples of 3 & 5}$
  2. $\text{Multiples Less than 30} = 14 + 9 + 5 – 4 – 2 – 2 = 21$

Notes about the Problem

  1. Though in this case I choose a number (30) which made the results for the multiple equation turn out nicely, in truth the actual chosen number won't be so nice. So, in those cases the ceiling function must be invoked.
  2. It is not a coincidence that the numbers in the set are all prime. My specific application is a bit odd in that it will only select prime numbers and that too, by choosing a prime number it must include all the prime numbers below it (ex: [11,7,5,3,2] is a valid set but [11,5,3,2] is not). I'm not sure how this note will affect the answer, but I thought I'd include it.

My Problem

This algorithm, while relatively simple, becomes a bit tedious with extremely large numbers and extremely large sets. Examining the problem again, I found that there is a huge amount of simplification that can be made with the overall equation. For example:

Consider (again) the case of finding the amount of numbers less than 30 that are Multiples of 2, 3, or 5. The overall equation is this:

  1. $ \text{Multiples Less than 30} = \text{Number of Multiples of 2} + \text{Number of Multiples of 3} + \text{Number of Multiples of 5} – \text{Number of Multiples of 2 & 3} – \text{Number of Multiples of 2 & 5} – \text{Number of Multiples of 3 & 5} $

  2. $\text{Multiples Less Than 30} = 29 – (\frac {30} 2 -1) – (\frac {30} 3 – 1) – (\frac {30} 5 – 1) + (\frac {30}{2*3} – 1) + (\frac{30} {2*5} -1) + (\frac{30} {3*5} – 1) $

  3. $$Multiples Less Than 30 = 29 – (\frac {30} 2) – (3\frac {30} 3) – (\frac {30} 5) + (\frac {30}{2*3}) + (\frac{30} {2*5}) + (\frac{30} {3*5}) + 3 – 3 $$

[Note: It is common but not required that the -1's cancel out]

  1. $$Multiples Less Than 30 = 29 – (\frac {30} 2) – (\frac {30} 3) – (\frac {30} 5) + (\frac {30}{2*3}) + (\frac{30} {2*5}) + (\frac{30} {3*5}) $$

  2. $$Multiples Less Than 30 = 29 – 30*(\frac12 + \frac 13 + \frac 15 – \frac 1 {2*3} – \frac 1 {2*5} – \frac 1 {(3*5)} )$$

  3. $$Multiples Less Than 30 = 29 – 2*3*5*(\frac12 + \frac 13 + \frac 15 – \frac 1 {2*3} – \frac 1 {2*5} – \frac 1 {(3*5)} )$$

  4. $$Multiples Less Than 30 = 29 – (3*5 + 2*5 + 2*3 – 5 – 3 – 2 )$$

[Note: In cases that don't involve the primorial ( 3*2 or 5*3*2 or 7*5*3*2 or 11*7*5*3*2), you'd have to multiple both sides by the primorial to be able to clear those fractions]

  1. $$Multiples Less Than 30 = 29 – (3*5 + 2*5 + 2*3 – 5 – 3 – 2 )$$
  2. $$Multiples Less Than 30 = 29 – (3*4 + 5 + 2*2) $$

[Note: As you can see (Step 9) the relatively long equation turned into something simple. I've done this with a few numbers, and without doing any calculations — other than factoring and combining like terms — it always comes down to something relatively simple.]

The Actual Question!

So, my question is: Using the type of simplification shown above (or any other system for that matter), is there any generalized way to find how many multiples of a prime set as discussed above are below a number that is simpler or faster than the algorithm I described?

P.S.
I'm apologize in advance for the formatting and visual look of the question. I've tried to make it as readable as possible, but I still feel that it is both bulky and a bit unorganized. In addition, I couldn't quite figure out how to make the math look nice (like 3*5)

Best Answer

You can write what you're after as

$$\lfloor{29\over2} \rfloor+\lfloor{29\over3} \rfloor+\lfloor{29\over5} \rfloor-\lfloor{29\over6} \rfloor-\lfloor{29\over10} \rfloor-\lfloor{29\over15} \rfloor+\lfloor{29\over30} \rfloor=14+9+5-4-2-1+0=21$$

In general, if you have a set of pairwise relatively prime (positive) integers $a_1,a_2,\ldots,a_n$ and want to know how many multiples of one of these there are less than some number $N$, the answer is

$$\lfloor{N-1\over a_1} \rfloor+\cdots+\lfloor{N-1\over a_n} \rfloor-\lfloor{N-1\over a_1a_2} \rfloor-\cdots-\lfloor{N-1\over a_{n-1}a_n} \rfloor+\cdots+(-1)^{n+1}\lfloor{N-1\over a_1\cdots a_n} \rfloor$$

by inclusion-exclusion, as JMac31 mentioned in comments. In general this gives you $2^n-1$ numbers to compute. I don't think you can do any better than that if you want to get the exact number.

On the other hand, if (as is the case in the OP's example), the $a_i$'s are distinct primes and $N$ is their product, then the answer is

$$N-1-(a_1-1)(a_2-1)\cdots(a_n-1)$$

This is mainly the multiplicative property of the Euler phi function.

Related Question