Project Euler problem six is another easy one.

The sum of the squares of the first ten natural numbers is,

1^{2}+ 2^{2}+ ... + 10^{2}= 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + ... + 10)^{2}= 55^{2}= 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

The solution to this problem boils down to a few folding operations and a map. The one-liner is below.

Pretty nasty, eh? Quite a bit of code duplication can be removed. Since they're identical, let's generalize all of the folds first by extracting them to a sum function.

sum [1..100] * sum [1..100] - sum (List.map (fun x -> x * x) [1..100])

That already looks a lot better.

Next, we can generalize the multiplication operations. Each time multiplication occurs in the solution above, it's simply squaring a value. So, we can extract those operations into a square function.

square (sum [1..100]) - sum (List.map (fun x -> square x) [1..100])

We can simplify that even further. Because the anonymous function passed to List.map just applies its argument to the square function, we can pass square directly.

Next, let's generalize the call to List.map that produces a list of squares by moving it to a new function, squares.

square (sum [1..100]) - sum (squares [1..100])

At this point, we have a perfectly acceptable solution. It states the problem almost like natural English: "The square of the sum of 1 to 100 minus the sum of the squares of 1 to 100." So, why are there a few more inches left in this article? Well, I'd like to take this a step further.

Thinking more abstractly, what does our solution do? It computes the difference of two *calculations* that are based on the same list. We can extract this general process to a new function like so:

difference (fun l -> square (sum l)) (fun l -> sum (squares l)) [1..100]

It turns out that we can simplify these anonymous functions in the same way that we did with the square function earlier. However, because there are two functions involved in each calculation, we must compose the functions together. In F#, there are two operators used to perform function composition: the >> operator, which applies the functions from left to right, and the << operator, which applies the functions from right to left. Obviously, we need the latter.

After using the forward pipe operator to move the list to the front, we're finished.

"Take the numbers 1 to 100 and find the difference of the square of the sum and the sum of the squares."

Function composition is beautiful.

A few days ago, I presented a solution for Project Euler problem four that I didn't really like. The challenge of problem four is to write a function that determines whether a number is a palindrome, that is, whether it reads the same backward as forward. When presented with that challenge, I took an approach that I feel is a bit of a cop-out: converting the number to a string, reversing the string and comparing the result. This felt somehow wrong because I'm not really solving the problem in a mathematical way. So, I'm declaring a mulligan. Below is a new function which properly performs the *math* necessary to reverse a base-10 number.

let rec loop x res =

if x = 0 then res

else loop (x/10) (res*10 + (x%10))

loop n 0

let isPalindrome n =

n = reverse n

Our original list comprehension below still works properly with the new isPalindrome function.

for y in 100..999

when isPalindrome(x*y) -> x*y ] |> toLargest

This solution is twice as fast as the original string-based solution. In addition, I'd argue that the tail-recursive loop is at least four times as beautiful.

At first glance, Project Euler problem five looks like a walk in the park:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

Sounds easy! The most straightforward solution is to take the sequence of all natural numbers, filter those that are evenly divisible by 1 through 20, and pop off the first element of the sequence (the head). Something like the code below would do the trick.

|> Seq.filter (fun n ->

[1L .. 20L] |> List.for_all (fun d -> n % d = 0L))

|> Seq.hd

Unfortunately, that solution, while direct, falls far outside of Project Euler's "one-minute rule." It eventually calculates the correct answer but takes as much as 10 minutes on my machine!

OK, let's take a step back. What exactly is the problem asking us to find? Stating it differently, "What is the least common multiple of all of the numbers from 1 to 20?"

The least common multiple (LCM) of two numbers is the smallest number that is evenly divisible by each. Still not familiar? Think about how fractions are added. The first step in adding fractions is to find the least common denominator, which is simply the LCM of the denominators. For example, given the fractions 1/8 and 1/12, we would find the LCM of 8 and 12. Then, the fractions would be rewritten with the LCM (24) as their denominators. Once this is done, we can easily add the fractions 3/24 and 2/24 to get the answer, 5/24.

So, how should we go about calculating the LCM of two numbers? It turns out that there are many well-known possibilities. One of the most popular methods involves finding the prime factors of both numbers. It goes something like this:

160 = 2

^{5}* 5

^{1}

90 = 2

^{1}* 3

^{2}* 5

^{1}

The least common multiple can be computed by multiplying the highest power of each unique factor.

lcm(160,90) = 2

^{5}* 3

^{2}* 5

^{1}= 1440.

Many people have chosen this method when working through problem five, and I was tempted to take this road as well because it would allow us to reuse our primeFactors function from problem three. However, the code would be fairly complex.

let incrCount m i =

match Map.tryfind i m with

| Some(c) -> Map.add i (c+1) m

| None -> Map.add i 1 m

lst |> List.fold_left incrCount Map.empty |> Map.to_list

let lcm x y =

let rec updateMap m t =

let i,c = t

match Map.tryfind i m with

| Some(v) when v < c -> Map.add i c m

| None -> Map.add i c m

| _ -> m

let factors =

[x; y]

|> List.map primeFactors

|> List.map countItems

|> List.fold_left (List.fold_left updateMap) Map.empty

Map.fold (fun i c res -> res * int64 (float i ** float c)) factors 1L

