# Finding the sum of all the multiples of 3 or 5 below 1000, using list comprehension

I'm trying to compare my own implementation with another solution of Project Euler problem #1, which uses a list comprehension:

module Progression1 (sumProgressions) where
import Prelude

sumProgressions :: Integer -> Integer -> Integer -> Integer
sumProgressions d1 d2 limit =
sum [n | n <- [1 .. limit], (n mod d1) == 0 || (n mod d2) == 0]


Mine is directly inspired by user nicocarlos' PHP solution on the PE site. It avoids using hard-coded constants, instead computing most of the values (with as much algebraic simplification as possible):

module Progression2 (sumProgressions2) where
aN               :: Integer -> Integer -> Integer -> Integer
pSum             :: Integer -> Integer -> Integer -> Integer
sumProgressions2 :: Integer -> Integer -> Integer -> Integer

aN a1 d n = a1 + (n - 1) * d  -- Calculating the value of the Nth term

pSum 0  d lim  = pSum d d lim -- a1 == 0 produces invalid pSum() result
pSum a1 d lim =
let n1 = (lim div d)            -- Using simplified method for finding n
n2 = ((lim - a1) div d + 1) -- Use non-simplified formula for calculation
in if (a1 == d)
then (d * n1 * (n1 + 1)) div 2      -- Assumes n1 is simplified
else (n2 div 2) * (a1 + aN a1 d n2) -- Non-simplified calculation

sumProgressions2 d1 d2 lim = let d3 = d1 * d2
in (pSum d1 d1 lim) + (pSum d2 d2 lim) - (pSum d3 d3 lim)


I'm new to Haskell and inexperienced with functional programming; I'd like suggestions for improving this code's performance and style.

Currently criterion is showing similar mean benchmark times for each solution, calculated for d1 = 3, d2 = 5, limit = 100000-1.

## Updated with current code:

This solves the bug mentioned in the accepted answer, and takes much of its advice on style (as well as discarding the simplified algebra.)

-- Using arithmetic progression formula for the Nth element aN, we can determine
-- the value aN = a1 + (N - 1) * d. Rearranging yields N = (aN - a1) / d + 1.
-- Calculates N, then the last aN, and uses it to find S = (N / 2) * (start + last)
pSum 0     diff limit = pSum diff diff limit
pSum start diff limit = truncate ((fromIntegral n / 2) * fromIntegral(start + last))
where n    = (limit - start) div diff + 1
last = start + (n - 1) * diff

-- Add the sums of two progressions and subtract sum of similar elements
sumProgressions2 :: Integer -> Integer -> Integer -> Integer
sumProgressions2 diff1 diff2 limit =
(pSum 0 diff1 limit) + (pSum 0 diff2 limit) - (pSum 0 diff3 limit)
where diff3 = lcm diff1 diff2


## Correctness:

Many reviewers will not bother to comment on code that is not correct. I might have kept this brief, myself, except that it was only in the process of considering optimization that I discovered that this code contains two bugs that prevent correct answers.

It shares one of those bugs with the simpler sumProgressions. The benefit of the simplicity of sumProgressions is that the bug has fewer places to hide there. Hint: Why does sumProgressions 3 5 1000 give the same answer as sumProgressions 3 5 1001?

The more serious bug is unique to sumProgressions2. Hint: Why does sumProgressions 3 6 20 give a different answer from sumProgressions2 3 6 20?

If I had noticed this earlier, my answer might have ended here.

But it seemed a shame to throw the rest of this away, so, (mostly) ignoring the cases in which the code fails...

## Style:

I don't see the benefit to the function type declarations all at the top separated from their implementations where they could have had some minor self-documentation effect.

You seem to be following the Haskell tradition of using one-letter symbols and minimal explanatory comments, as if it was obvious from the context that a1 is the first element of a progression and d is its delta and n is the number of elements. To me, these things were not all obvious, especially when n is either n1 or n2 and the '1' in n1 has nothing to do with the '1' in a1. I think that n' and n would have been a more idiomatic naming than n1 and n2, since they are variants of each other. Function header comments describing the input arguments would not have been out of place, nor would spelling out "delta" and "limit", but that may be an "m o" (meaning "minority opinion" -- obviously).

The formulas used in pSum are sufficiently complicated and their syntax not quite algebraic, so their intent is obscured. A comment explaining the intent in plain language like "multiplying ... first and last elements..." or pure algebra would help.

Since both aN and pSum are short and used only within pSum and sumProgressions2, respectively, I'd have opted for defining them under a where clause. In the case of pSum, that allows lim to be referenced in the parent scope so it doesn't need to be explicitly passed. This makes the structure of the code more readable, making it clear that aN and pSum serve sumProgressions2 and sumProgressions2 only. I'm guessing (mostly from the presence of a1) that this may not have been your intent, in which case you should have made that intent clear by exporting these functions or showing other uses within the module.

In fact, the purpose of a1 is confounded by the fact that a1 is only ever passed the same value as d by the 3 callers of pSum, and since pSum isn't exported from the module, those seem to be the only cases. From that perspective, a1 is only used once, in an equality test that always passes, so it seems that you could eliminate it and with it half the complexity of pSum.

Even if your intent is to provide pSum as a useful function outside of sumProgressions2, the usage of pSum in sumProgressions2 is so specialized and falls so cleanly into the "simplified" case that it still warrants its own separate truly simplified pSum function that takes no a1 argument.

Whether the existence of another more general pSum implementation is justified and whether its a1 == d case is worth optimizing -- or (as I suspect) similar simplification applies equally to the general case -- is outside the scope of the current problem.

