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