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 a^{2} + b^{2} = c^{2}. There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

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 |

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 |

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 |

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 |

- [animation] Unknown Pleasures
- [tech-test] What is a binary tree and how to invert it using Kotlin
- [project-euler] Find Highly Divisible Triangular Numbers with Kotlin
- [project-euler] Find the Largest Product in a Grid with Rust
- [project-euler] Summation of the First Two Million Primes with Rust
- [project-euler] Finding the largest product in a series with Rust
- [project-euler] Finding the 10001st prime with Rust
- [js] The complete list of rational numbers with Stern-Brocot and Javascript
- [project-euler] Project Euler number six solved with Rust
- [project-euler] Smallest positive number that is evenly divisible by all of the numbers from 1 to 20 with Rust
- [project-euler] Finding the largest palindrome product with Rust
- [project-euler] Get the largest prime factor with Reason
- [project-euler] Find the sum of all even Fibonacci numbers below four million with OCaml
- [project-euler] Finding the sum of all multiples of 3 or 5 below 1000 with OCaml
- [project-euler] Special Pythagorean Triplet solved with Reason
- [personal] New Year's Resolution 2018