Yet I think that there is a point to be made here about over-generalization. You could argue that you are doing a good thing by providing and using a more general solution that does not require a1 to equal d, but I don't think that argument holds up. It sounds like the same argument that justifies writing sumProgressions2 as a general solution that does not depend on the values 3, 5, and 1000. But consider the following:

sumProgressions3_5_1000 3   5 1000 = correctAnswerForEuler1
sumProgressions3_5_1000 d1 d2 lim   = let d3 = d1 * d2
in (pSum d1 d1 lim) + (pSum d2 d2 lim) - (pSum d3 d3 lim)


or even

sumProgressions3 3  d2 lim = specialCaseOptimizedFor3 d2 lim
sumProgressions3 d1 d2 lim = let d3 = d1 * d2
in (pSum d1 d1 lim) + (pSum d2 d2 lim) - (pSum d3 d3 lim)


Do you consider these to have the same benefits of generality as your original solution? To me, if (a1==d) in pSum defeats the purpose of the generalized solution just as much as this last example does. Your pSum just hard-codes for an arbitrary argument relationship rather than for an arbitrary argument value, but it's still arbitrary hard-coding for an arbitrary case.

There is danger in over-generalization. Testing and correctness is more difficult for a general function than for a more constrained or hard-coded function. Case in point, the bug triggered by arguments 3 6 20 does not effect cases like 3 5 1000. Also, optimization may be completely different when targeting all cases vs. average or typical cases vs. the special case that is going to be exercised in the benchmark. Case in point, it was only in considering an optimization that would benefit cases like 3 6 20 while slightly penalizing cases like 3 5 1000 that I discovered that I wasn't really optimizing this new case at all -- I was correcting it. And given the context/contest, I wasn't sure that optimizing or correcting the 3 6 20 case was really "in scope". I decided that what was in scope was a style critique along the lines of:

The good work of substituting code that works in many general cases for code that only needs to handle a specific case may not be worthwhile unless the code is correct for the general case or guards against the cases it does not handle correctly.

You've got a good solution to the problem of sumProgressions2 3 5 1000 disguised as a faulty solution to the problem of sumProgressions2 d1 d2 limit. So, technically, you'd be in better shape if you had been less ambitious.

## Optimization:

There's not much to say here, except that the correction for the 3 6 20 case (arguably out of scope and counter-productive to the optimization of the 3 5 1000 solution) was originally mis-identified as a missing optimization. As it turns out, there seem to be multiple edge cases that require either more processing or less processing than 3 5 1000.

Eliminating a1 from pSum would help to focus the effort on the calculation of n1 and its use rather than on dead code. As far as I can see, there's no better formulation -- no reason to prefer (n*n+n) over n*(n+1) or to prefer (lim - (lim mod d))*(n+1) over d*(lim div d)*(n+1), given that n+1 requires (lim div d) to be calculated in either case. But I could be wrong, and easily proven wrong by some quick benchmarks. So, your solution seems optimal within the current structure of sumProgressions2 as 3 calls to pSum.

The only other way I could see to further optimize the code would be IF there was an alternative way of expressing the third call to pSum so that it eliminated some operations in favor of re-using sub-expressions from the first two pSum calls. I don't know if this is possible. What I'm imagining is something like a reformulation of the pSum functions, especially the one used in the 3rd call, that took advantage of a fact like (d1*d2)*(d1*d2) == (d1*d1)*(d2*d2) (assuming that result to be useful) to reuse (d1*d1) and (d2*d2) values calculated already in the first two (reformulated) pSum calls. I don't know enough about Haskell internal optimizations to know if it can access function results "recently memoized" in called "sibling" functions. If not, I'd guess you would pass the useful sub-expressions like (d1*d1) from sumProgressions2 into the pSum calls. This whole idea could turn out to be too ugly for serious consideration, so you might be better off where you are.

• +1 just because you obviously took a LONG time to provide a thorough answer (hope that doesn't make me a bad netizen) – jlnorsworthy Jan 13 '12 at 0:47

I'll leave the question open, but here are some other attempts. Credit goes to RMartinhoFernandes for solution3, which requires his Pointfree module for the /\ combinator.

sumProgressions3 :: Integer -> Integer
sumProgressions3 limit = solve [1 .. limit]
multipleOf n = (== 0) . (mod n)
multipleOf3Or5 = uncurry (||) . ((multipleOf 3) /\ (multipleOf 5))
solve = sum . filter multipleOf3Or5


And solution4 is a completely in-lined version of the simplified formula in my question:

sumProgressions4 :: Integer -> Integer -> Integer -> Integer
sumProgressions4 d1 d2 lim = let d3 = d1 * d2
in d1 * (lim div d1) * (1 + (lim div d1)) div 2
+ d2 * (lim div d2) * (1 + (lim div d2)) div 2
- d3 * (lim div d3) * (1 + (lim div d3)) div 2


I've repeated the benchmarks on my machine with the same parameters as above.

• You can use (&&&) from Control.Arrow instead of (/\). Also, pointful version is much nicer in this case. – Rotsor Jan 21 '12 at 1:12

The solutions posted so far seem a bit overcomplicated to me, so I thought I'd share my solution:

sum_of_first_n_numbers n = n * (n + 1) div 2

sum_of_multiples max factor = sum_of_first_n_numbers (max div factor) * factor

solution = sum_of_multiples 999 3 + sum_of_multiples 999 5 - sum_of_multiples 999 15

• +1 for "so far ... overcomplicated" and a clean solution, tho' just a little terse for my taste -- 999 and 15 appear out of nowhere to save the day -- it makes for a great happy ending, but it's not a very reassuring story. – Paul Martel Jan 13 '12 at 3:51

I know this isn't code golf, but may I point out that you don't need fancy operators to express (mod x 3 == 0) && (mod x 5 == 0):

sum \$ filter ((>1).(gcd 15)) [1..999]