Project Euler #20

#load "nums.cma";;

open Big_int;;

let rec factorial n =
  if eq_big_int n unit_big_int then
    unit_big_int
  else
    mult_big_int n (factorial (pred_big_int n));;

let int_list_of_string s =
  let len = String.length s in
  let rec chars_of_string s n =
    if n == 0 then
      [int_of_char s.[0] - int_of_char '0']
    else
      (chars_of_string s (n - 1)) @ [(int_of_char s.[n]) - int_of_char '0']
  in
  chars_of_string s (len - 1);;
  
Printf.printf "%d\n" 
    (List.fold_left 
       (+) 
       0 
       (int_list_of_string 
      (string_of_big_int 
         (factorial 
        (big_int_of_int 100)))));;

Project Euler #6

#load "nums.cma"

open Big_int;;

let rec sum_of_squares n = 
  if eq_big_int n unit_big_int then
    unit_big_int
  else
    add_big_int (square_big_int n) (sum_of_squares (pred_big_int n));;

let square_of_sum n =
  let rec sum n =
    if eq_big_int n unit_big_int then
      unit_big_int
    else
      add_big_int n (sum (pred_big_int n))
  in
  square_big_int (sum n);;

let s1 = sum_of_squares (big_int_of_int 100);;
let s2 = square_of_sum (big_int_of_int 100);;

let result = sub_big_int s2 s1;;

Printf.printf "%s\n" (string_of_big_int result);;

Сначала написал с использованием встроенных int, перепутал местами суммы при вычитании, получил отрицательный результат, подумал, что проблема с переполнением int, переписал при помощи Big_int, после чего и обнаружил, что перепутал суммы местами.

Project Euler #4

(* Checks if int is palindrome *)
let is_palindrome n = 
  let str = string_of_int n in
  let len = String.length str in
  let rec check_char s n =
    if n == len - 1 then
      (String.get s n == String.get s 0)
    else
      (String.get s n == String.get s (len - 1 - n)) && (check_char s (n + 1))
  in
  check_char str 0;;

(* check if n is a product of two 3-digit numbers *)
let is_product n = 
  let rec check_numbers i j n =
    let rest = n mod i in
    let modulo = n / i in
    let mod_length = String.length (string_of_int modulo) in
    if i = j then
      false
    else if (rest == 0) && (mod_length == 3) then 
      begin
        Printf.printf "%d %d\n" i modulo;
        true
      end
    else
      check_numbers (i+1) j n
  in
  check_numbers 100 999 n;;

(* looks for palindromes which a products of two 3-digit numbers*)
let rec check_range n m =
  if n == m then
    -1
  else if (is_palindrome n) && (is_product n) then
    n
  else
    check_range (n-1) m;;

Printf.printf "%d\n" (check_range 998001 10000)

Изначально пытался просто переделать двойной цикл с проверкой в рекурсию, в итоге оказалось проще перебрать числа в одной рекурсии.

Project Euler #3

#load "nums.cma"

open Big_int;;

let num = big_int_of_string "600851475143";;

let solution n =
  let rec factorize m p =
    if ge_big_int p m then
      Printf.printf "%s\n" (string_of_big_int m)
    else
      if eq_big_int (mod_big_int m p) zero_big_int then
        factorize (div_big_int m p) (big_int_of_int 2)
      else
        factorize m (succ_big_int p)
  in
  factorize n (big_int_of_int 2);;

solution num;;

Решение вида "а давайте-ка найдем все простые числа до sqrt(N), а потом найдем максимальное, которое разделит N без остатка", что прокатило для C++, в Ocaml оказалось неосуществимо в разумные сроки ;)

Project Euler #2

#load "nums.cma";;
open Big_int;;

let rec fib a b = function
        | 0 -> a
        | 1 -> b
        | n when n > 1 -> fib b (add_big_int a b) (n - 1)
        | _ -> raise (Invalid_argument "");;

let rec fib_range n =
        let fn = fib zero_big_int unit_big_int n in
        if lt_big_int fn (big_int_of_string "4000000") then
                if eq_big_int 
                (mod_big_int fn (big_int_of_int 2)) 
                zero_big_int then
                        fn :: (fib_range (n + 1))
                else
                        zero_big_int :: fib_range (n + 1)
        else
                [];;

Printf.printf "%s\n" (string_of_big_int 
(List.fold_left (add_big_int) zero_big_int (fib_range 0)));;

Генерация списка по причинам детского восторга от fold, в принципе можно было сразу суммировать.

Project Euler #1

let rec range n m = if n > m then [] else n :: range (n + 1) m;;
Printf.printf "%d\n" 
  (List.fold_left (+) 0 (List.map 
     (fun n -> if n mod 3 == 0 or n mod 5 == 0 then n else 0) 
        (range 1 999)))