Author: Emanuel

Home/Articles Posted by Emanuel (Page 2)

Project Euler Problem #8

I’m beginning to learn F# and the best way for me to go about that is to start applying it. There are some interesting computational problems over at Project Euler . This post is the continuation of a series of posts each involving a separate Project Euler problem. This post involves solutions to Project Euler problem #8.

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

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

Compared to some of the previous problems this one seems pretty easy. What I want to do is to transform that number from a string into a sequence of numbers, then into a sequence of 5-digit numbers, and compute the product of each of those and produce the max.

open System
 
let number =
    "73167176531330624919225119674426574742355349194934" +
    "96983520312774506326239578318016984801869478851843" +
    "85861560789112949495459501737958331952853208805511" +
    "12540698747158523863050715693290963295227443043557" +
    "66896648950445244523161731856403098711121722383113" +
    "62229893423380308135336276614282806444486645238749" +
    "30358907296290491560440772390713810515859307960866" +
    "70172427121883998797908792274921901699720888093776" +
    "65727333001053367881220235421809751254540594752243" +
    "52584907711670556013604839586446706324415722155397" +
    "53697817977846174064955149290862569321978468622482" +
    "83972241375657056057490261407972968652414535100474" +
    "82166370484403199890008895243450658541227588666881" +
    "16427171479924442928230863465674813919123162824586" +
    "17866458359124566529476545682848912883142607690042" +
    "24219022671055626321111109370544217506941658960408" +
    "07198403850962455444362981230987879927244284909188" +
    "84580156166097919133875499200524063689912560717606" +
    "05886116467109405077541002256983155200055935729725" +
    "71636269561882670428252483600823257530420752963450"
 
 
let to_digitsSeq (str:string) = 
    str.ToCharArray()
    |> Array.to_seq
    |> Seq.map (fun c -> Convert.ToInt32(c) - Convert.ToInt32('0'))
 
 
let products digits:seq<int> = 
    digits
    |> Seq.windowed 5
    |> Seq.map (Array.reduce (fun i j -> i*j))
 
 
let answer = number |> to_digitsSeq |> products |> Seq.max
 
printfn "Answer: %d" answer

Project Euler Problem #7

I’m beginning to learn F# and the best way for me to go about that is to start applying it. There are some interesting computational problems over at Project Euler . This post is the continuation of a series of posts each involving a separate Project Euler problem. This post involves solutions to Project Euler problem #7.

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

My first naive attempt is to generate a sequence of primes simply by testing each and every number for whether it is prime:

let dividesEvenly dividend divisor = int64(dividend % divisor) = 0L
 
let isPrime x = seq { 2 .. x-1 } |> Seq.exists (dividesEvenly x) |> not
let primes1 = Seq.initInfinite (fun x -> x + 2) |> Seq.filter isPrime
let version1 = Seq.nth (10001-1 (* nth is zero-based *)) primes1
 
printfn "Project Euler Problem #7: What is the 10001st prime number?"
printf "Answer: %d" version1

This code took 8 minutes to generate the answer on my machine. What kind of optimizations can we make?

  1. The isPrime function currently tests the number from 2 up to, but not including, the number being tested against. This can be improved in two ways: 1) it need only test up to the square root of the number being tested, and 2) it only needs to test against the prime numbers.

We first start by memoizing and lazily evaluating the sequence of primes by turning it into a LazyList:

let rec primes2 =
let nextPrime prevPrime =
Seq.initInfinite (add (prevPrime + 1))
|> Seq.filter isPrime1
|> Seq.hd
let rec PrimesStartingFrom prime =
LazyList.consf prime (fun () -> PrimesStartingFrom (nextPrime prime))
LazyList.consf 2 (fun () -> PrimesStartingFrom 3)

The code still takes 8 minutes to return an answer, but now we can reuse the sequence without reincurring the processing cost. Now we transform the isPrime function to use the new primes sequence.

open System
 
let rec isPrime2 x =
let limit = int(Math.Sqrt(float(x)))
primes2 |> LazyList.to_seq |> Seq.takeWhile (fun i -> i <= limit) |> Seq.exists (dividesEvenly x) |> not
 
