Problem 9

A Pythagorean triplet is a set of three natural numbers, a b c, for which,

a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

Solution 1

using System;

namespace ProjectEulerCSharp_009

{

    class Program

    {

        static void Main(string[] args)

        {

            int iterations = 0;

            for (int a = 1; a <= 998; a++)

            {

                for (int b = 1; b <= 998; b++)

                {

                    int c = 1000 – (a + b);

                    iterations++;

                    if (a * a + b * b == c * c)

                    {

                        System.Console.WriteLine("{0}", a*b*c);

                        System.Console.WriteLine(iterations);

                        return;

                    }

                }

            }

        }

    }

}

Solution 2

using System;

namespace ProjectEulerCSharp_009

{

    class Program

    {

        static void Main(string[] args)

        {

            int iterations = 0;

            for (int a = 1; a <= 998; a++)

            {

                for (int b = a + 1; b <= 998; b++)

                {

                    int c = 1000 – (a + b);

                    iterations++;

                    if (a * a + b * b == c * c)

                    {

                        System.Console.WriteLine("{0}", a*b*c);

                        System.Console.WriteLine(iterations);

                        return;

                    }

                }

            }

        }

    }

}

Solution 3

using System;

namespace ProjectEulerCSharp_009

{

    class Program

    {

        static void Main(string[] args)

        {

            int iterations = 0;

            for (int a = 1; a <= 998; a++)

            {

                for (int b = a + 1; a + b < 1000; b++)

                {

                    int c = 1000 – (a + b);

                    iterations++;

                    if (a * a + b * b == c * c)

                    {

                        System.Console.WriteLine("{0}", a*b*c);

                        System.Console.WriteLine(iterations);

                        return;

                    }

                }

            }

        }

    }

}

 

Solution 4

using System;

namespace ProjectEulerCSharp_009

{

    class Program

    {

        static void Main(string[] args)

        {

            int iterations = 0;

            for (int a = 1; a <= 998; a++)

            {

                for (int b = a + 1; a + b < 1000; b++)

                {

                    int c = 1000 – (a + b);

                    if (c <= b) { break; }

                    iterations++;

                    if (a * a + b * b == c * c)

                    {

                        System.Console.WriteLine("{0}", a*b*c);

                        System.Console.WriteLine(iterations);

                        return;

                    }

                }

            }

        }

    }

}

Discussion

I am a big fan of getting the code working then optimizing later.  I wanted to demonstrate that process with those post so I have included 4 iterations of optimizations.

If we were to loop through all of the possible digits from 1 through 998 twice (once for a and once for b) we would end up doing 996,004 iterations.  That’s our baseline.

Solution 1

Because they state that there is only 1 solution, as soon as we find it there is no reason to continue.  The obvious optimization is to exit the loops once we’ve found it.  This brings our iterations to 198,778.

Solution 2

If we realize that we only need to check the numbers where b is greater than a then we can save ourselves and addition 20,000 iterations bringing our new number to 178678.

Solution 3

Knowing that another condition is that a + b + c = 1000 then a + b has to be less than 1000.  This saves nearly 20,000 iterations as well.  We are down to 159,716 iterations.

Solution 4

Finally, knowing that c has to be greater than b we can cut the iterations by 90,000 to : 69676.

That makes us about 14 times faster than the original version.  There are going to be some additional optimizations you can make, but how fast do you need it?   On my laptop, the difference is imperceptible.  I could have left it at the original and been quite happy.

If you have any questions, leave a comment, find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).

Problem 8

Find the greatest product of five consecutive digits in the 1000-digit number.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

Solution

namespace ProjectEulerCSharp_008

{

    class Program

    {

        static void Main(string[] args)

        {

            string digits = @"

                73167176531330624919225119674426574742355349194934

                96983520312774506326239578318016984801869478851843

                85861560789112949495459501737958331952853208805511

                12540698747158523863050715693290963295227443043557

                66896648950445244523161731856403098711121722383113

                62229893423380308135336276614282806444486645238749

                30358907296290491560440772390713810515859307960866

                70172427121883998797908792274921901699720888093776

                65727333001053367881220235421809751254540594752243

                52584907711670556013604839586446706324415722155397

                53697817977846174064955149290862569321978468622482

                83972241375657056057490261407972968652414535100474

                82166370484403199890008895243450658541227588666881

                16427171479924442928230863465674813919123162824586

                17866458359124566529476545682848912883142607690042

                24219022671055626321111109370544217506941658960408

                07198403850962455444362981230987879927244284909188

                84580156166097919133875499200524063689912560717606

                05886116467109405077541002256983155200055935729725

                71636269561882670428252483600823257530420752963450"

            .Replace(" ", "").Replace("\r\n", "");

           

            int answer = 0;

            for(int i = 0; i < digits.Length – 5; i++)

            {

                int digit1 = int.Parse(digits.Substring(i+0, 1));

                int digit2 = int.Parse(digits.Substring(i+1, 1));

                int digit3 = int.Parse(digits.Substring(i+2, 1));

                int digit4 = int.Parse(digits.Substring(i+3, 1));

                int digit5 = int.Parse(digits.Substring(i+4, 1));

                int product = digit1*digit2*digit3*digit4*digit5;

                if(product > answer) { answer = product; }

            }

            System.Console.WriteLine(answer);

        }

    }

}

