euler78-2.fsx

open System.Collections.Generic

let limit = 100000
let divisor = 1000000

let memo = new Dictionary<int,int> ()

let rec partitions = fun (n, m) ->
  if (n >= limit || m >= limit) then 0
  elif (n = 0) then 1
  elif (n = 1 || m = 1) then 1
  elif (n < m) then partitions(n, n)
  elif (memo.ContainsKey(n * limit + m)) then memo.[n * limit + m]
  else
    let result = List.reduce (fun sum x -> (sum + x) % divisor ) [ for i in 1 .. m -> partitions(n - i, i) ]
    memo.Add(n * limit +  m, result)
    result

let rec f = fun n -> if (partitions(n, n) = 0) then n else f(n+1)

let start = fun _ -> printfn "%d" (f 1)

start()

euler78-3.fsx

open System.Collections.Generic
 
let limit = 100000
let divisor = 1000000
 
let memo = new Dictionary<int,int> ()
 
let rec partitions n m =
  if (n >= limit || m >= limit) then 0
  elif (n = 0) then 1
  elif (n = 1 || m = 1) then 1
  elif (n < m) then partitions n n
  elif (memo.ContainsKey(n * limit + m)) then memo.[n * limit + m]
  else
    let result = List.reduce (fun sum x -> (sum + x) % divisor ) [ for i in 1 .. m -> partitions (n - i) i ]
    memo.Add(n * limit +  m, result)
    result
 
let rec f n = if ((partitions n n) = 0) then n else f(n+1)
 
let start = printfn "%d" (f 1)
 
start

euler78.fsx

let memo = [| for i in 1 .. 10 -> [| for i in 1 .. 10 -> -1 |] |]

let rec partitions = fun (n, m) -> 
  printfn "partitions %d, %d" n m
  if (n >= 10 || m >= 10) then 0
  elif (n = 0) then 1
  elif (n = 1 || m = 1) then 1
  elif (n < m) then partitions(n, n)
  elif (memo.[n].[m] <> -1) then memo.[n].[m]
  else
    let result = ([ for i in 1 .. m -> partitions(n - i, i) ] |> List.sum)
    printfn "result = %d" result
    Array.set memo.[n] m result
    result % 7

let rec f = fun n -> if (partitions(n, n) = 0) then n else f(n+1)

let start = fun _ -> printfn "%d" (f 1)

start()

printfn "%A" memo