Personally, I feel a sense of accomplishment at writing all of those folds—particularly the double-fold near the end, that's really cool. However, it's pretty far below my standard for code beauty. If you recall, I'm trying to present the most *beautiful* solution that I can. So, I'm rejecting this solution, even though it's efficient enough to meet Project Euler's requirements. Admittedly, there's a certain beauty in the list transformations, but there's a **much** better method.

The least common multiple of two numbers can be calculated quite simply using their greatest common divisor (GCD), or the largest number that divides evenly into both numbers. The GCD can be computed easily with the Euclidean algorithm. Here's how it works:

- Start with 2 natural numbers, x and y
- If y is equal to zero, the answer is x.
- If not, set x to the value of y, and y to the remainder of dividing x by y.
- Go back to step 2.

For the more visual among you, a flowchart of the Euclidean algorithm is pictured below.

Once we have the GCD, calculating the LCM is easy. Simply divide x by the GCD of x and y, and multiply the result by y. These two algorithms can be implemented quite beautifully in F#.

if y = 0 then x

else gcd y (x%y)

let lcm x y =

if x = 0 or y = 0 then 0

else (x / (gcd x y)) * y

However, the F# libraries already supply a function to calculate the GCD of two numbers. The greatest common denominator also goes by another name, highest common factor (HCF), and there is an HCF function in the Microsoft.FSharp.Math.BigInt module. It's a simple matter to rewrite lcm using BigInt.hcf.

let lcm x y =

if x = 0I or y = 0I then 0I

else (x / (BigInt.hcf x y)) * y

With lcm in place, would you believe that our solution looks like this?

F# can produce truly beautiful code indeed!

Yet Another Project Euler Series (YAPES) continues with problem four:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

The most straightforward way to determine if a number is palindromic is to convert it to a string and compare that string with its reverse. Sound easy? It is!

One minor snag is the lack of a library function in F# for reversing strings, but that's easily defined like so:

let rev (s : string) = new string(s.ToCharArray() |> Array.rev)

With String.rev in place, writing an isPalindrome function is trivial.

let text = Int32.to_string n

text = String.rev text

Using a list comprehension, we can generate all of the palindromes that are products of 3-digit numbers. Once we have this list, producing the result is as simple as passing it to the toLargest function that we defined for Problem Three.

for y in 100..999

when isPalindrome (x*y) -> x*y ] |> toLargest

Short and sweet—my favorite!

Project Euler problem three is first of *many* to deal with prime numbers.

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143?

Eventually, we'll need a prime number generator to solve some of the more advanced problems, but this problem can be solved efficiently without one. The number in question is small enough (just 12 digits) that the divide-and-conquer method that many of us learned in elementary school will suffice.

Consider how we might use this process to find the prime factors of 140.

140 | Is 140 evenly divisible by 2? Yes! Remember 2 and divide 140 by 2. |

2 * 70 | Is 70 evenly divisible by 2? Yes! Remember 2 and divide 70 by 2. |

2 * 2 * 35 | Is 35 evenly divisible by 2? No, how about 3? No. 4? Nope. 5? Yes! Remember 5 and divide 35 by 5. |

2 * 2 * 5 * 7 | And we're done! |

This method isn't rocket science, but it gets the job done. In fact, it's pretty fast for reasonably small numbers. After all, we're not trying to find the factors of RSA-200.

The basic algorithm is pictured as a flowchart below.

The following F# function implements our algorithm.

let inline isFactor n d = n % d = 0L

let rec nextFactor n d =

let x = if d = 2L then 3L else d+2L

if isFactor n x then x else nextFactor n x

let rec findFactors n d acc =

if isFactor n d then

findFactors (n/d) d (d::acc)

elif n > d then

findFactors n (nextFactor n d) acc

else

acc

findFactors n 2L [] |> List.rev

To the uninitiated, that function might look pretty complex. In reality, it's extremely simple, but three other functions are nested inside of it. Let's look at each nested function in turn.

There's nothing tricky about isFactor. It simply abstracts the modulo operation that determines whether n is evenly divisible by d.

let x = if d = 2L then 3L else d+2L

if isFactor n x then x else nextFactor n x

nextFactor recursively determines the next value of d to be used in the algorithm. There is a small optimization here: nextFactor only produces odd numbers. Since 2 is the only even prime, why bother checking any other evens?

if isFactor n d then

findFactors (n/d) d (d::acc)

elif n > d then

findFactors n (nextFactor n d) acc

else

acc

The meat of the algorithm is handled by findFactors. Any factors found are cons'd up with the accumulator variable, acc. Note that both findFactors and nextFactor are written tail-recursively, so they can be optimized by the compiler to conserve stack space.

The *real* body of primeFactors kicks off the recursion:

The result of findFactors is passed to List.rev to return the prime factors in a more logical order (smallest to largest).

A simple test in the F# Interactive Environment shows that primeFactors works as expected.

val it : int64 list = [2L; 2L; 5L; 7L]

Almost done.

Project Euler Problem Three asks, "What is the largest prime factor of the number 600851475143?" That's just a matter of folding the list of prime factors with the max function (from the F# libraries) to get the answer.

We can generalize the folding logic above with a new function...

...And now we can write the following solution.

That's just lovely.

**NeRd Note**