2018-1-17

# Special Pythagorean Triplet solved with Reason

Brute force is a good enough approach when finding small Pythagorean triplets, but unsuitable with greater target sums. When brute force takes minutes, a smarter approach will take microseconds.

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
Jan Järfalk — User experienced esthete, technician, geek and web worker. Aspiring artist and recreational mathematician. I indulge and travel plenty. Constraints are good.