# Project Euler Problem 75

Project Euler Problem 75 solution partially builds on solution to Project Euler Problem 39. But the main strategy is the following.

There is known Euclid’s formula for generation of Pythagorean triples given two numbers.

We can produce all triples and, subsequently, perimeters from all applicable combinations of two numbers, then filter in perimeters that occur only once and take their count for the answer.

Two easy prerequisites prior to code:

- it stems from the Euclid’s formula that the larger of numbers is limited from above by square root of half of the largest perimeter
- as Euclid’s formula does not produce all triples the missing perimeters can be produced as multiples of perimeters corresponding to primitive triples

// Euclidean algorithm for gcd(n,m) let rec gcd n m = match m with | 0 -> n | _ -> gcd m (n % m) let maxPerimeter = 1500000 let maxSide = maxPerimeter/2 |> (float >> sqrt >> int) // Euclid's formula for generating Pythagorean triples // (http://en.wikipedia.org/wiki/Pythagorean_triple) let perimeters = let multiples p = Seq.unfold (fun perimeter -> if perimeter <= maxPerimeter then Some(perimeter, perimeter + p) else None) p [ for m in 2..maxSide do for n in 1..(m - 1) do if (n + m) % 2 = 1 && (gcd n m = 1) then yield! multiples (2 * (m*m + n*m)) ] let problem075() = perimeters |> Seq.groupBy id |> Seq.fold (fun sum (x,y) -> if Seq.length y = 1 then sum + 1 else sum) 0

This solution takes about 2s. Looking into execution profile revealed that most heavy hit on performance belongs to **Seq.groupBy**. This fact turned me towards a more imperative approach based on direct caching of found profiles into an array. There we will distinguish three cases: a perimeter **p** is either not encountered, or encountered exactly once, or encountered more, than once. Further, we can use the unoccupied cell corresponding to zero perimeter for calculating “exactly once” occurences on the fly while we’re filling the array. Here we add to it on the first occurence of each unique perimeter value and subtract one as soon as we find that a perimiter occurs more, than once.

let rec gcd n m = match m with | 0 -> n | _ -> gcd m (n % m) let maxPerimeter = 1500000 let maxSide = maxPerimeter/2 |> (float >> sqrt >> int) let problem075() = let allPerimeters: int[] = Array.zeroCreate (maxPerimeter + 1) let rec multiples p' p = if p' <= maxPerimeter then if allPerimeters.[p'] = 0 then allPerimeters.[0] <- allPerimeters.[0] + 1 allPerimeters.[p'] <- 1 elif allPerimeters.[p'] = 1 then allPerimeters.[0] <- allPerimeters.[0] - 1 allPerimeters.[p'] <- -1 multiples (p' + p) p // Euclid's formula for generating Pythagorean triples // (http://en.wikipedia.org/wiki/Pythagorean_triple) for m in 2..maxSide do for n in 1..(m - 1) do if (n + m) % 2 = 1 && (gcd n m = 1) then multiples (2 * (m*m + n*m)) (2 * (m*m + n*m)) allPerimeters.[0]

The second solution delivers an amazing performance improvement of approximately 44 times, shrinking it down to 46ms!