Just A Programmer We’re Just Programmers…

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.