Euler's First Problem

Actually, Euler project's first problem:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

This is simple enough (it is ranked first by the number of solutions to it) that you can cook up a brute-force solution in minutes, and the limit parameter N = 1,000 is so low that brute-forcing it is quite reasonable. First, a natural-interval-producing function:

let rec between m n =
  if m >= n then [] else
  m :: between (m + 1) n

With this, the problem gets solved by:

open List

let prob1 max = fold_left (+) 0
  (filter (fun p -> p mod 3 = 0 || p mod 5 = 0)
    (between 1 max))

And so, it instantaneously gives that:

# prob1 1000 ;;
- : int = 233168

(Sorry about the spoiler.) There is, however, the nagging sensation that there's not much point in going through every number, discarding those that we don't want and summing those which are left. Can't we just generate those multiples of 3 or 5 directly, without chaff so to speak? Yes, by a trick analogous to Dijkstra's solution to the so-called Hamming problem:

let prob1 max =
  let rec iter sm p3 p5 =
    let m, q3, q5 =
      if p5 < p3 then p5, p3,   p5+5 else
      if p3 < p5 then p3, p3+3, p5   else
                      p3, p3+3, p5+5 in
    if m >= max then sm else
    iter (m + sm) q3 q5
  in iter 0 0 0

The idea of the inner loop is to keep the running sum and the next multiples of 3 and 5 to consider next. Of both, the least is added to the sum and updated in turn, up to the requested limit. This not only limits the numbers needing to be inspected precisely to the multiples of 3 or 5 in order, but it also deforests completely the intermediate lists in the original program.

For N = 1,000, there's no perceptible difference between both versions, but for N = 100,000 there is some, and for N = 1,000,000 the non-tail-recursive between blows the stack (and the second version overflows an integer, so I guess both fail miserably.)

This problem is indeed so simple that I'd leave it at that, were not for the fact that it rather easily gives in to some analysis. Let:

s3 = [sum i : 0 ≤  3*i < 1000 :  3*i]
s5 = [sum i : 0 ≤  5*i < 1000 :  5*i]
sf = [sum i : 0 ≤ 15*i < 1000 : 15*i]

By the inclusion-exclusion principle, prob1 1000 = s3 + s5 - sf. Also:

 3*i < 1000  ⇐  i < ⌈1000/ 3⌉ = 334;
 5*i < 1000  ⇐  i < ⌈1000/ 5⌉ = 200;
15*i < 1000  ⇐  i < ⌈1000/15⌉ =  67.

It is well known that:

s.n = [sum i : 0 ≤ i < n : i] = n*(n-1)/2.

Substituting:

s3 =  3*[sum i : 0 ≤ i < 334 : i] =  3 * s.334 = 166833
s5 =  5*[sum i : 0 ≤ i < 200 : i] =  5 * s.200 =  99500
sf = 15*[sum i : 0 ≤ i <  67 : i] = 15 * s. 67 =  33165

and so, the analytic solution is, simply 166833 + 99500 - 33165 = 233168. In the general case for arbitrary limit max:

let prob1 max =
  let (//) n k = int_of_float (ceil (float_of_int n /. float_of_int k))
  and sum  n   =
    if n land 1 == 0
    then (n / 2) * (n - 1)
    else n * ((n - 1) / 2)
  in
  3 * sum (max // 3)  +  5 * sum (max // 5)  -  15 * sum (max // 15)

The only complication is avoiding overflow in the arithmetic sum. Of course, this is easy to generalize to an arbitrary-precision version, except maybe for the ceilinged division, which needs adding one if the dividend doesn't evenly divide the divisor.