Project Euler - Problem 4 in C#

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.

Sounds like pretty simple problem ... right.

For all the three digit numbers, find the product between them and check if the product of numbers is palindrome or not. And if yes, find the greatest product.

Like explained in the problem, a palindrome is a word, phrase, or number, whose meaning may be interpreted the same way in either forward or reverse direction. To test a palindrome number, we need to reverse the digits of the number. And for that, we iterate using formula ((y*10) + (x%10)) where y is new reversed number starting from 0 and x is original number to be reversed. Here is the example below to understand it better

Iteration	Formula	New Number (y)	Actual Number (x)
0	0	0	98743
1	(0*10) + (98743%10)	3	9874
2	(3*10) + (9874%10)	34	987
3	(34*10) + (987%10)	347	98
4	(347*10) + (98%10)	3478	9
5	(3478*10) + (9%10)	34789	0

Method to reverse digits and test if number is palindrome or not ....

// Check is number is palindrome
public static bool IsPalindrome(this int number)
{
    // store the actual number for check
    var actualNumber = number;
    // initialize new palindrome number
    var palindromeNumber = 0;

    // to reverse the number e.g. 98743 and set new palindrome number to 0
    // multiple new palindrome number with 10, and add modulus when number is divide by 10 and set it back in the new number
    // iteration 1 -> newPalindromeNumber: (0*10 + 98743%10) -> 3; number -> 9874
    // iteration 2 -> newPalindromeNumber: (3*10 + 9874%10) -> 34; number -> 987
    // iteration 3 -> newPalindromeNumber: (34*10 + 987%10) -> 347; number -> 98
    // iteration 4 -> newPalindromeNumber: (347*10 + 98%10) -> 3478; number -> 9
    // iteration 5 -> newPalindromeNumber: (3478*10 + 9%10) -> 34789; number -> 0
    // loops till number is not equal to 0
    // and now we have reversed number to check if its palindrome
    while (number != 0)
    {
        palindromeNumber = (palindromeNumber * 10) + (number % 10);
        number = number / 10;
    }
    //if actual number and new expected palindrome numbers are same
    return (actualNumber == palindromeNumber);
}

Here is the first basic implementation to solve the problem

// basic looping
public static IEnumerable<int> ListOfThreeDigitNumbersProduct()
{
    // looping for the first 3 digit numbers
    for (var i = 999; i > 99; i--)
    {
        // looping for the second 3 digit numbers
        for (var j = 999; j > 99; j--)
        {
            // find the product b/w the numbers
            var product = i*j;

            // check if the number is palindome
            if (product.IsPalindrome())
            {
                yield return product;
            }
        }
    }
}

Whats happening in this solution

• Number x and y iterate from 100 to 999 to find product of x with all the 3 digits y number.
• Every product is verified for palindrome test and if successful, added to the list of palindrome products of 3 digit number
• Max number is picked from the list of palindrome numbers from the list.

var maxProduct = ListOfThreeDigitNumbersProduct().Max();

Note: We don't need to create the list of palindrome numbers.We can put conditions to always compare and get the largest palindrome number.

This solution works but there is room for improvement .... :) . Here are my observation for improvement for faster solution ...

• Product of x*y is equal to y*x. So we don't need check the product of x with y and again for x = y and y = x. This can be avoided by setting upper bound y to x.
• If the new product is greater then the previously stored palindrome number, only then we should run palindrome test on the current number. This way we can avoid palindrome test processing time on many numbers, hence making solution faster.

// intelligent faster solution
public static int LargestThreeDigitNumbersProduct()
{
    // initialize largest palindrome number variabel
    var largestPalindromeNumber = 0; 

    // loopping thru all 3 digit numbers
    for (var i = 999; i > 99; i--)
    {
        // PERFORMACE BOOST
        // looping thru 3 digits number from 100 to first number
        // anything greater then first number has been already calculated
        // as (a*b) = (b*a)
        for (var j = 100; j <= i; j++)
        {
            // product of nunmbers
            var product = i*j;

            // PERFORMACE BOOST
            // if current product is greated then the previous saved palindrome product
            // only then check for number is palindrome else we can avoid extra checking task
            if (product > largestPalindromeNumber) 
            {
                // check number is palindrome
                if (product.IsPalindrome())
                {
                    // if is palindrome, save it as largest palindrome number 
                    largestPalindromeNumber = product;
                }
            }
        }
    }

    return largestPalindromeNumber;
}

Link to Problem #3

If you have a better solution, please don't hide it from us .... share your knowledge ... :) .... till then, enjoy solving problems.

Project Euler - Problem 3 in C#

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 ?

To find the largest prime factor of a number x, we can do it in couple of ways. One way is the start dividing the number x by y = 2, 3, 4 ... For each factor y of x, this will remove all the smaller factors before moving to the next y till y is less then x. This will work but there is room for improvement over here.

