Lesson goal: Divisibility and the Principle of Inclusion-Exclusion

Previous: Father and Son Age Puzzle | Home | Next: Cryptarithmetic and divisibility

In the 1966 MAA High School Mathematics Contest (Problem #29), contestants were presented with this counting problem:

"The number of positive integers less than 1,000 divisible by neither 5 nor 7 is:"

To solve this, we cannot simply count how many numbers are divisible by 5, add how many are divisible by 7, and subtract from the total. Why? Because some numbers are divisible by both 5 and 7 (like 35, 70, 105...), and they would be subtracted twice!

To handle overlapping sets properly, mathematicians use the Principle of Inclusion-Exclusion: $$|A \cup B| = |A| + |B| - |A \cap B|$$ Let $N = 999$ be the total number of positive integers strictly less than 1,000:
  • Divisible by 5: $|A| = \lfloor 999 / 5 \rfloor = 199$
  • Divisible by 7: $|B| = \lfloor 999 / 7 \rfloor = 142$
  • Divisible by both 5 and 7 (multiples of $\text{lcm}(5, 7) = 35$): $|A \cap B| = \lfloor 999 / 35 \rfloor = 28$
Applying the formula, the number of integers divisible by 5 or 7 is: $$|A \cup B| = 199 + 142 - 28 = 313$$ Therefore, the count of integers divisible by neither 5 nor 7 (the complement) is: $$N - |A \cup B| = 999 - 313 = 686$$ In this lesson, we will see how a simple computer loop verifies this mathematical principle in milliseconds!
count = 0
for n = 1, 999 do
  -- Divisible by neither 5 nor 7: Replace ???? with 5 and 7 if n % ???? ~= 0 and n % ???? ~= 0 then
    count = count + 1
  end
end
print(count)
Move the mouse over a dotted box for more information.

  • Modulo operator %: n % d == 0 tests if $n$ is evenly divisible by $d$. The condition n % 5 ~= 0 and n % 7 ~= 0 ensures that neither 5 nor 7 divides $n$.
  • Why Inclusion-Exclusion matters: In a small problem, a computer loop can test numbers one-by-one. But if we asked for numbers less than 1,000,000,000,000, the loop would take hours, while the mathematical formula $\lfloor N/5 \rfloor + \lfloor N/7 \rfloor - \lfloor N/35 \rfloor$ calculates the answer instantly!

Now you try. Run the code to see both methods match at 686. Then try changing $N$ to 10,000 to see how the formula scales effortlessly!

Type your code here:


See your results here: