Project Euler in OCaml

euler.ml

#load "nums.cma";;
#load "prime.cmo";;

open Big_int;;

let p1 () =
  let sum = ref 0 in
  for i = 1 to 1000 - 1 do
    if i mod 3 = 0 || i mod 5 = 0 then sum := !sum + i
  done;
  !sum;;

let p2 () =
  let sum = ref 0 in
  let a = ref 1 and b = ref 2 in
  while !a < 4_000_000 do
    if !a mod 2 = 0 then sum := !sum + !a;
    let c = !a + !b in a := !b; b := c
  done;
  !sum;;

let p3 () =
  let number = ref (big_int_of_string "600851475143") in
  let limit = ref (int_of_big_int (sqrt_big_int !number)) in
  let i = ref 3 in
  while !i <= !limit do
    let flag = ref false in
    while int_of_big_int (mod_big_int !number (big_int_of_int !i)) = 0 do
      number := div_big_int !number (big_int_of_int !i);
      flag := true
    done;
    if !flag then limit := int_of_big_int (sqrt_big_int !number);
    i := !i + 2
  done;
  int_of_big_int !number;;

let rec gcd a b =
  if b = 0 then a
  else gcd b (a mod b);;

let lcm a b =
  a / (gcd a b) * b;;

let p5 () =
  let result = ref 1 in
  for i = 1 to 20 do
    result := lcm !result i
  done;
  !result;;

let p6 () =
  let a = ref 0 and b = ref 0 in
  for i = 1 to 100 do
    a := !a + i * i;
    b := !b + i
  done;
  b := !b * !b;
  !b - !a;;

let p7 () =
  let p = new Prime.prime in
  for i = 1 to 10000 do
    ignore p#next
  done;
  p#next;;

let triple_with_sum n f =
  for a = 1 to n / 3 do
    for b = a to n / 2 do
      let c = n - a - b in
      if a * a + b * b = c * c then f a b c
    done
  done;;

let p9 () =
  let product = ref 0 in
  triple_with_sum 1000 (fun a b c -> product := a * b * c);
  !product;;

let sqrt_int n =
  int_of_float (sqrt (float_of_int n));;

let sieve n =
  let a = Array.make n true in
  let i = ref 2 in
  while !i < sqrt_int n do
    if a.(!i) then begin
      let j = ref (!i + !i) in
      while !j < n do
        a.(!j) <- false;
        j := !j + !i
      done
    end;
    i := !i + 1
  done;
  a;;

let p10 () =
  let a = sieve 2_000_000 in
  let sum = ref (big_int_of_int 0) in
  for i = 2 to 2_000_000 - 1 do
    if a.(i) then sum := add_big_int !sum (big_int_of_int i)
  done;
  string_of_big_int !sum;;

let exponent n p =
  let rec iter n p c =
    if n mod p = 0 then iter (n / p) p (c + 1)
    else c in
  iter n p 0;;

let number_of_divisors n =
  let l = sqrt_int n in
  let a = sieve l in
  let result = ref 1 in
  for i = 2 to l - 1 do
    if a.(i) then
      let e = exponent n i in
      result := !result * (e + 1)
  done;
  !result;;

let triangle n =
  n * (n + 1) / 2

let p12 () =
  let rec iter i =
    let n = triangle i in
    let d = number_of_divisors n in
    if d > 500 then n
    else iter (i + 1) in
  iter 1;;

let p14 () =
  let size = 100 in
  let a = Array.make size 0 in
  a.(1) <- 1;
  let collatz n =
    let rec i1 n l =
      if a.(n) <> 0 then n :: l
      else if n mod 2 = 0 then i1 (n / 2) (n :: l)
      else i1 (n * 3 + 1) (n :: l) in
    let rec i2 d l =
      match l with
      | [] -> ()
      | h :: t ->
        Printf.printf "T: %d\n" h;
        if h < size then begin
          a.(h) <- (d + 1)
        end;
        i2 (d + 1) t in
    let f l =
      match l with
      | [] -> ()
      | h :: t ->
        Printf.printf "H: %d\n" h;
        i2 a.(h) t in
    f (i1 n []) in
  for i = 1 to size - 1 do
    collatz i
  done;
  a;;

let digit_sum_big_int n =
  let sum = ref 0 and num = ref n in
  while gt_big_int !num (big_int_of_int 0) do
    let q, r = quomod_big_int !num (big_int_of_int 10) in
    sum := !sum + (int_of_big_int r);
    num := q
  done;
  !sum;;

let p16 () =
  let product = ref (big_int_of_int 1) in
  for i = 1 to 1000 do
    product := mult_big_int !product (big_int_of_int 2)
  done;
  digit_sum_big_int !product;;

let p20 () =
  let product = ref (big_int_of_int 1) in
  for i = 1 to 100 do
    product := mult_big_int !product (big_int_of_int i)
  done;
  digit_sum_big_int !product;;

let sigma n =
  let rec iter n i a =
    if n = i then a
    else if n mod i = 0 then iter n (i+1) (a+i)
    else iter n (i+1) a in
  iter n 1 0;;

let p21 () =
  let rec iter n i a =
    if n = i then a
    else
      let j = sigma i in
      let k = sigma j in
      if i <> j && i = k then iter n (i+1) (a+i)
      else iter n (i+1) a in
  iter 10000 1 0;;

let factlist n =
  let product = ref 1
  and result = ref [] in
  for i = 1 to n do
    product := !product * i;
    result := !product :: !result
  done;
  !result;;

let radix n l =
  let rec iter n l a =
    match l with
    | [] -> a
    | h :: t -> iter (n mod h) t (n / h :: a) in
  iter n l [];;

let p39 () =
  let max = ref 0 and num = ref 0 in
  for i = 1 to 1000 do
    let count = ref 0 in
    triple_with_sum i (fun _ _ _ -> incr count);
    if !count > !max then begin
      max := !count;
      num := i
    end
  done;
  !num;;

let count_array f a =
  let count = ref 0 in
  for i = 0 to Array.length a - 1 do
    if f a.(i) then incr count
  done;
  !count;;

let p53 () =
  (* Pascal's triangle *)
  let next a =
    let l = Array.length a in
    let b = Array.make (l + 1) 0 in
    b.(0) <- 1;
    b.(l) <- 1;
    for i = 1 to l - 1 do
      if a.(i - 1) < 0 || a.(i) < 0 then b.(i) <- -1
      else
        let c = a.(i - 1) + a.(i) in
        if c > 1_000_000 then b.(i) <- -1
        else b.(i) <- c
    done;
    b in
  let count = ref 0 in
  let a = ref [|1|] in
  for i = 1 to 100 do
    a := next !a;
    count := !count + count_array (fun n -> n < 0) !a
  done;
  !count;;

let p56 () =
  let big = big_int_of_int in
  let max = ref 0 in
  for a = 1 to 100 do
    let power = ref (big 1) in
    for b = 1 to 100 do
      power := mult_big_int !power (big a);
      let sum = digit_sum_big_int !power in
      if sum > !max then max := sum
    done
  done;
  !max;;

let digit_count_big_int n =
  String.length (string_of_big_int n);;

let p57 () =
  let count = ref 0 in
  let rec iter i a b =
    if i = 1000 then ()
    else begin
      let dc = digit_count_big_int in
      if dc a < dc b then incr count;
      let c = add_big_int a b in
      let d = add_big_int a c in
      iter (i + 1) c d
    end in
  let big = big_int_of_int in
  iter 1 (big 2) (big 3);
  !count;;