and primes2 =
let nextPrime prevPrime =
Seq.initInfinite (add (prevPrime + 1))
|> Seq.filter isPrime2
|> Seq.hd
let rec PrimesStartingFrom prime =
LazyList.consf prime (fun () -> PrimesStartingFrom (nextPrime prime))
LazyList.consf 2 (fun () -> PrimesStartingFrom 3)
 
let answer2 = lazy (primes2 |> LazyList.drop 10000 |> LazyList.hd)

This version only takes about 200 milliseconds to generate the answer on my machine! That’s a 2400x improvement! This is pretty good, but I’d like to try a different algorithm to see if it’s any better: the well known Sieve of Eratosthenes.

let sieveOfEratosthenes n =
    let prime = true
    let composite = false
    let (candidates:bool array) = Array.create (int(n+1)) prime
    candidates.[0] <- composite
    candidates.[1] <- composite
    for i in { 2..n } do
        if candidates.[int(i)] = prime then
            for j in { i..i..n } do 
                // flag all multiples of i as composite since candidate i is prime
                candidates.[int(j)] <- composite
    candidates

This will produce an array of boolean values where the value indicates whether the corresponding index is prime. This can be sped up by recognizing that all of the multiples of i, from 2*i to i2 have already been marked as composite, so we can start marking composites from i2 instead of i.

let sieveOfEratosthenes n =
    let prime = true
    let composite = false
    let (candidates:bool array) = Array.create (int(n+1)) prime
    candidates.[0] <- composite
    candidates.[1] <- composite
    for i in { 2..n } do
        if candidates.[int(i)] = prime && (new bigint(i))*(new bigint(i)) <= (new bigint(n)) (* avoid 32-bit integer overflow *) then
            for j in { i*i..i..n } do 
                // flag all multiples of i as composite since candidate i is prime
                candidates.[int(j)] <- composite
    candidates

That adjustment reduces the running time by about 25%. For low values of primes like the one in Project Euler problem #7, my memoized version is faster than the Sieve of Eratosthenes, but comparing the algorithms when trying to find the millionth prime and the Sieve wins.

The only problem with the Sieve of Eratosthenes is that is produces all of the primes up to a certain number – which is difficult when you don’t know how high you may go. Luckily the primes follow a well-known distribution, and the upper bound on how big the nth prime will be is given by the equation n * ln n + n * ln ln n.

let upperBound n:int =
    let f = float(n)
    let ln x = Math.Log x
    f*(ln f) + f*(ln (ln f)) |> int

Putting it all together we get:

open Microsoft.FSharp.Math
 
let sieveOfEratosthenes n =
    let prime = true
    let composite = false
    let (candidates:bool array) = Array.create (int(n+1)) prime
    candidates.[0] <- composite
    candidates.[1] <- composite
    for i in { 2..n } do
        if candidates.[int(i)] = prime && (new bigint(i))*(new bigint(i)) <= (new bigint(n)) then
            for j in { i*i..i..n } do 
                // flag all multiples of i as composite since candidate i is prime
                candidates.[int(j)] <- composite
    candidates
 
let upperBound n:int =
    let f = float(n)
    let ln x = Math.Log x
    f*(ln f) + f*(ln (ln f)) |> int
 
let sieve2Seq (sieve:bool array) = seq {
    for i = 2 to sieve.Length do
        if sieve.[i] then yield i }
 
let nthPrime3 n = 
    sieveOfEratosthenes (upperBound n) 
    |> sieve2Seq
    |> Seq.nth (int(n - 1 (* zero-based *)))
 
let answer3 = lazy (nthPrime3 10001)

Project Euler Problem #6

I’m beginning to learn F# and the best way for me to go about that is to start applying it. There are some interesting computational problems over at Project Euler . This post is the continuation of a series of posts each involving a separate Project Euler problem. This post involves solutions to Project Euler problem #6.

The sum of the squares of the first ten natural numbers is, 12 + 22 + … + 102 = 385

The square of the sum of the first ten natural numbers is, (1 + 2 + … + 10)2 = 552 = 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.

Here’s my solution:

let square x = x*x
 
