Sum of multiples of 3 or 5 below N How do I improve speed of this code? The problem definition is "Find the sum of all the multiples of 3 or 5 below N".

{-# LANGUAGE BangPatterns #-}
{-# OPTIONS_GHC -O2 -optc-O2 #-}
import qualified Data.ByteString.Lazy as L
import Control.Monad (forM_)

readInt :: L.ByteString -&gt; Int
readInt !s = L.foldl' (\x c -&gt; 10 * x + fromIntegral c - 48) 0 s

main :: IO ()
main = do 
    -- don't need number of inputs, since it is read lazily.
    (_:ls) &lt;- L.split 10 `fmap` L.getContents
    -- length ls &lt;= 10^5
    forM_ ls $ \ l -&gt; 
        print $ f . readInt $ l 

-- n &lt;= 10^9
f :: Int -&gt; Int
f n = go 0 0
  where
    go i !a | i == n = a
            | i `mod` 3 == 0 || i `mod` 5 == 0 = go (i+1) (a+i)
            | otherwise         = go (i+1) a
Specification

There is  some possible ambiguity in the specification: Are multiples of 15 counted once as in FizzBuzz or twice as in a more mathematical specification?

Mathematics

The general problem of summing a sequence of integers is well understood



The pseudo code for the FizzBuzz version of the problem:

   threes   = (n/3).toInteger
   fives    = (n/5).toInteger
   fifteens = (n/15).toInteger

   sigmaThrees = [threes * (threes + 1) / 2] * 3
   sigmaFives = ...
   sigmaFifteens = ...

   return sigmaThrees + sigmaFives - sigmaFifteens


Implementation

The implementation should use Haskell's quot to perform integer division.

Performance

Blazingly fast. Not just because there are few calculations but also quot usually runs as a hardware integer operation.