Special Pythagorean Triplet solved with Reason

The ninth Project Euler problem - Special Pythagorean Triplet - is stated as follows. A Pythagorean triplet is a set of three natural numbers, a < b < c, for which a2 + b2 = c2. There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

Solving with brute force

The easiest way to solve this problem is by brute force and iterate through all possible values of a, b and c where their sum equals 1000.

let findTriplet = (sum) =>
  for (a in 1 to sum) {
    for (b in a to sum) {
      let c = sum - a - b;
      if (a * a + b * b === c * c) {
        print_int(a * b * c)
      }
    }
  };

findTriplet(1000); /* ==> 31875000 */

One of the first noticeable problems with the brute force approach is that it does not scale very well. When finding a triplet with the sum 1000 takes milliseconds it takes minutes to find a triplet with the sum 100000.

Sum Execution Time (s)
1000 0.009845
10000 0.964073
100000 92.694244

Brute force with smaller bounds

By applying some wetware to this problem, we can make the bounds for the loops smaller.

We can deduce that a < 1000/3 since if a is not less than 1000/3, then b and c can’t be greater than a.

We can also deduce that b < 1000/2 since if b is greater than 1000/2, c can’t be greater than b.

let findTriplet = (sum) => {
  let rec next = (a, b) => {
    let c = sum - a - b;
    switch (a * a + b * b === c * c) {
    | true => a * b * c
    | false when b < sum / 2 => next(a, b + 1)
    | false when a < sum / 3 => next(a + 1, a + 2)
    | _ => 0
    }
  };
  next(1, 2)
};

findTriplet(1000); /* ==> 31875000 */

The shorter loops significantly speed up the solution, but unfortunately, it still has the same scaling behavior.

Sum Execution Time (s)
1000 0.002457
10000 0.256682
100000 26.623702

Multiple possible triplets

Another flaw with the code above, when we start looking for a more general solution, is that we cannot be sure that there exists only one Pythagorean triplet where a + b + c = 1000 since it only returns the first triplet it encounters.

let findTriplets = (sum) => {
  let rec next = (a, b, memo) => {
    let c = sum - a - b;
    let nextMemo = a * a + b * b === c * c ? [a * b * c, ...memo] : memo;
    switch (b < sum / 2, a < sum / 3) {
    | (true, true) => next(a, b + 1, nextMemo)
    | (false, true) => next(a + 1, a + 2, nextMemo)
    | _ => memo
    }
  };
  next(1, 2, [])
};

findTriplets(990); /* ==> 34178760, 29452500, 28030860, 19645560 */

Adding that functionality takes a toll on the execution time and makes it even more apparent that this approach is flawed for greater sums.

Sum Execution Time (s)
1000 0.005372
10000 0.581307
100000 54.624186

The holy grail

After you turn in your answer to Project Euler you get access to a solution using parametrisation of Pythagorean triplets. I did this Reason implementation below just to see how it compare to my solitions - minutes became microseconds.

let getTriplet = (sum) => {
  let s2 = sum / 2;
  let mlimit = ceil(sqrt(float_of_int(s2))) -. 1.0;
  let rec gcd = (a, b) => b === 0 ? a : gcd(b, a mod b);
  let rec rss = (sm) => sm mod 2 === 0 ? rss(sm / 2) : sm;
  let search = (m, s2, memo) => {
    let sm = rss(s2 / m);
    let rec helper = (k) =>
      if (k < 2 * m && k <= sm) {
        if (sm mod k === 0 && gcd(k, m) === 1) {
          let d = s2 / (k * m);
          let n = k - m;
          let a = d * (m * m - n * n);
          let b = 2 * d * m * n;
          let c = d * (m * m + n * n);
          [a * b * c, ...memo]
        } else {
          helper(k + 2)
        }
      } else {
        memo
      };
    helper(m + m mod 2 + 1)
  };
  let rec helper = (m, memo) =>
    switch (s2 mod m === 0, m < int_of_float(mlimit)) {
    | (true, true) => helper(m + 1, search(m, s2, memo))
    | (true, false) => search(m, s2, memo)
    | _ => helper(m + 1, memo)
    };
  helper(2, [])
};

getTriplet(990) |> Array.of_list |> Array.map(string_of_int) |> Array.map(print_endline);
Sum Execution Time (s)
1000 0.000006
10000 0.000010
100000 0.000018