let difference =
    let naturals = seq { 1L..100L }
    let sumOfSquares = naturals |> Seq.map square |> Seq.sum
    let squareOfSum = naturals |> Seq.sum |> square
    squareOfSum - sumOfSquares
 
printfn "Project Euler Problem #6: What is the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.?"
difference |> printfn "Answer: %d"

Simple and straight-forward.

Project Euler Problem #5

I’m beginning to learn F# and the best way for me to go about that is to start applying it. There are some interesting computational problems over at Project Euler . This post is the continuation of a series of posts each involving a separate Project Euler problem. This post involves solutions to Project Euler problem #5.

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?

One quick thing to note. 2520 is not the product of 12345678910 (10 factorial or 10!). Since some of those numbers share common factors, those common factors are not repeated. So 2520 = 5789. The prime factorization of 2520 is 2^3 * 3^2 * 5 * 7. Here are the prime factorizations of all the numbers from 1 to 10:

  1. 1
  2. 2
  3. 3
  4. 2^2
  5. 5
  6. 2 * 3
  7. 7
  8. 2^3
  9. 3^2
  10. 2 * 5

The trick to efficiently computing the smallest number which can be divided by the numbers from 1 to X is to produce a prime factorization which overlaps with each of those divisors.

As part of my solution for Project Euler problem #3 I developed a function to produce a sequence which contains the prime factors for any number:

let sequence (smallest : int64) (x : int64) = 
    if smallest <= 2L then
        // Start with 2
        Seq.append
            (Seq.singleton 2L)
            (Seq.unfold (fun (i : int64) -> Some (i, i + 2L)) 3L)
    else
        // Start with smallest
        Seq.unfold (fun (i : int64) -> Some (i, i + 2L)) smallest
 
let findSmallestDivisor (smallest : int64) (x : int64) = 
    sequence smallest x 
    |> Seq.tryPick (fun elem ->  if x % elem = 0L then Some elem else None)
 
// The smallest divisor we can find will always be prime. By factoring 
// out each prime divisor, a list of prime factors can be efficiently 
// built up.
let primeFactors (x : int64) = 
    let unfoldHelper (smallest, remainder) = 
        match findSmallestDivisor smallest remainder with
        | Some divisor -> Some (divisor, (divisor, remainder / divisor))
        | None -> None
    Seq.unfold unfoldHelper (2L, x)

Starting with the primeFactors sequence and modifying it slightly this is my first solution to the problem:

// utility definitions
let boolToOption (test:'T->bool) (value:'T) = 
    if test value then Some value else None
let dividesEvenly dividend divisor = int(dividend % divisor) = 0
let isEven dividend =  dividesEvenly (int64(dividend)) 2L 
let isOdd dividend = isEven dividend |> not
let id x = x
 
 
let potentialDivisors (start: int64) (upTo: int64) = 
    let infiniteDivisors =
        if start <= 2L then
            // Start with 2
            Seq.append
                (Seq.singleton 2L)
                (Seq.unfold (fun (i : int64) -> Some (i, i + 2L)) 3L)
        else
            // Start with smallest odd greater than or equal to start
            Seq.unfold (
                fun (i : int64) -> 
                    Some (i, i + 2L)) (if start % 2L = 1L 
                        then start 
                        else start + 1L)
    let limitedDivisors = 
        infiniteDivisors |> Seq.takeWhile (fun divisor -> divisor <= upTo)
    limitedDivisors
 
let findSmallestDivisor (start:int64) (dividend:int64) = 
//    printf "Potential divisors for %d: " dividend
//    potentialDivisors start dividend |> Seq.iter (fun x -> printf "%d " x)
//    printfn ""
    potentialDivisors start dividend 
    |> Seq.tryPick (dividesEvenly dividend |> boolToOption)
 
// The smallest divisor we can find will always be prime. By factoring
// out each prime divisor, a list of prime factors can be efficiently
// built up.
let primeFactors (x : int64) = 
    let unfoldHelper (smallest, remainder) = 
        match findSmallestDivisor smallest remainder with
        | Some divisor -> Some (divisor, (divisor, remainder / divisor))
        | None -> None
    Seq.unfold unfoldHelper (2L, x)
 
 
