Solution to Project Euler problem 5 (LCM of 1 to 20)

I'm an experienced C# developer trying to teach myself F#. I spent a day or 3 reading throught the F# wikibook trying to get to know the syntax and F# fundamentals.

As an exercise I'm trying to go through the Project Euler problems to get a better feeling of the syntax and working with the language.

I've just solved problem 5 (finding the least common multiple of 1, 2, 3, …, 20). But I'm not so happy about the hoops I had to jump through to get a data structure that represents my solution. I've used this blogpost to get to the algorithm for solving the problem.

I was wondering if anyone could give me some pointers as to how this code could be improved? My guess is that the inherent immutability of F# values is causing me to have to perform a lot of steps to get the exact data I want...

This is my code:

let main argv =
//calculates the prime factors of a number
let findPrimeFactors x =
let primes = [|2I;3I;5I;7I;11I;13I;17I;19I|]
let rec loop acc counter = function
| x when x = 1I -> failwith "A PRIME IS BY DEFINITION GREATER THAN 1"
| x when primes |> Array.contains x -> x :: acc
| x when counter = primes.Length -> failwith "MY LIST OF KNOWN PRIMES IS NOT BIG ENOUGH"
| x when x%primes.[counter]=0I-> loop (primes.[counter]::acc) (counter) (x/primes.[counter])
| x -> loop acc (counter + 1) x

let primeFactor = loop [] 0 x |> List.rev
primeFactor

//calculates the prime factors for each of the numbers between 2 and n
//then, for each of the prime factorizations it tries to find the highest power for each occurring prime factor
let findPrimeFactorsPowers n =
//builds a map of all the prime factor powers for all prime factorizations
let rec addCounterFactorPowers factorPowers = function
| counter when counter = n -> factorPowers
| (counter : int) -> addCounterFactorPowers ((findPrimeFactors (counter|>bigint) |> List.countBy (fun x-> x)) @ factorPowers) (counter + 1)
let allFactorPowers = addCounterFactorPowers [] 2
//group all the powers per prime factor
let groupedFactorPowers = allFactorPowers |> List.groupBy (fun (factor, power) -> factor)
//get the highest power per prime factor
let maxFactorPowers = groupedFactorPowers |> List.map (fun (key, powers) -> (key, powers |> List.map (fun (factor, power) -> power) |> List.max))

//return the result
maxFactorPowers

let n = 20;
let primeFactorSet = findPrimeFactorsPowers n
printfn "%A" primeFactorSet

let smallestNumberDivisableByAllNumbersBelown =  (primeFactorSet |> List.fold (fun state (factor, power) -> state * pown factor power) 1I)
printfn "Result %A" smallestNumberDivisableByAllNumbersBelown

0 // return an integer exit code

• Please describe the purpose of your code in the title of your question (rather than what you want to be done with it in a review) :-) In particular, as this is an answer to a Project Euler question, you may want to mention that in the title of your question with the number of the problem - that'll stop it being spoiled for other users of Project Euler. – Dan Pantry Jan 7 '16 at 16:34

Let's start with the loop inside findPrimeFactors. You have the right idea, but it's complicated because you're flattening two loops into one: looping over the primes, and looping over the factors for your target number.

So let's do those one at a time. First, let's create a function that finds the next prime factor:

let rec findNextFactor candidates n =
match candidates with
| x::xs when n%x=0I -> x
| x::xs -> findNextFactor xs n
| _ -> failwith "No factor found"


The first line matches when a factor is found, the second when no factor is found, and the third when the collection is empty. Note how matching on the collection makes it very easy to recursively loop through it by matching against x:xs. This helps avoid your issue of looping by index.

Now that we know how to find the next prime factor, it's easy to find all of them:

let rec loop acc n =
match findNextFactor primes n with
| n -> n:acc
| p -> findPrimeFactors p:acc n/p


We're not passing primes in here as we're not iterating it here. The primes referred to is the outer one which always contains all the primes up to 20. By splitting out the loop, we only need to deal with these two simple cases.

Just glue those together and you get your findPrimeFactors implementation.

For findPrimeFactorsPowers, you're again increasing the complexity by completely changing your data type, from a list of factors, to a map of factors to the count of those factors. This isn't actually that hard. For a single number n it might look like:

let findPrimeFactorsPowers n =
findPrimeFactors n
|> Seq.groupBy i -> i
|> Seq.map i -> (i.Key, i.Count)


I'm honestly not quite sure what your version is doing, so I can't compare very closely.

But actually, there's something even simpler we can do. Really all we want to do is merge two lists in a special way: for each value, the number of times that value appears in the merged list should equal the maximum number of times it appears in each individual list.

By taking advantage of the fact that our lists are sorted, we can do that very easily:

let rec merge a b acc =
match a,b with
| x::xs, y::ys when x = y -> merge xs ys (x::acc)
| x::xs, y::ys when x < y -> merge xs b (x::acc)
| x::xs, y::ys -> merge a ys (y::acc)
| _, [] -> List.append (List.rev acc) a
| [], _ -> List.append (List.rev acc) b


We loop over the lists, take the head of each one. If they're equal, remove both heads and add it to the accumulator, otherwise take just the lowest and add that. Finally the last lines let us terminate once a list is empty.

This is the last piece we need. Now we just need to get the prime factor lists for each number under 20, and merge each one in turn into an empty list. Finally find the product of the numbers in the resultant list, and you have your answer.

For more general comments, there isn't much I can find to fault. There's a couple of times you declare a variable, then only use it once in the next line. Not doing that means you can get rid of the cumbersome name smallestNumberDivisableByAllNumbersBelown.

Also, you should probably trim out some unnecessary comments. If you're just learning F#, the idea that the last expression of a function is what gets returned might cause enough cognitive friction for you that you want to leave yourself a comment, but those shouldn't be in part of a finished piece of code.

Generally, though, stylistically the code is good, including both naming and organization.

• (Just as a warning, my F# is a bit rusty and I don't have a compiler handy, so apologies in advance if any syntax is wrong. Feel free to edit in corrections. Most of this deals with algorithms rather than syntax, so hopefully it's not important) – Ben Aaronson Jan 7 '16 at 18:13
• Tnx Ben! That was exactly the kind of advice I was looking for. Splitting up the loops decreases the complexity indeed. And I just KNEW, there HAD to be a simpler way of merging all those lists, but with all the new stuff I had learned my brain synapses were firing in all different directions. I tweaked your merge function a bit to maintain the sorting of the lists (also edited your post). My code looks & feels much cleaner now. I've gained better insights, tnx again! – Stif Jan 8 '16 at 9:37
• @Stif Glad it helped! I partially apply your edit. I didn't really understand the purpose of the whole candidatesLeft thing, so I didn't include that. I think the slightly simpler list gluing in merge should work too. – Ben Aaronson Jan 8 '16 at 13:12
• The candidatesLeft was just a small optimization to not loop over all the primes every time. Once a prime has been factored out, you know it will never be a candidate again. But it's not that important here since n will never get very big in this example. – Stif Jan 8 '16 at 13:43
• @Stif Oh okay, I do understand now. You return the candidates with all the primes greater than or equal to the one you just found as a factor. That makes sense. It's a nice extra optimization, but I won't include it in my answer because it's really your work rather than mine. – Ben Aaronson Jan 8 '16 at 15:05