euler.ml

(* Project Euler in OCaml
 * John Evans <john@jpevans.com>
 *)

(* Euler #1
 * Answer: 233168
 *
 * If we list all the natural numbers below 10 that are multiples of 3 or 5,
 * we get 3, 5, 6 and 9. The sum of these multiples is 23.
 *
 * Find the sum of all the multiples of 3 or 5 below 1000.
 *)

let rec range a b =
    if a > b then []
    else a :: range (a+1) b
    ;;

let sum_list =
    List.fold_left ( + ) 0
    ;;

let divisible_by_3_or_5 n = 
    (n mod 3 == 0) || (n mod 5 == 0)
    ;;

let euler1 = fun() ->
    sum_list (List.filter divisible_by_3_or_5 (range 3 999))
    ;;


(* Euler #2
 * Answer: 4613732
 *
 * Each new term in the Fibonacci sequence is generated by adding the previous
 * two terms. By starting with 1 and 2, the first 10 terms will be:
 *
 * 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
 *
 * Find the sum of all the even-valued terms in the sequence which do not
 * exceed four million.
 *)

let rec e2search a b acc =
    if b > 4000000 then acc
    else e2search b (a + b) (if b mod 2 == 0 then acc + b else acc)
    ;;

let euler2 = fun() ->
    e2search 1 2 0
    ;;


(* Euler #3:
 * Answer: 6857 [ NOT WORKING YET ]
 *
 * The prime factors of 13195 are 5, 7, 13 and 29.
 *
 * What is the largest prime factor of the number 600851475143 ?
 *)

(* let rec largest_factor_of_n_below_n_acc n x =
    if n mod x == 0 then x
    else largest_factor_of_n_below_n_acc n (x - 1)
    ;;

let largest_factor_of_n_below_n n =
    largest_factor_of_n_below_n_acc n (n - 1)
    ;;

let is_prime n = 
    largest_factor_of_n_below_n n == 1
    ;;

let rec e3search f t =
    if f mod t == 0 && is_prime f then f
    else e3search (f-1) t
    ;;

let euler3 =
    let target = 600851475143
    let max_factor = ceil (sqrt target)
    e3search max_factor target
    ;; *)


(* Problem #4
 * Answer: 906609
 *
 * A palindromic number reads the same both ways. The largest
 * palindrome made from the product of two 2-digit numbers is 9009 =
 * 91 99.
 *
 * Find the largest palindrome made from the product of two 3-digit
 * numbers.
 *)

(* let rec list_of_string s =
    match s with
        "" -> []
        | _ -> (String.get s 0)::list_of_string (String.sub s 1 ((String.length s) - 1))
    ;;

let string_from_char c =
    String.make 1 c
    ;;

let rec string_of_list xs =
    match xs with
        [] -> ""
        | _ -> (string_from_char (List.hd xs))::string_of_list (List.tail xs)
    ;;

(* Really? *)
let rec rev s =
    match s with
        [] -> s
        | x::xs -> (rev xs)::[x;]
    s;;

let rec rev (l, a) = match l with
    [] -> a
    | (x::xs) -> rev (xs, (x::a))
    let rev l = rev (l, [])
    ;;

let is_palindromic_number n =
    (string_of_int n) == rev (string_of_int n);;
    (* let s = string_of_int n;
    s == rev s
    ;; *)

let e4search i j acc =
    if j > 999 then acc
    else
        if i > 999 then e4search 1 (j + 1) acc
        else
            let p = i * j
            e4search (i + 1) j (if is_palindromic_number p then acc + p else acc)
    ;;

let euler4 =
    e4search 1 1 0
    ;; *)


let eulers = [|euler1, euler2|];;
let print_euler n =
    print_char '#';
    print_int n;
    print_string ": ";
    let euler = eulers.(n) in
    print_int euler
;;

let main () =
    let num_args = Array.length Sys.argv in
    if num_args > 0 then
       for i = 1 to num_args - 1 do
           print_euler int_of_string Sys.argv.(i)
       done
    else
        for i = 0 to Array.length eulers do
            print_int eulers.(i)
        done
    ;;

(*         if Sys.arg
        let print_all =
        print_int euler1;
        print_char '\n';
        print_int euler2;
        print_char '\n';; *)

main ();;