The loop and the closed form

Problem 1 is the sum of all multiples of 3 or 5 below 1000. The solution here builds the range, iterates, and adds. Correct, O(n), instant.

It is also the clearest illustration of what Euler is actually teaching, which is not how to write a loop. Inclusion-exclusion gives the same answer in constant time: sum the multiples of 3, add the multiples of 5, subtract the multiples of 15 because they were counted twice, using the arithmetic series formula for each. Three multiplications instead of a thousand iterations.

At n = 1000 the difference is unmeasurable, and that is the point. The loop and the formula are indistinguishable until the problem says 10^12, at which point one finishes and the other does not. Euler problems are built so the naive solution works on the example and fails on the real input, which teaches complexity better than being told about it.

Verifying the closed form against the loop at small n is the habit worth keeping, because a formula off by one at the boundary looks exactly like a correct one.

Two files. I did problem 1, did problem 2, and stopped.