Skip to content

Project Euler Problem 75

January 31, 2012

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:

  1. 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
  2. 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!

Advertisements

From → Project Euler

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: