Just A Programmer We’re Just Programmers…

Project Euler in F# – Problems 4 – 6

Problem 4

Find the largest palindrome that results from the multiplication of two numbers under 1000

I feel like I have a strange obsession with the Seq.unfold function. That function does most of the heavy lifting here.

Although the wise Euler pointed out to me that I can avoid duplicate multiplication factors, and keep track of the largest palindrome so far to avoid unnecessary `isPalindrome` checks.

let problem4 () =
    let isPalindrome (value: string) =
        match value.Length with
        | x when x % 2 = 1 -> (x-1)/2, (x-1)/2 + 1
        | x -> (x/2), (x/2)
        |> fun (pos1, pos2) ->
                    value.Substring(0, pos1), value.Substring(pos2)
        |> (fun (firstHalf, secondHalf) ->

            Array.rev (secondHalf.ToCharArray())
            |> (fun reversedcharArray -> new string(reversedcharArray))
            |> (fun reversedSecondHalf ->
                    firstHalf.Equals(reversedSecondHalf)))

    let productSeq (maximumInt:int) =
        Seq.unfold (fun state ->
            let mult1, mult2 = state
            let result = mult1 * mult2

            match state with
            | 100, _ -> None
            | _, 100 -> Some((result), ( (mult1 - 1) , (mult1 - 1)))
            | _ -> Some((result), ( mult1, (mult2 - 1)))
        ) (maximumInt, maximumInt)

    let largestPalindromeSoFar = ref None

    productSeq 999
    |> Seq.filter(fun (result) ->

        match !largestPalindromeSoFar with
        | Some(largestResult) when largestResult > result -> false
        | _ -> match isPalindrome (result.ToString()) with
                  | true ->
                        largestPalindromeSoFar := Some(result)
                        true
                  | _ -> false)
    |> Seq.max

Problem 5

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

I was so happy with my brute force solution, it looks so pretty, unfortunately it takes 3 1/2 minutes on my machine.

let problem5 () =
    let evenlyDivisibleByAllUpTo limit number =
        {limit .. -1 .. 1}
        |> Seq.forall(fun testNumber -> number % testNumber = 0)

    Seq.initInfinite(fun i -> (i + 1) * 20)
    |> Seq.find(fun testIndex ->evenlyDivisibleByAllUpTo 20 testIndex)

Project Euler’s math explains the problem a bit differently. I cant explain the formula in ten words or less, but after understanding it and applying a bit of functional style, results in this, which runs in under 1ms.

let problem5_correct () =

    let primesWithLimit limit =
        let testPrime (possiblePrime:float) =
            let sqrRootOfPrime = sqrt(possiblePrime)

            {2.0 .. sqrRootOfPrime}
            |> Seq.forall(fun divisor ->
                match divisor with
                | 1.0 -> true
                | x when divisor = possiblePrime -> true
                | _ -> possiblePrime % divisor > 0.0)

        {2.0 .. limit}
        |> Seq.filter(fun index -> testPrime index)

    let computeLimit = sqrt(20.0)

    primesWithLimit 20.0
    |> Seq.fold(fun state prime ->

        let exponent =
            match prime < computeLimit with
            | true -> floor( (log(20.0) / log(prime)) )
            | _ -> 1.0

        state * (float(prime) ** exponent)) 1.0
    |> int64

Problem 6

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

The brute force of this is rather innocent looking, and runs in < 1ms.

let problem6 () =

    let sumOfSquares maximum =
        {1L .. maximum}
        |> Seq.map(fun number -> number * number)
        |> Seq.sum

    let squareOfSums maximum =
        {1L .. maximum}
        |> Seq.sum
        |> fun result -> result * result

    (squareOfSums 100L) - (sumOfSquares 100L)

Following the algorithm from Euler, there isn’t much to it at all.

let problem6_correct () =

    let limit = 100L
    let sum = limit * (limit + 1L) / 2L
    let sum_sq = ((2L * limit) + 1L) * (limit + 1L) * limit / 6L
    int64(pown sum 2) - sum_sq

Project Euler in F# – Problems 1 – 3

Problem 1

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

Brute force is the first thing that comes to mind

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

But the wise Euler shows Math to be a better tactic, as his answer is unquestionably faster.

let problem1_correct () =
    let target = 999

    let sumDivisibleBy value =
        let p = target / value
        value * (p * (p + 1)) / 2

    (sumDivisibleBy 3) + (sumDivisibleBy 5) - (sumDivisibleBy 15)

Problem 2

Sum of all even Fibonacci numbers under 4 million

No real curveball here, unfold with a limit was the first Fibonacci method that came to mind

let problem2 () =
    let fibonacciSeq withLimit =
        Seq.unfold (fun previousState ->
            let nMinusTwo, nMinusOne = previousState
            let nextValue = nMinusTwo + nMinusOne
            let nextState = (nMinusOne, nextValue)

            match nextValue < withLimit with
            | true -> Some(nextValue, nextState)
            | false -> None
        ) (0, 1)

    fibonacciSeq 4000000
    |> Seq.filter(fun x -> x % 2 = 0)
    |> Seq.sum

Problem 3

What is the largest prime factor of the number 600851475143?

This one might take a few tries to get correct. I actually went and completed a few other Euler problems before coming back to this one.

The sample number, 13195, is the red herring here because it is so easy to get the answer if you aren’t thinking.

let problem3 () =
    let testPrime (possiblePrime:int64) =
        let sqrRootOfPrime = int64(System.Math.Sqrt(float(possiblePrime)))

        {1L .. sqrRootOfPrime}
        |> Seq.forall(fun divisor ->
            match divisor with
            | 1L -> true
            | x when divisor = possiblePrime -> true
            | _ -> possiblePrime % divisor > 0L)

    let factorSeq ofNumber =
        {2L .. (ofNumber/2L)}
        |> Seq.filter(fun testNumber -> ofNumber % testNumber = 0L)
        |> Seq.map(fun factor1 -> (factor1, (ofNumber / factor1)))
        |> Seq.takeWhile(fun (factor1, factor2) -> factor1 <= factor2)
        |> Seq.fold (fun acc (factor1, factor2) -> factor1 :: factor2 :: acc) []
        |> Seq.sort
        |> Seq.toList
        |> List.rev

    factorSeq 600851475143L
    |> Seq.find (fun factor -> testPrime factor)

That was unofficially my fourth attempt.

Project Euler in F#

While job hunting this time around, a recruiter pointed me to a website called Project Euler, as a great place to practice.

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

The problems always seem overly complicated, and somehow ask you to find the sum of this operation or said sequence. Most of the time, you are even provided with a sample input and output. An input I’m sure which is carefully chosen to tempt you to write a brute force algorithm.

I immediately went to do them in F#, because I find it so fun. 25 problems later… Why stop there…
After talking to Justin about it, I decided to blog my progress.

So this is a test to see how far I can get.
This might take a while…

Current Level: