Project Euler Problem 9 Solution

Question

A Pythagorean triplet is a set of three natural numbers, a \lt b \lt c, for which

a^2 + b^2 = c^2

For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.

There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product a \times b \times c.

Clojure

#!/usr/bin/env clojure
(defn square [n]
  (* n n))

(defn triple? [a b c]
  (and
    (and (> a 0) (> b 0) (> c 0))
    (and (< a b) (< b c))
    (= (+ (square a) (square b)) (square c))))

(defn candidates [limit]
  (for [a (range 1 (inc limit)) 
        b (range a (inc limit)) 
        c (range b (inc limit))
        :when (and 
                (= (+ a b c) 1000)
                (triple? a b c))] 
    (list a b c)))

(println (reduce * (first (candidates 500))))

$ time clojure pythagorean-triples.clj
real   0m1.600s
user   0m2.626s
sys    0m0.299s

Go

package main

import "fmt"

func main() {
    var a, b, c, lb int
    max := 1000
    for a = 1; a < max; a++ {
        lb = max - a
        for b = a; b < lb; b++ {
            c = max - (a + b)
            if a*a+b*b == c*c {
                fmt.Println(a * b * c)
                return
            }
        }
    }
}

$ go build -o pythagorean pythagorean.go
$ time ./pythagorean
real   0m0.001s
user   0m0.000s
sys    0m0.001s

Haskell

main ::  IO ()
main = print $ head [a*b*c | a <- [1..500], b <- [a..500], c <- [b..500],
                             a+b+c == 1000, a*a + b*b == c*c]

$ ghc -O2 -o pythagorean pythagorean.hs
$ time ./pythagorean
real   0m0.376s
user   0m0.368s
sys    0m0.008s

JavaScript

for (let a = 1; a < 1000; a++) {
  for (let b = a, lb = 1000 - a; b < lb; b++) {
    const c = 1000 - (a + b)
    if (a * a + b * b === c * c) {
      return console.log(a * b * c)
    }
  }
}

$ time node --use-strict pythagorean.js
real   0m0.054s
user   0m0.047s
sys    0m0.008s

Ruby

#!/usr/bin/env ruby
for a in (1..500)
  for b in (a..500)
    for c in (b..500)
      if a**2 + b**2 == c**2 and a+b+c == 1000
        puts a*b*c
      end
    end
  end
end

$ time ruby pythagorean-triples.rb
real   0m3.244s
user   0m3.227s
sys    0m0.016s

Rust

fn main() {
    for a in 1..1000 {
        for b in a..(1000 - a) {
            let c = 1000 - (a + b);
            if a * a + b * b == c * c {
                return println!("{}", a * b * c);
            }
        }
    }
}

$ rustc -C target-cpu=native -C opt-level=3 -o pythagorean pythagorean.rs
$ time ./pythagorean
real   0m0.001s
user   0m0.000s
sys    0m0.001s