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 allFactor

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

StackExchange Code Review Q#116134, answer score: 3