(* f(0) = 0
     f(1) = 1
     f(2n) = n
     f(2n + 1) = f(n) + f(n + 1)
    --------------------------------

    a * f(2n) + b * f(2n + 1) = (a + b) * f(n) + b * f(n + 1)
    let F(x, y, z) = x * f(z) + y * f(z + 1)
    then
     F(a, b, 2n) = F(a+b, b, n)

    if z is even
     then F(x, y, z) = F(x + y, y, z / 2)
   else
     F(x, y, z) = x * f(z) + y * f(z + 1) = x * (f( (z - 1) / 2 ) + f( (z + 1) / 2)) + y * f( (z + 1) / 2)
       = x * f((z-1)/2) + (x + y) * f((z-1)/2 + 1)
       = F(x, x + y, (z - 1) / 2)
*)

let fusc (n : int) : int =
  let rec f x y z =
    if z == 0 then y
    else if z mod 2 = 0 then f (x + y) y (z / 2)
    else f x (x + y) ((z - 1) / 2)
  in
  f 1 0 n