Hi,
It took me a while to find a quick algorithm for generating an array of Euler's Totient numbers, so I thought I would share the result. This is useful for a some Project Euler chalanges.
#light;;
///Returns an array of Euler's Phi numbers starting at Phi(0)
let EulerPhi n =
let totarr = Array.init (n + 1) (fun x -> Int64.of_int x)
{2 .. n} |>
Seq.iter (fun x ->
let x64 = Int64.of_int x
if (totarr.[x] = x64) then
(totarr.[x] <- totarr.[x] - 1L)
{(x + x) .. x .. n} |> Seq.iter (fun q -> totarr.[q] <- (totarr.[q] * (x64 - 1L) / x64))
else ())
totarr;;
[Edit: Added Int64 casting to prevent integer overflow for large inputs.]