let createFactorMap dividend =
    let countedFactors = primeFactors dividend |> Seq.countBy id 
    let factorMap = 
        countedFactors
        |> let foldHelper map (factor, count) = 
               match Map.tryFind factor map with 
               | Some existingCount -> 
                   if count > existingCount
                       then Map.add factor count map 
                       else map 
               | None -> Map.add factor count map
           in Seq.fold foldHelper Map.Empty
    factorMap
 
// combine the factor maps by folding over map A and combining with the
// corresponding entries in map B
let combineFactorMaps mapA mapB=
    let foldHelper combinedMap factor countB =
        match Map.tryFind factor mapA with
        | Some countA -> Map.add factor (max countB countA) combinedMap
        | None -> Map.add factor countB combinedMap
    let combinedFactorMap = Map.fold foldHelper mapA mapB
    combinedFactorMap
 
let combinedFactorMap x = 
    seq { 1L..x }
    |> Seq.map createFactorMap
    |> Seq.fold combineFactorMaps Map.empty
 
let generateNumber x =
    let rec pow exponent x =
        match exponent with
        | 0 -> 1L
        | exponent -> x * pow (exponent - 1) x
    combinedFactorMap x
    |> Map.fold (fun number factor count -> number * (pow count factor)) 1L
 
printf  "Project Euler Problem #5: What is the smallest number that is "
printfn  "evenly divisible by all of the numbers from 1 to 20?"
generateNumber 20L |> printfn "Answer: %d"

Project Euler Problem #4

I’m beginning to learn F# and the best way for me to go about that is to start applying it. There are some interesting computational problems over at Project Euler . This post is the continuation of a series of posts each involving a separate Project Euler problem. This post involves solutions to Project Euler problem #4.

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.

// generate pairs of 3-digit numbers
let seq = seq {
    for a in 100..999 do
        for b in 100..999 do
            yield (a, b)
            }
 
// test if a string is palindromic - only works on numbers
let rec isPalindrome (str : string) =
    let len = str.Length
    if len <= 1 then true
    else
        if str.Chars(0) = str.Chars(len - 1) then isPalindrome str.[1..len - 2]
        else false
 
// sequence of pairs of 3-digit numbers which when multiplied produce a palindromic number
let palindromes = seq |> Seq.filter (fun (a, b) -> (a * b).ToString() |> isPalindrome)
 
// find the biggest palindromic numbers from the pairs of 3-digit numbers
let max = palindromes |> Seq.maxBy (fun (a, b) -> a*b)
 
printfn "Project Euler Problem #4: Find the largest palindrome made from the product of two 3-digit numbers."
let (a, b) = max in printfn "Answer: %d*%d = %d" a b (a*b)

Pretty good so far – it gets the correct answer, but what if we had to deal with finding very large palindromes? The above code has several inefficiencies.

  1. It generates duplicate pairs of numbers: for instance it will generate both (100, 200) and (200, 100) – so most pairs of numbers appear twice in the generated sequence.
  2. Since we’re looking for the largest palindrome – not the smallest – it would make sense to start at (999, 999) rather than (100, 100).
  3. If we find that for some (a, b), a*b is a palindrome, then for any (x, y) for which x < a and y < b, then x*y < a*b. By this logic we can short-circuit the pair generation for all pairs for which that inequality holds.
  4. If we short-circuit certain pairs of numbers, then it doesn’t make sense to generate a list for each range of numbers – if we use sequence ranges instead of list ranges we’ll never generate the numbers which aren’t used.
  5. Some numbers will never generate a palindrome when multiplied with another number – for instance all numbers which end in zero (divisible by ten) can never generate a palindrome.

Solving #1 involves only a small change – the start of the inner range variable begins at ‘a’ not ’100′.

// generate pairs of 3-digit numbers
let seq = seq {
    for a in 100..999 do
        for b in a..999 do
            yield (a, b)
    }

Solving #2 and #4 affect the same area of code:

// generate pairs of 3-digit numbers
let seq = seq {
    for a in seq {999.. -1 ..100} do
        for b in seq {a.. -1 ..100} do
            yield (a, b)
    }

