Project Euler 12

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

素因数分解すれば簡単に約数の個数を数えることができます。n+1を素因数分解して、前に求めてあるnの素因数分解とかけて2で割ります。
これ、エラーになるんですね。

let f a = a.Head

printfn "%d" (f [2])

head.fs(1,11): error FS0072: Lookup on object of indeterminate type based on information prior to this program point. A type annotation may be needed prior to this program point to constrain the type of the object. This may allow the lookup to be resolved.

引数の型を指定すれば通ります。

let f (a : int list) = a.Head

printfn "%d" (f [2])

プロパティではなく関数を使えば型を指定しなくても通るんですね。

let f a = List.head a

printfn "%d" (f [2])

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 mul_f f1 f2 =
    if List.isEmpty f1 then
        if List.isEmpty f2 then
            []
        else
            f2
    else
        if List.isEmpty f2 then
            f1
        else
            let p1, e1 = f1.Head
            let p2, e2 = f2.Head
            if p1 = p2 then
                (p1, e1 + e2) :: (mul_f f1.Tail f2.Tail)
            else if p1 < p2 then
                f1.Head :: (mul_f f1.Tail f2)
            else
                f2.Head :: (mul_f f1 f2.Tail)

// fは2の成分を有していること前提
let half_f (f : (int * int) list) =
    let e = snd f.Head
    if e = 1 then
        f.Tail
    else
        (2, e - 1) :: f.Tail

let rec pow n e = if e = 0 then 1 else n * (pow n (e - 1))

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

let s = seq {
    let prev_fac = ref []
    for n in Seq.initInfinite(fun i -> i + 1) do
        let f = factorize(n + 1)
        let f2 = half_f (mul_f !prev_fac f)
        yield (val_f f2, List.fold (fun x y ->
                                    (x * ((snd y) + 1))) 1 f2)
        prev_fac := f
}

let N = 500
printfn "%A" (fst (Seq.head (Seq.filter (fun x -> snd(x) > N) s)))