Project Euler - Problem 4 in F#

Largest palindrome product

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.

For this problem, we need to iterate through all the 3 digits number and get there products. Here is the solutions

    // function to flip the existing number to reverse the digits 
    let reverseNumber n =
        // recurring function to create new number to flip the 
        // existing the number digit one at a time
        let rec loop newNum = function
            // if the new number is 0
            // return the new created number as it is
            |0 -> newNum
            // if number is not 0
            // recall the function with new number * 10 and adding modules 
            // of number dividing by 10.
            // return update old number by dividing by 10 
            |x -> loop (newNum * 10 + x % 10) (x/10)    
        loop 0 n

    // check if the number is palindrome
    let isPalindrome = function
        // if number is equal to reversed number then its palindrome, 
        // return true
        | x  when x = reverseNumber x -> true
        // else return false
        | _ -> false

    // function to get the max palindrome number of multiplication
    // of two numbers between the limits
    let maxPalindromeNumber lowerLimit upperLimit =
        // create the seq of all the palidrome numbers create 
        // by multiple two numbers between the limits
        let numbers = seq {
            // get first number from the loop
            for i = lowerLimit to upperLimit do
                // get the second number from the loop
                for j = lowerLimit to upperLimit do
                    // multiple both the numeber
                    let z = i * j
                    // and check if number is palindrome
                    if isPalindrome z then
                        // if yes, return the number to seq else 
                        // move back to new numbers in the loop
                        yield z
        }
        // return the max number from the seq
        Seq.max numbers

    // create diagnostics stopwatch
    let sw = System.Diagnostics.Stopwatch()
    // start the stopwatch
    sw.Start() 
    // call function to get max palindrome number product of two numbers 
    // between 100 and 900
    let number = maxPalindromeNumber 100 999
    // stop the stopwatch
    sw.Stop()
    
    // print number
    printfn "multple of 3 digit resulting %d  - (with processing time %A)" number sw.ElapsedMilliseconds
 

Code is pretty self explanatory with comments. The avg time of the solution is 177ms

Please feel free to leave you feedback, whats good in the blogs and where i can improve.

Thanks and Happy CODING .... :)

Project Euler - Problem 3 in F#

Largest prime factor

Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

Here is my Solution #1

    

    (**********************************
    Solution 1 
    ***********************************
    slow solution as it iterates through all the numbers
    **********************************)

    let theNumber = 600851475143I //13195

    let rec LargestPrimeFactorial (x: bigint) (y:bigint) = 
        match x, y with
            | u, t when u = t -> u
            | c, d when c%d = 0I -> 
                match c with
                    | m when m = theNumber -> LargestPrimeFactorial (m/d) 2I
                    | n -> LargestPrimeFactorial theNumber ((theNumber/n)+1I)
            | e, f -> LargestPrimeFactorial e (f+1I)
            | a, b when a = b -> a
            | _, _ -> failwith "not valid option"

    let sw = System.Diagnostics.Stopwatch()
    sw.Start()  
    let primeFactorNo = LargestPrimeFactorial theNumber 2I
    sw.Stop()
    printfn "%A - (with processing time %A)" primeFactorNo  sw.ElapsedMilliseconds

In this solution, i try to iterates through all the numbers which is not so great solution for the huge numbers.
LargestPrimeFactorial takes two parameters, one the number we are finding factorial for and second number we are checking is divisor or not. Here are match condition checks

• | u, t when u = t -> u: If both the numbers are same then, return the prime number
• | c, d when c%d = 0I -> : If second number is factor of first number, then we try to find the factors for the divisor to check if that's a prime number or not. we call the same function with different parameters to find is its a prime number or not.
• | e, f -> LargestPrimeFactorial e (f+1I): If number is not divisor then recall the function with new incremented number to find the largest prime number divisor.
• | _, _ -> failwith "not valid option": If no condition is matched, fail with exception.

We this process is very slow. This is a basic logic to find the largest prime factor by dividing the number with each and every number to find all the factors and then check if the factorial number is prime number of not in the same manner. This logic on avg took 59590 ms.