That’s slightly better. Now to try to tackle the third bullet item:

// test if a string is palindromic - only works on numbers
let rec isPalindrome (str:string) =
    let len = str.Length
    if len <= 1 then true
    else
        if str.Chars(0) = str.Chars(len - 1) then isPalindrome str.[1..len - 2]
        else false
 
let boolToOption (test:'a->bool) (value:'a) = if test value then Some value else None
 
// sequence of pairs of 3-digit numbers which when multiplied produce a palindromic number
let palindromes = 
    let palindromeOptions = seq {
        for a in seq {999.. -1 ..100} do
            let isPalindrome (a, b) = (a*b).ToString() |> isPalindrome
            yield (seq {a.. -1 ..100} |> Seq.tryPick (fun b -> boolToOption isPalindrome (a,b)))
         }
    palindromeOptions |> Seq.choose (fun x -> x)
 
// find the biggest palindromic numbers from the pairs of 3-digit numbers
let max = palindromes |> Seq.maxBy (fun (a, b) -> a*b)
 
printfn "Project Euler Problem #4: Find the largest palindrome made from the product of two 3-digit numbers."
let (a, b) = max in printfn "Answer: %d*%d = %d" a b (a*b)

The code now generates fewer pairs – but it still generates pairs which are obviously not higher than the previous pairs. Here’s an almost completely rewritten program to find the maximum:

// test if a string is palindromic - only works on numbers
let rec isPalindrome (str:string) =
    let len = str.Length
    if len <= 1 then true
    else
        if str.Chars(0) = str.Chars(len - 1) then isPalindrome str.[1..len - 2]
        else false
 
let maxPalindromePair = 
    let maxLimit = 999
    let minLimit = 100
    let rec maxPalindrome max  i j = 
        if i = minLimit-1 then max
        else if j = minLimit-1 then maxPalindrome max (i-1) maxLimit
        else
        match max with
        | Some (a, b) ->
            let min = min a b
            if i < min && j < min then max
            else
                if isPalindrome ((i*j).ToString()) then 
                    if i*j > a*b then Some (i, j)
                    else maxPalindrome max (i-1) j
                else maxPalindrome max i (j-1)
        | None ->
            if isPalindrome ((i*j).ToString()) then
                maxPalindrome (Some (i, j)) (i-1) maxLimit
            else maxPalindrome None i (j-1)
    match maxPalindrome None maxLimit maxLimit with
    | Some x -> x
    | None    -> (0, 0)
 
// find the biggest palindromic numbers from the pairs of 3-digit numbers
//let max = palindromes |> Seq.maxBy (fun (a, b) -> a*b)
 
printfn "Project Euler Problem #4: Find the largest palindrome made from the product of two 3-digit numbers."
let (a, b) = maxPalindromePair in printfn "Answer: %d*%d = %d" a b (a*b)

If you run this version and compare it against my first attempt the performance difference isn’t very noticeable. However, if you try to find the largest palindrome which is the product of say 4 or 5 digits….the difference is more than noticeable.

Project Euler Problem #3

I’m beginning to learn F# and the best way for me to go about that is to start applying it. There are some interesting computational problems over at Project Euler . This post is the continuation of a series of posts each involving a separate Project Euler problem. This post involves solutions to Project Euler problem #3.

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

What is the largest prime factor of the number 600851475143 ?

module Version1 =
    let potentialDivisors (x : int64) = 
        Seq.unfold (fun (i : int64) -> Some (i, i + 1L)) 2L
 
    let findSmallestDivisor (x : int64) = 
        if x = 1L then 1L
        else Seq.pick (fun elem ->  if x % elem = 0L then Some elem else None) (potentialDivisors x)
 
    // The smallest divisor we can find will always be prime. By factoring out each
    // prime divisor, a list of prime factors can be efficiently built up.
    let primeFactors (x : int64) = 
        let unfoldHelper (remainder : int64) = 
            let divisor = findSmallestDivisor remainder
            if divisor = 1L
                then None
                else Some (divisor, remainder / divisor)
        Seq.unfold unfoldHelper x
 
    let maxPrimeFactor (x : int64) = primeFactors x |> Seq.max

