The following derivation produces two formulas that appear equivalent, yet behave differently when implemented.
What’s going on?
Problem: Write a program to find the sum of all multiples of
3 or 5 up to a given integer n. If a number is a
multiple of both, count it only once.
At first glance, this problem looks straightforward. One natural approach is to add all multiples of 3, add all multiples of 5, and subtract the multiples of 15 once to account for double-counting.
We can write the sum as:
\[ f(n) = (3 + 6 + 9 + \dots) + (5 + 10 + 15 + \dots) - (15 + 30 + 45 + \dots) \]Each of these is an arithmetic series, so we factor out the constants:
\[ = 3(1 + 2 + 3 + \dots) + 5(1 + 2 + 3 + \dots) - 15(1 + 2 + 3 + \dots) \]Let \( S(k) = \frac{1}{2}k(k+1) \) denote the sum of the first \( k \) positive integers. Then:
\[ = 3S(n/3) + 5S(n/5) - 15S(n/15) \tag{1} \]Expanding this gives:
\[ = 3 \cdot \frac{1}{2}\frac{n}{3}\left(\frac{n}{3}+1\right) + 5 \cdot \frac{1}{2}\frac{n}{5}\left(\frac{n}{5}+1\right) - 15 \cdot \frac{1}{2}\frac{n}{15}\left(\frac{n}{15}+1\right) \]Which simplifies to:
\[ = \frac{n}{2} \left( \frac{n}{3} + 1 + \frac{n}{5} + 1 - \frac{n}{15} - 1 \right) \]And finally:
\[ = \frac{n}{2} \left( \frac{n}{3} + \frac{n}{5} - \frac{n}{15} + 1 \tag{2} \right) \]Full Python code (copy-paste):
# Sum of first k numbers
def s(k):
return (k * (k + 1)) // 2
# From Equation 1
def ss(n):
return 3 * s(n // 3) + 5 * s(n // 5) - 15 * s(n // 15)
# From Equation 2
def sss(n):
return (n // 2) * (n // 3 + n // 5 - n // 15 + 1)
# Testing both implementations:
# (n, expected)
tests = [
(3, 3),
(5, 8),
(0, 0),
(10, 33),
(1000, 234168),
]
for n, expected in tests:
print(n, expected, ss(n), sss(n))
Output:
| n | expected | ss(n) | sss(n) |
|---|---|---|---|
| 3 | 3 | 3 | 2 |
| 5 | 8 | 8 | 6 |
| 0 | 0 | 0 | 0 |
| 10 | 33 | 33 | 30 |
| 1000 | 234168 | 234168 | 234000 |
The function ss produces the correct result.
The function sss does not.
Both come from the same derivation. Both look algebraically equivalent.
So why do they behave differently?