Source

project-euler / OCaml / Euler023.ml

(******************************************************************************
 **                                                                          **
 **  Project Euler #23                                                       **
 **                                                                          **
 **  Copyright (c) 2010, Taylor Venable.  All rights reserved.               **
 **  Released under the terms of the simplified (2-clause) BSD license.      **
 **                                                                          **
 ******************************************************************************)

include List
include TaylorList
include TaylorNumber
include TaylorMisc
include TaylorArray

open TaylorMisc

module Euler023 : sig
  val is_abundant : int -> bool
  val solution : unit -> int list
  val expressible : (bool array * int list * int * int) -> int -> bool
end = struct
  let sum l = List.fold_left
    (fun a (n, m) ->
      if n == m then a + n else a + n + m)
    1 l
  let build_array l =
    let arr = Array.make 28124 false in
    let rec build_array' ll last =
      match ll with
          [] -> last
        | h::t ->
          begin
            arr.(h) <- true;
            build_array' t h
          end
    in
    let last = build_array' l (-1) in
    (arr, l, List.hd l, last)

  let is_abundant n = sum (TaylorNumber.factors n) > n

  let expressible (arr, l, first, last) n =
    let len = Array.length arr in
    let rec expressible' lit =
      match lit with
          [] -> false
        | h::t ->
          if h > (n / 2) then false
          else if arr.(h) && (n - h) < len && arr.(n - h) then true
          else expressible' t
    in
    expressible' l

  let solution () =
    let a_list = List.filter is_abundant (TaylorList.iota 1 28123) in
    let exp_data = build_array a_list in
    print_string ("Found " ^ string_of_int (List.length a_list) ^ " abundant numbers.\n");
    List.filter (not <<- expressible exp_data) (TaylorList.iota 1 28123)
end;;

let solution = Euler023.solution () in
begin
  print_string ("Found " ^ string_of_int (List.length solution) ^ " solutions.\n");
  print_string ("Solution = " ^ string_of_int (List.fold_left (+) 0 solution) ^ "\n");
end
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.