Discussion

I’m not sure what the ‘trick’ with this problem was supposed to be.  Even when this problem was posted (a little over 9 years ago) it probably only took a fraction of a second.  I suppose converting a character digit to an integer used to be a bit of a novelty.  Something like int digit = chardigit – ‘0’ would give you the results you want. 

If you have any questions, leave a comment, find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).

Problem 7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

Solution

//By listing the first six prime numbers:

//2, 3, 5, 7, 11, and 13, we can see that

//the 6th prime is 13.

 

//What is the 10001st prime number?

 

 

using System.Collections.Generic;

namespace ProjectEulerCSharp_007

{

    class Program

    {

        static void Main(string[] args)

        {

            List<long> primes = new List<long>(10) { 2, 3 };

            while (primes.Count < 10001)

            {

                bool isPrime = false;

                long candidate = primes[primes.Count – 1] + 2;

                while (!isPrime)

                {

                    isPrime = true;

                    foreach (long prime in primes)

                    {

                        if (candidate % prime == 0)

                        {

                            isPrime = false;

                            break;

                        }

                    }

                    if (!isPrime) { candidate += 2; }

                    else { primes.Add(candidate); }

                }

            }

            System.Console.WriteLine(primes[primes.Count-1]);

        }

    }

}

 

Discussion

Getting back to my imperative roots, this problem was pretty easy to solve.

If you have any questions, leave a comment, find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).

Problem 6

The sum of the squares of the first ten natural numbers is,

1² + 2² + … + 10² = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)² = 55² = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Solution

//The sum of the squares of

 //the first ten natural numbers is,

 

 //1^2 + 2^2 + … + 10^2 = 385

 //The square of the sum of the

 //first ten natural numbers is,

 

 //(1 + 2 + … + 10)^2 = 55^2 = 3025

 //Hence the difference between the sum

 //of the squares of the first ten natural

 //numbers and the square of the sum is

 //3025 – 385 = 2640.

 

 //Find the difference between the sum of

 //the squares of the first one hundred natural

 //numbers and the square of the sum.

 

 

namespace ProjectEulerCSharp_006

{

    class Program

    {

        static void Main(string[] args)

        {

            int sumsqrs = 0;

            int sqrsums = 0;

            for (int i = 0; i <= 100; i++)

            {

                sumsqrs += i * i;

                sqrsums += i;

            }

            sqrsums *= sqrsums;

            System.Console.WriteLine(sqrsums – sumsqrs);

        }

    }

}

 

Discussion

No trick today. 

If you have questions, leave a comment or please find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).

Problem 5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Solution

// 2520 is the smallest number that can be

// divided by each of the numbers from 1 to 10

// without any remainder.

 

// What is the smallest positive number

// that is evenly divisible by all of the

// numbers from 1 to 20? 

 

namespace ProjectEulerCSharp_005

{

    class Program

    {

        static void Main(string[] args)

        {

            //have we found the answer yet?

            //let’s start off by saying "no"

            bool notFound = true;

            //20 seems like as good of a

            //starting spot as any

            long candidate = 20;

            while(notFound)

            {

                //I am incrementing up front

                //so that my loop exits elegantly

                candidate++;

 

                //here I am assuming that this candidate

                //is the answer.  I set it back when I

                //find a divisor that it doesn’t work for

                notFound = false;

 

                //this is not too important, but it’s a good

                //idea to start with the small numbers first because

                //they are more likely to fail

                for (int divisor = 2; divisor <= 20; divisor++)

                {

                    if (candidate % divisor != 0)

                    {

                        notFound = true;

                        break;

                    }

                }

            }

 

            System.Console.WriteLine(candidate);

        }

    }

}

Discussion

The brute force approach is pretty silly, but it does work and within the 1 minute rule.  It takes about 7.5 seconds on my 6 month old laptop.  When this problem was announced (November 2001) the same code would have probably taken over 10 minutes to complete – at least according to my back of the napkin estimation of Moore’s law.  🙂

If you have questions, leave a comment or please find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).

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.

Solution

using System.Collections.Generic;

 

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

 

namespace ProjectEulerCSharp_004

{

    class Program

    {

        static void Main(string[] args)

