Project Euler 9

http://projecteuler.net/index.php?section=problems&id=9

この手の直角三角形の問題はピタゴラス数の生成式を使うのが定番です。

a = l(m² - n²) b = 2lmn c = l(m² + n²)
a + b + c = 2lmn'
n' = m + n
m > n
mとnは互いに素

500を3つの積で表してそれが条件に合うか調べればよいです。それには500を素因数分解して、約数を出す処理を2回繰り返します。これらはがんばれば書けます。
さて、タプルについてF#ではこういうシンタックスも可能だったんですね。

let a, b = (1, 2)
printfn "%d %d" a b  // 1 2

これでもOKです。

let c, d = 3, 4
printfn "%d %d" c d  // 3 4

こういうこともできます。

for x, y in [ (1, 2); (3, 4) ] do
   printfn "%d %d" x y

let rec calc_exp n p =
   if n % p = 0 then
      let t = calc_exp (n / p) p
      (fst t + 1, snd t)
   else
      (0, n)

let rec fac n p =
   if n = 1 then
      []
   else if p * p > n then
      [(n, 1)]
   else
      let t = calc_exp n p
      if fst t > 0 then
         (p, fst t) :: (fac (snd t) (p + 1))
      else
         fac n (p + 1)

let factorize n = fac n 2

let rec pow n e = if e = 0 then 1 else
                  let m = pow n (e / 2)
                  if e % 2 = 1 then m * m * n else m * m

let rec value_f f = List.fold (fun x y -> x * (pow (fst y) (snd y))) 1 f

let rec divisors = function
      | [] -> [([], [])]
      | (p,e)::fs -> 
            [ for t in (divisors fs) do
                  for e' in [0..e]
                     -> if e' = 0 then (fst t, (p, e)::(snd t))
                        else if e' = e then ((p, e)::(fst t), snd t)
                        else ((p, e')::(fst t), (p, e - e')::(snd t)) ]

let divs n =
      let f = factorize n
      [ for f1, f2 in divisors f do
            for f3, f4 in divisors f2
                  -> (value_f f1, value_f f3, value_f f4) ]

let rec gcd m n = if m % n = 0 then n else gcd n (m % n)

let is_valid t =
      let l, m, n = t
      m < n && n < m * 2 && n % 2 = 1 && gcd m n = 1

let product t =
      let l, m, n' = t
      let n = n' - m
      2 * l * l * l * m * n * (m * m * m * m - n * n * n * n)

let N = 1000
printfn "%A" (List.map product (List.filter is_valid (divs (N / 2))))