0
$\begingroup$

so I have an assignment to write a program that calculates multiples using inclusion exclusion however I am having a little trouble understanding the math.

The program is that given two integers a, b,

$2\le a_i \le a$ and $1\le b_i \le b$ how many integers in b are a multiple of any integer $2\le a_i \le a$.

for example for a = 3 and b = 30 there are 20 such integers: 2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 26, 27, 28, 30.

So I am trying to do the math by hand to figure out the algorithm first. The second sample input I am given is a = 11 and b = 123. I know the answer is 97.

My approach is $\frac{123}{2}$ + $\frac{123}{3}$ + $\frac{123}{5}$ + $\frac{123}{7}$ + $\frac{123}{11}$ = 154, then I subtract the numbers I have counted twice so,

154 - $\frac{123}{2*3}$ - $\frac{123}{2*5}$ - $\frac{123}{2*7}$ - $\frac{123}{2*11}$ - $\frac{123}{3*5}$ - $\frac{123}{3*7}$ $\frac{123}{3*11}$ - $\frac{123}{5*7}$ - $\frac{123}{5*11}$ - $\frac{123}{7*11}$

= 87

from here I am not quite sure where to go.

$\endgroup$
  • $\begingroup$ Just do $$87+\left(\frac {123}{2*3*5}+\frac {123}{11*3*5}+\frac {123}{2*3*11}+\frac {123}{2*11*5}\right)-\left(\frac {123}{2*3*5*11}\right)$$ $\endgroup$ – Rohan Shinde Feb 13 '18 at 3:17
  • $\begingroup$ FYI you will not get the right answer in your example because you forgot the prime $7$. $\endgroup$ – bames Feb 13 '18 at 3:39
  • $\begingroup$ thank you. I can't believe I missed that. $\endgroup$ – k4iru Feb 13 '18 at 3:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.