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. [fsharp] 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) [/fsharp] Following the algorithm from Euler, there isn't much to it at all. [fsharp] 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 [/fsharp]