Skip to content

Project Euler Problem 88

November 4, 2012

After a quite long silence I’m back with F# solution to one of the relatively challenging (based on the number of people that solved it up to the date) Project Euler problems – Problem 88.

Two things are needed to be realized if approaching the solution from combinatorial search standpoint:

  1. Every number can be converted to a product-sum by the following simple operation – if a number n is represented by a set of f factors we can convert it to a product-sum by adding to f factors (n – sum(factors)) of 1s that increase sum part while keeping product part constant. The result set would be a product-sum (not necessarily minimal) of the set of size f + n – sum(factors).
  2. For pretty obvious reasons the minimal product-sum for some k is between k and 2k.

So, if we manage to factorize all numbers between 2 and 24000 this would give us an answer. However, we can approach the task from the opposite consideration. If we manage building all combinations of factors yielding product-sums for different k in the above range and select minimum for each particular k, then after adding together all distinct minimums we should arrive to the same result.

What would help us assessing the latter approach is finding few boundary conditions. First, the maximum factorization of two factors yielding result closest to 24000 is 154*155. Second, what would be the maximal number of factors yielding the same? Taking the minimal factor of 2 it is easy to find that this length is 14.

Now, equipped with all these consideration we can lay out the algorithm for finding the solution. We can build a factors generator yielding us all possible sets of factors limited from up by set power of 14 and the product of 24000. This is what the pair of functions prodSums and moveNext in the code below does: it first builds all lists of two factors from [2;2] to [155;154], then all lists of three factors [2;2;2] to [30;28;28], etc till the final list [2;2;2;2;2;2;2;2;2;2;2;2;2;2]. Using this sequence of factor lists prodSums we iterate thru it making a product-sum of each member and collecting correspondent minimums in array prodSumMins. Finally, we take a sum of each distinct number among all product-sum minimums for 2..12000, which gives us the answer.

let K = 12000
let K2 = K*2

module List =
    let mul xs =
        xs |> List.reduce (fun a x -> a * x)

let rec moveNext = function
    | h::t as x when x.Length = 14 -> if (h + 1) * (List.mul t) <= K2 then
                                        (h + 1) :: t
                                      else moveNext t
    | [] -> []
    | h::t -> let mutable candidate = []
              for i in 1 .. (14 - t.Length) do
                  candidate <- (h + 1)::candidate
              candidate <- candidate @ t
              if (List.mul candidate) <= K2 then
                  candidate
              else moveNext t

let prodSums = [2;2;1;1;1;1;1;1;1;1;1;1;1;1]
               |> Seq.unfold (fun state ->
                  if state = [] then None
                  else Some(state, moveNext(state)))
               |> Seq.map (List.filter ((<>) 1))

let prodSumMins = Array.init (K + 1) ((*) 2)
prodSumMins.[1] <- 0

let factorsProductSum xs =
    let sum, prod = List.sum xs, List.mul xs
    (xs.Length + prod - sum, prod)

let updateMins = function
    size,prodSum -> if size <= K && prodSum < prodSumMins.[size]  then
                        prodSumMins.[size] <- prodSum

let problem088() =
    prodSums |> Seq.iter (factorsProductSum >> updateMins)
    prodSumMins |> set |> Set.toArray |> Array.sum
Advertisements

From → Project Euler

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: