Problem 8: Find the greatest product of five consecutive digits in the 1000-digit number.

First we get our 1000-digit number into a string suitable for digit traversal.  F# has multi-line strings and the backslash character may be used at the end of each line to prevent newline characters from being inserted.

let digits1000 = "73167176531330624919225119674426574742355349194934\
96983520312774506326239578318016984801869478851843\
85861560789112949495459501737958331952853208805511\
12540698747158523863050715693290963295227443043557\
66896648950445244523161731856403098711121722383113\
62229893423380308135336276614282806444486645238749\
30358907296290491560440772390713810515859307960866\
70172427121883998797908792274921901699720888093776\
65727333001053367881220235421809751254540594752243\
52584907711670556013604839586446706324415722155397\
53697817977846174064955149290862569321978468622482\
83972241375657056057490261407972968652414535100474\
82166370484403199890008895243450658541227588666881\
16427171479924442928230863465674813919123162824586\
17866458359124566529476545682848912883142607690042\
24219022671055626321111109370544217506941658960408\
07198403850962455444362981230987879927244284909188\
84580156166097919133875499200524063689912560717606\
05886116467109405077541002256983155200055935729725\
71636269561882670428252483600823257530420752963450"

While the algorithm required for solving this problem is straight forward, it gives us a nice opportunity to compare an iterative approach (a) with a pure functional approach (b).  Note: make sure to convert each char to a string before converting to an int!

let problem8a =
    let mutable max = 0
    for i in 0..(digits1000.Length-5) do
        let mutable next = 1
        for j in 0..4 do
            next <- next * (digits1000.[i+j] |> string |> int)
        if next > max then max <- next
    max
       
let problem8b =
    {0..digits1000.Length-5}
    |> Seq.map
        (fun i -> 
             {0..4} 
             |> Seq.map (fun j -> digits1000.[i+j] |> string |> int) 
             |> Seq.fold (*) 1)
    |> Seq.max

I personally prefer the descriptiveness of (b) and it’s performance is on par with (a) .

Problem 7: What is the 10001st prime number?

I think I’m getting the hang of this!  Some notable optimizations: isPrime only needs to check the divisibility of n by numbers 2..sqrt(n), and nthPrime only needs to check odd numbers for primality by incrementing i by steps of 2 starting at 1.

let problem7a =
    let isPrime n =
        let nsqrt = n |> float |> sqrt |> int
        let rec isPrime i =
            if i > nsqrt then true
            elif n % i = 0 then false
            else isPrime (i+1)
        isPrime 2
        
    let nthPrime n = 
        let rec nthPrime i p count =
            if count = n then p
            elif i |> isPrime then nthPrime (i+2) i (count+1)
            else nthPrime (i+2) p count
        nthPrime 1 1 0
        
    nthPrime 10001

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

This one is simple.

let problem6a =
    let range = {1..100}
    let sumOfSquares = range |> Seq.sumBy (fun x -> x * x)
    let sumSquared = pown (range |> Seq.sum) 2
    sumSquared - sumOfSquares

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

This one was pretty easy.  We only need to test i against 11 to 20 since the numbers in that range are themselves divisible by those in 1 to 10.  Also, a lower bound for i is the product of all primes in 1 to 20.

let problem5a =
    let rec find i = 
        if {11..20} |> Seq.forall (fun d -> i % d = 0) then i
        else find (i + 1)
    find (2*3*5*7*11*13*17*19)

Problem 4: Find the largest palidromic number made from the product of two 3-digit numbers.

First we implement a function for determining whether a number is palindromic.  We use an efficient tail recursive algorithm comparing the string converted number by character indices working from either end of the string until we reach the middle.

let isPalindrome n =
    let rec isPalindrome (nstr:string) i j =
        if i > j then true 
        elif  nstr.[i] <> nstr.[j] then false
        else isPalindrome nstr (i+1) (j-1)
    let nstr = n |> string
    isPalindrome nstr 0 (nstr.Length - 1)

Now we just need to enumerate all products made from two 3-digit (100 through 999) numbers, taking the max of those which are palindromic.  Solution (a) uses an imperative approach justifiable in nested loop scenarios while (b) and (c) use sequence expressions and typical function applications.

//fastest, reasonable use of iterative loop + mutable
let problem4a =        
    let mutable max = 0
    for i in 100..999 do
        for j in 100..999 do
            let p = i * j
            if p > max && p |> isPalindrome then max <- p    
    max

//notably slower since has to process isPalindrome for every possibility
let problem4b =
    seq { for i in 100..999 do for j in 100..999 do yield i * j }
    |> Seq.filter isPalindrome
    |> Seq.max

//still lower than 4a
let problem4c =
    seq { for i in 100..999 do for j in 100..999 do yield i * j }
    |> Seq.fold (fun acc i -> if i > acc && i |> isPalindrome then i else acc) 0

While (b) is the clearest, I like solution (a) the best since it’s clear enough and notably faster than either (b) or (c).

Problem 3: What is the largest prime factor of the number 600851475143?

This one required a flash of inspiration.  We recursively build a list of prime factors by finding the first even divisor j of n, necessarily prime, and then repeating with n/j until we reach n = 1.  It works out that the head of the list is the largest prime factor.

let problem3a =
    let factorize n =
        let rec factorize n j list = 
            if n = 1I then list
            elif n % j = 0I then factorize (n/j) j (j::list)
            else factorize n (j + 1I) (list)
        factorize n 2I []
    600851475143I |> factorize |> List.head

Now, we only need the largest prime factor so this algorithm can be specialized.

let problem3b =
    let rec largestFactor n j largest = 
        if n = 1I then largest
        elif n % j = 0I then largestFactor (n/j) j j
        else largestFactor n (j + 1I) largest
    largestFactor 600851475143I 2I 1I

Problem 2: Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million.

First we implement a function for computing terms of the Fibonacci sequence.

let rec fib n = if (n = 1 || n = 0) then 1 else fib(n-1) + fib(n-2)

We pipe that into a sequence generator, taking all even terms not exceeding four million, and then sum them.

let problem2a =
    fib
    |> Seq.initInfinite
    |> Seq.takeWhile (fun i -> i <= 4000000) 
    |> Seq.filter (fun i -> i % 2 = 0)
    |> Seq.sum

Problem 1: Add all the natural numbers below one thousand that are multiples of 3 or 5.

Solutions (a)-(c) take the same approach but use different Seq function applications. Every integer from 1 to 999 is tested.

let problem1a =
    {1..999}
    |> Seq.filter (fun i -> i % 3 = 0 || i % 5 = 0)
    |> Seq.sum

let problem1b =
    {1..999}
    |> Seq.fold (fun acc i -> if i % 3 = 0 || i % 5 = 0 then acc + i else acc) 0
    
let problem1c =    
    {1..999}
    |> Seq.sumBy (fun i -> if i % 3 = 0 || i % 5 = 0 then i else 0)

Solution (d) uses inclusion/exclusion instead of an exhaustive search.

let problem1d = 
    let a = Seq.append {0..3..999} {0..5..999} |> Seq.sum
    let b = {0..15..999} |> Seq.sum
    a - b    

I like solution (a) the best since it's the clearest.

The beginning

Back in 2008 I happened upon Expert F# while browsing my local book store.  Having a background in mathematics, I was enticed by the Introduction which pitched F# as a programming language close in expression to what mathematicians are accustomed.  I purchased the book and read it in large part while also following the language on the web.  In this first pass I mostly absorbed the concepts of functional programming but didn't practice much with the language itself.  However, in the intervening years I've been applying a lot of the functional concepts I learned to my day work in C#.  Now, with the release of F# version 2.0, I've found renewed interest and have determined to become experienced with the language itself.  The mathematical nature of the problems in Project Euler make it a particularly well-suited set of challenges for becoming familiar with F#.  While it's been done, here I will document my journey.