Here is my Solution #2

    

    

    (**********************************
    Solution 2
    ***********************************
    Better solution to find all the divisors
    if n / x = y, obviously both x and y are factors, so I don't have to probe y anymore
    If I start probing from 2 going up, I can stop probing when I have reached \sqrt n. In fact, any number bigger than \sqrt n must have been already found probing a smaller number.
    Suppose for example that we have to factor the number 36 (one of the triangle number
    **********************************)

    let theNumber = 600851475143I //13195

    let divides (x:bigint) (y:bigint) = (x % y = 0I)

    let rec GetAllFactors (num:bigint) (index:bigint) factors = 
        if (divides num index) then
            let y = num / index
            if index < y then
                GetAllFactors num (index + 1I) (index::y::factors)
            else if (y = index) then
                (index::factors)
            else 
                factors
        else if index > bigint (sqrt (float num)) then
            factors
        else 
            GetAllFactors num (index + 1I) factors

    let rec PrimeNumber = function
        | [] -> 0
        | h::t -> 
            let factors = GetAllFactors h 2I []
            if(factors.Length = 0) then
                int h
            else 
                PrimeNumber t

    let rec LargestPrimeFactorial (x: bigint) = 
        let factorList = GetAllFactors x 2I []
        let factorRevList = factorList
                                |> List.sort 
                                |> List.rev

        let largestPrimeNumber = PrimeNumber factorRevList
        largestPrimeNumber        
    
    let sw = System.Diagnostics.Stopwatch()
    sw.Start()    
    let primeFactorNo = LargestPrimeFactorial theNumber
    sw.Stop()

In this solution, i have used better solution to find all the divisors. According to new formula, if n / x = y, obviously both x and y are factors, so I don't have to probe y anymore. If I start probing from 2 going up, I can stop probing when I have reached sqrt n. In fact, any number bigger than sqrt n must have been already found probing a smaller number. Here is the explanation of the written code

• GetAllFactors: Gets all the factors of a number in the array
• PrimeNumber: Checks if the number is prime or not
• LargestPrimeFactorial: Get the largest number from the factors list.

This logic on avg took 2900 ms.

Please feel free to leave feedback ... whats good in the post and where i can improve.

Thanks and happy coding

Project Euler - Problem 2 in F#

Even Fibonacci numbers

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, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Here is my solution

    // Create a mutable list, so that we can add elements 
    // (this corresponds to standard .NET 'List<T>' type)
    let l = new ResizeArray<_>([1;2])
 
    let rec fabonacci a b upperLimit = 
        match a, b with
            | _, _ when a + b <= upperLimit -> 
                let c = a + b
                l.Add(c)
                fabonacci b c upperLimit
            | _ -> l
 
    let sumOfEven =
        (fabonacci 1 2 4000000)
            |> List.ofSeq
            |> Seq.filter (fun x -> x % 2 = 0) 
            |> Seq.sum 

Since its dynamic seq we are creating which depends on the last two numbers, we need a mutable list which we can populate according to our need and logic. For Fibonacci, we need to have access to previous two numbers in the list to generate new one.

This solution is flexible too with the upper limit, so this logic can be used anywhere to create the Fibonacci sequence with any upper bound. First step is to create Fibonacci sequence with the upper bound and initial number to kick start the sequence.Once seq is created up to desired upper bound, we are left with filtering of the sequence for even numbers only and get their sum.

Please leave your feedback and happy coding. 

Project Euler - Problem 1 in F#

Multiples of 3 and 5

Problem 1

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.

Here is my solution

    // Option 1
    let sumOfNoDivisbleBy3or5UnderN n = 
        [for i in 1 .. n-1 -> i]
            |> Seq.filter (fun x -> x%3 = 0 || x%5 = 0)
            |> Seq.sum
 
    let sumOfNoDivisbleBy3or5Under10 = sumOfNoDivisbleBy3or5UnderN 10
 
    let sumOfNoDivisbleBy3or5Under1000 = sumOfNoDivisbleBy3or5UnderN 1000
 
    printfn "The sum of all the multiples of 3 or 5 is %d" sumOfNoDivisbleBy3or5Under1000
 
    // Option 2
    let sumOfFilteredSeq filterCri n = 
        seq { for i in 1 .. n-1 -> if filterCri i then i else 0 }
            |> Seq.sum
 
    let filteredSeqOf3or5 = sumOfFilteredSeq (fun x -> x%3 = 0 || x%5 = 0)
 
    let sumOfNoUnder10 = filteredSeqOf3or5 10
 
    let sumOfNoUnder1000 = filteredSeqOf3or5 1000
 
    printfn "The sum of all the multiples of 3 or 5 is %d" sumOfNoUnder1000

Here i have specified two solutions. 

Options 1 is hard coded with the filter criteria and is only flexible  in changing the upper bound of the List where as option 2 is flexible in both upper bound as well as the filter criteria