        {

            //simple placeholder for our

            //biggest palindrome

            int maxPalindrome = 0;

 

            //loop through each 3-digit number

            for (int i = 100; i < 1000; i++)

            {

                //this is a slight optimization

                //over our F# solution because

                // 100 * 101 = 101 * 100 so we

                // don’t need to perform the second

                // multiplication

                for (int j = i; j < 1000; j++)

                {

                    int product = i * j;

                    //used an extension method to test for

                    //palindromicity (is that a word)

                    if (product.IsPalindrome()

                        && product > maxPalindrome)

                    {

                        maxPalindrome = product;

                    }

                }  

            }

            System.Console.WriteLine(maxPalindrome);

        }

    }

 

    // extension methods are awesome

    public static class Extensions

    {

        // here we create a function called

        // IsPalindrome that uses the same

        // technique as the F# function

        public static bool IsPalindrome(this int i)

        {

            // get a convenient list of chars

            List<char> chars =

                new List<char>(i.ToString().ToCharArray());

            // reverse them

            chars.Reverse();

            // are we a palindrome?

            return i == int.Parse(new string(chars.ToArray()));

        }

    }

}

 

Discussion

My favorite part of this solution is the use of the extension method.  Why don’t we use those all the time?  Of course, the generic List structure offers some helpful routines as well.

If you have questions, leave a comment or please find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).

Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Solution

using System.Collections.Generic;

using System;

namespace ProjectEulerCSharp_002

{

    class Program

    {

        static void Main(string[] args)

        {

            List<long> factors = PrimeFactor(600851475143);

           

            // this sorts the numbers in ascending order

            factors.Sort();

            // this reverses the list so the biggest one

            // is on top.

            factors.Reverse();

 

            //show me the money

            System.Console.WriteLine(factors[0]);

        }

   

 

        public static List<long> PrimeFactor(long number)

        {

            //here is our list of prime factors

            List<long> factors = new List<long>();

           

            //assume the number is prime

            //unless we find a factor

            bool isPrime = true;

 

            //here is the upper limit of what we need to test

            long factorCandidate = (long)Math.Sqrt(number);

            while (factorCandidate > 1)

            {

                //is this a factor?

                if (number % factorCandidate == 0)

                {

                    //if so, what are it’s factors?

                    factors.AddRange(

                        PrimeFactor(factorCandidate));

                    //what about the other divisor?

                    factors.AddRange(

                        PrimeFactor(number / factorCandidate));

                    //we know this one isn’t prime

                    isPrime = false;

                }

                //next

                factorCandidate–;

            }

            //we are only adding prime factors

            if (isPrime) { factors.Add(number); }

            //send ’em back

            return factors;

        }

    }

}

 

Discussion

In contrast to my F# solution this didn’t take much longer than 5 minutes to write.  I didn’t spend any time optimizing it because it ran so fast for the problem already.

If you have questions, leave a comment or please find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).

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.

Solution

namespace ProjectEulerCSharp_002

{

    //By considering the terms in the Fibonacci sequence

    //whose values do not exceed four million, find the

    //sum of the even valued terms.

    class Program

    {

        static void Main(string[] args)

        {

            int answer = 0;

            //typically when calculating fibonacci series

            //it’s performed two elements at a time

            //this is not a requirement

            int fib0 = 1;

            int fib1 = 1;

            int fib2 = 2;

            while (fib2 < 4000000)

            {

                //we know the fib2

                //is always even

                //and represents ALL

                //evens in the series

                //see the ‘proof’ below

                answer += fib2;

 

                //odd + even = odd

                fib0 = fib1 + fib2;

                //odd + even = odd

                fib1 = fib0 + fib2;

                //odd + odd = even

                fib2 = fib0 + fib1;

            }

 

            System.Console.WriteLine(answer);

        }

    }

}

Discussion

As I mentioned in the F# solution, an obvious optimization is to sum as you go.  I’ve also taken it a step further and removed the check for evenness because every third Fibonacci is even.  I layout a rough proof in my comments above.

If you have questions, leave a comment or please find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).

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.

Solution

namespace ProjectEulerCSharp_001

{

    //Add all the natural numbers below one

    //thousand that are multiples of 3 or 5.

 

    //first, we will get all of

    //the numbers divisible by 3

    class Program

    {

        static void Main(string[] args)

        {

            int answer = 0;

 

            // add the 3’s, the 5’s, and subtract one set of 15’s

            for (int three = 0; three < 1000; three += 3)

              { answer += three; }

            for (int five = 0; five < 1000; five += 5)

              { answer += five; }

            for (int fifteen = 0; fifteen < 1000; fifteen += 15)

              { answer -= fifteen; }

 

            System.Console.WriteLine(answer);

        }

    }

}

 

Discussion

If you saw the F# solution then this should be a relatively easy translation.  The main difference is that I create the sum as I’m building the list.

If you have questions, leave a comment or find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).