# Project Euler Problem 88

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:

- 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)**. - 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