This code is fairly efficient at brute-forcing small numbers like the one in problem #3 – but it can be made even more efficient. One factor is to recognize that 2 is the only even prime – all others are odd. The sequence which generates the factors to test should skip all even numbers after 2:

    let potentialDivisors (x : int64) = 
        Seq.append
            (Seq.singleton 2L)
            (Seq.unfold (fun (i : int64) -> Some (i, i + 2L)) 3L)

Another optimization to notice is that since we keep successively finding the smallest divisor it’s not necessary to keep trying those numbers which are less than the previously found smallest divisor – they’ve already been checked.

let sequence (smallest : int64) (x : int64) = 
    if smallest <= 2L then
        // Start with 2
        Seq.append
            (Seq.singleton 2L)
            (Seq.unfold (fun (i : int64) -> Some (i, i + 2L)) 3L)
    else
        // Start with smallest
        Seq.unfold (fun (i : int64) -> Some (i, i + 2L)) smallest
 
let findSmallestDivisor (smallest : int64) (x : int64) = 
    if x = 1L then 1L
    else Seq.pick (fun elem ->  if x % elem = 0L then Some elem else None) (sequence smallest x)
 
// The smallest divisor we can find will always be prime. By factoring out each
// prime divisor, a list of prime factors can be efficiently built up.
let primeFactors (x : int64) = 
    let unfoldHelper (smallest, remainder) = 
        let divisor = findSmallestDivisor smallest remainder
        if divisor = 1L
            then None
            else Some (divisor, (divisor, remainder / divisor))
    Seq.unfold unfoldHelper (1L, x)

The program snippet above was adapted to track the smallest divisor found to speed up the checks for further divisors. The updated code looks like the following:

open System
 
let sequence (smallest : int64) (x : int64) = 
    if smallest <= 2L then
        // Start with 2
        Seq.append
            (Seq.singleton 2L)
            (Seq.unfold (fun (i : int64) -> Some (i, i + 2L)) 3L)
    else
        // Start with 3
        Seq.unfold (fun (i : int64) -> Some (i, i + 2L)) smallest
 
let findSmallestDivisor (smallest : int64) (x : int64) = 
    if x = 1L then 1L
    else Seq.pick (fun elem ->  if x % elem = 0L then Some elem else None) (sequence smallest x)
 
// The smallest divisor we can find will always be prime. By factoring out each
// prime divisor, a list of prime factors can be efficiently built up.
let primeFactors (x : int64) = 
    let unfoldHelper (smallest, remainder) = 
        let divisor = findSmallestDivisor smallest remainder
        if divisor = 1L
            then None
            else Some (divisor, (divisor, remainder / divisor))
    Seq.unfold unfoldHelper (1L, x)
 
let maxPrimeFactor (x : int64) = primeFactors x |> Seq.max
 
printfn "Project Euler Problem #3: What is the largest prime factor of the number 600851475143?"
maxPrimeFactor 600851475143L  |> printfn "Answer: %d"

So far these improvements have focused improving the performance at the expense of code bloat. When writing the first version of findSmallestDivisor I used the Seq.pick method and used 1L as a sentinel value. After writing the initial version I found the Seq.tryPick method which wraps the result in an option value.

[fsharp firstline="13"] let findSmallestDivisor (smallest : int64) (x : int64) = sequence smallest x |> Seq.tryPick (fun elem -> if x % elem = 0L then Some elem else None)

// The smallest divisor we can find will always be prime. By factoring out each // prime divisor, a list of prime factors can be efficiently built up. let primeFactors (x : int64) = let unfoldHelper (smallest, remainder) = match findSmallestDivisor smallest remainder with | Some divisor -> Some (divisor, (divisor, remainder / divisor)) | None -> None Seq.unfold unfoldHelper (2L, x)

By removing the sentinel value and using option values instead I can leverage the F# type checker to improve the quality of my code - the compiler can't tell that 1L is a sentinel value - but it can easily check None.

Project Euler Problem #2

I’m beginning to learn F# and the best way for me to go about that is to start applying it. There are some interesting computational problems over at Project Euler . This post is the continuation of a series of posts each involving a separate Project Euler problem. This is my first solution to Project Euler problem #2.

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

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

