I approached by finding the number of integers between 1 and 3000 inclusive and the number of integers between 1 and 2000 inclusive, finding the difference between these and subtracting it from 1000 (the number of integers between 2001 and 3000 inclusive).
This gives me (all fractions have the floor function on them:
$
1000-(\frac{3000}{3}+\frac{3000}{7}+\frac{3000}{13}-\frac{3000}{3*7}-\frac{3000}{3*13}-\frac{3000}{7*13}+\frac{3000}{3*7*13}-(\frac{2000}{3}+\frac{2000}{7}+\frac{2000}{13}-\frac{2000}{3*7}-\frac{2000}{3*13}-\frac{2000}{7*13}+\frac{2000}{3*7*13}))
$
which gives me
$
1000-(1000+428+230-142-76-32+10-(666+285+153-95-51-21+7))= 526
$
Is this the correct, if so would this be the most efficient way to calculate it, if not, how would I go about performing this calculation?
Thanks
Best Answer
This is correct, and is the most efficient way to calculate it for the numbers $3,7,13$. The final answer is correct also. Basically, inclusion-exclusion is the way to go if the range that you're checking (in this case $2000$ to $3000$) is "large" and the number of things that are not allowed to be multiples (in this case, $3$) is "small".