Math Fundamentals18 sections · 814 units
Open in Course

Nth Magical Number - Counting Formula

Inclusion-exclusion principle

How many magical numbers are ≤ x? Count multiples of a, plus multiples of b, minus multiples of lcm(a, b) to avoid double-counting.

Formula: count(x) = floor(x/a) + floor(x/b) - floor(x/lcm(a,b)).

Example: a = 2, b = 3, x = 12. Multiples of 2: 6. Multiples of 3: 4. Multiples of 6: 2. Total = 6 + 4 - 2 = 8.