Here’s my first attempt at it:

open System
 
let fibonacci = Seq.unfold (fun (current, next) -> Some (current + next, (next, current + next))) (0, 1)
let isEven = (fun i -> i % 2 = 0)
 
let sumOfEvenFibonacciNumbers = Seq.sum (Seq.filter isEven (Seq.takeWhile (fun i -> i < 4000000) fibonacci))
 
printfn "Project Euler Problem #2: Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million."
printfn "Answer: %d" sumOfEvenFibonacciNumbers

Notice though that I have to use a lot of parenthesis due to composition – there’s gotta be a better way that is clearer and doesn’t involve so many parenthesis.

Leaving the fibonacci and isEven definitions alone:

[fsharp firstline="6"] let sumOfEvenFibonacciNumbers = fibonacci |> Seq.takeWhile (fun i -> i < 4000000) |> Seq.filter isEven |> Seq.sum

Now that's a lot nicer - it's much more obvious that we start off with the original Fibonacci sequence, stop at 4 million, take only the even ones, and finally sum them all up.

Now to fix a bug in our Fibonacci sequence. Typically the Fibonacci sequence starts with (0, 1) or (1, 1), not (1, 2) - but our problem statement specifies the start as (1, 2) (although even if the problem is evaluated starting at (0, 1) or (1, 1) the result is the same). The fibonacci definition above specifies (0, 1) as the starting point for the unfold operation...however the first two terms of the generated sequence are (1, 2). What's going on?

When we return the return the value we need to make sure to return the initial values. Here's the buggy line of code:

[fsharp firstline="3"] fun (current, next) -> Some (current + next, (next, current + next))

And the corrected version:

[fsharp firstline="3"] fun (current, next) -> Some (current, (next, current + next))

Project Euler Problem #1

I’m going to start learning F# and the best way for me to go about that is to start applying it. There are some interesting computational problems over at Project Euler . This will be the first post in a series of posts each involving a separate Project Euler problem.  This is my first solution to Project Euler problem #1 and it also happens to be my very first F# program.

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

module Version1 =
    let IsMultipleOfThreeOrFive (i : int) = i % 3 = 0 or i % 5 = 0
 
    let MultiplesOfThreeOrFiveLessThan (i : int) = Seq.filter IsMultipleOfThreeOrFive [1..(i - 1)]
 
    let SumOfMultiplesOfThreeOrFiveLessThan i = Seq.sum (MultiplesOfThreeOrFiveLessThan i)
 
    let answer = lazy(SumOfMultiplesOfThreeOrFiveLessThan 1000)

The lazy block in the answer allows the timing to be accurately computed – if it’s missing the answer is computed to eagerly. This could easily be cleaned up and compressed some by taking out the debug statements and some of the lets which are only used once. Here’s the cleaned up version:

[fsharp gutter="true"] module Version2 = let isMultipleOf (multiples : seq) i = Seq.exists (fun x -> (i % x) = 0) multiples

let sumOfMultiplesLessThan (multiples : seq<int>) (i : int) =
    Seq.sum (Seq.filter (isMultipleOf multiples) [1..i-1])

let answer = lazy(sumOfMultiplesLessThan [3; 5] 1000)

As you can see I made it more generic - it's not limited to multiples of 3 or 5 anymore. One more tweak to the program involves pipelining the expression on line 7:

[fsharp gutter="true" firstline="6"] [1..i-1] |> Seq.filter (isMultipleOf multiples) |> Seq.sum

This looks much nicer because there's fewer parenthesis and you don't have to go hunting for the middle of the expression to find where it starts executing: with this pipelined style execution flows much more smoothly from left to right.

Final version:

module Version3 =
    let isMultipleOf (multiples : seq<int>) i =
        Seq.exists (fun x -> (i % x) = 0) multiples
 
    let sumOfMultiplesLessThan (multiples : seq<int>) (i : int) =
        [1..i-1] |> Seq.filter (isMultipleOf multiples) |> Seq.sum
 
    let answer = lazy(sumOfMultiplesLessThan [3; 5] 1000)