Let improve this existing solution with some facts.

• 2 is the only even prime number, so we can eliminate all the even numbers by recursively dividing the number by 2. Then we can find the prime factor of new whole number faster by incrementing divisor by 2 starting from 3.
• If we don't find the prime factor of x until y (number we are testing to be prime factorial starting from 3) is less then equal to square root of x, means we have a tested all the possible options and no more factors are present. 

Here is the function to find the largest prime factor of a given number.

public static long LargestPrimeFactorByDividingBy2InLoopsInitially(long number)
{
    // set the initial dividing number
    long dividingNumber = 2;
    // looping to divide with only even prime number to remove all possible even numbers
    while (number % 2 == 0)
    {
        number = number / 2;
    }
    // no even number is left, hence starting with 3
    dividingNumber = 3;
    // divide in loops until dividing number is less then square root of expected lpf
    while (System.Math.Sqrt(number) > dividingNumber)
    {
        if (number % dividingNumber == 0)
        {
            // if expected lpf is divisible, update the number
            number = number / dividingNumber;
        }
        else
        {
            dividingNumber += 2;
        }
    }

    return number;
}

Link to Problem #2
Link to Problem #4

If you have any better and faster way, please share it with us. Till then, enjoy solving problems .....

Project Euler - Problem 2 in C#

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.

We have two options to solve this problem, declarative or imperative approach. Declarative approach has two steps

• Step 1: Generate the list of all the numbers in fibonacci series less then equal to 4 million

public static IEnumerable<int> GenerateList(int upperBound)
{
 if (upperBound < 2)
 {
  throw new Exception("Invalid upper bound");

 }

 IList<int> list = new List<int>();

 var prev1 = 1;
 list.Add(prev1);
 var prev2 = 2;
 list.Add(prev2);
 var sum = 0;

 while (sum < upperBound)
 {
  sum = prev1 + prev2;

  list.Add(sum);

                prev1 = prev2;
                prev2 = sum;
 }

 return list;
}

• Step 2: Sum all the even numbers in the list

// OPTION 1
var sum = GenerateList(4000000)
  .Where(x => x % 2 == 0)

  .Sum();

// By creating list first and reducing list to +ve numbers and finding their sum
Console.WriteLine(sum);

In the imperative approach, sum the even number while generating the fibonacci series in the loop itself.

// OPTION 2
var prev1 = 1;
var prev2 = 2;

// prev2 value is 2 which is a even number, so sum starts from 2
var sumByLooping = prev2;

while(prev2 <= 4000000) 

{
 var sumOf2Nos = prev1 + prev2;

 prev1 = prev2;
 prev2 = sumOf2Nos;

 if (sumOf2Nos % 2 == 0) 

 {
  sumByLooping += sumOf2Nos;
 }
}

// By looping thru numbers and adding only +ve numbers
Console.WriteLine(sumByLooping);

Link to Problem #1
Link to Problem #3

Have fun solving problems ....

Project Euler - Problem 1 in C#

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

For this problem, either we can create list of int or array of int values up to 1000 like this

// generate the list of numbers from lower bound to upper down
private static IList<int> GenerateNumberList(int upperBound, int lowerBound = 0)
{
 var numberList = new List<int>();

 for (var i = lowerBound; i < upperBound; i++)
 {
  numberList.Add(i);
 }

 return numberList;
}

// generate the array of numbers from lower bound to upper down
private static int[] GenerateNumberArray(int upperBound, int lowerBound = 0)
{
 var arrLength = upperBound - lowerBound;

 var numberArr = new int[arrLength];

 for (var i = 0; i < arrLength; i++)
 {
  numberArr[i] = lowerBound + i;
 }

 return numberArr;
}

Using LINQ for the declarative approach to find the sum of all the numbers either divisible by 3 or 5

// OPTION 1
stopwatch.Start();

var listSum = GenerateNumberList(1000)
   .Where(x => x % 3 == 0 || x % 5 == 0)
   .Sum();

stopwatch.Stop();

Console.WriteLine (listSum);

// OPTION 2
stopwatch.Reset ();
stopwatch.Start ();

var arrSum = GenerateNumberArray (1000)
   .Where (x => x % 3 == 0 || x % 5 == 0)
   .Sum ();

stopwatch.Stop();

Console.WriteLine (arrSum);

With imperative way of programming without using LINQ, we can run the for loop from 0 to 1000 and keep adding all number which meet the criteria.

// OPTION 3
stopwatch.Reset ();
stopwatch.Start ();

var sum = 0;

for(var i = 0; i < 1000000; i++) {
 if (i % 3 == 0 || i % 5 == 0) {
  sum += i;
 }
}

stopwatch.Stop ();

Console.WriteLine (sum);

Click here to next problem

Have fun solving problems ...

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