mgroves

As always, you can find my source code at CodePlex.

Problem 11 has given me all kinds of trouble.  So much so that I haven’t actually solved it.  I’ve tried 2 or 3 different methods, I’ve Google it, I’ve tried cheating, I’ve tried guessing.  Nothing is working for me.  I gave up after many, many tries.  I’m so sure that I’m doing it right, but I must be missing one minor thing somewhere.

Problem 12 was kinda fun.  The meat of the problem is figuring out the factors of a given number.  Once I had that (which was easy to brute force, and a little tricky to slim down), the rest is just a couple of for-loops.  I used the given example as a single test case.

Problem 13 involves very, very large numbers.  Larger than 32-bits can represent.  So, since I was still using .NET 3.5 at the time, I scratched out a very rudimentary “BigInt” class that only performed addition on itself.  It was just as much a pain in the neck as it was 10 years in Introduction to C++ class, except this time I only implemented one operator.  Once I switched the Project Euler solution over to VS2010 and .NET 4, I went back and switched this solution to use the BigInteger class, which, by the way, is new to .NET (obviously) and lives in System.Numerics.  Anyway, once you have your own BigInt or BigInteger (or some language like Ruby that handles all that nonsense for you), Problem 13 is a piece of cake: just do some adding up and some parsing.  I wrote a couple of tests that used long.MaxValue—I left them in, even though it’s generally quite silly to test a class built into the framework.

If you guys have any ideas for Problem 11, I would love a fresh set of eyes.

Just a quick Project Euler update.  Number 8 was pretty straightforward, I just went through and got each product and then found the max.  For Number 9, I created a Triplet class with an IsPythagorean method.  I then use three loops (nested) to go start from 1 and go up to a given n.  It’s not entirely brute force, because the 2nd number must be greater than the 1st, and the 3rd number can be calculated using the Pythagorean theorum.  Then, if that Triplet sums to the given n, I add it to a list, and return that list at the end.  The Triplet with the highest sum is the answer.  Since the problem says there is only one that sums to 1000, I simply return .Single() of the list.

Number 10 was yet another prime-numbers problem.  I used the IsPrime method from before, and simply looped from 1 to a million, and added the primes to a list.  Linq can be used then to sum up the list, and done.

As before, check out all the source on CodePlex.

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

I did a slow, brute force algorithm, and a fast algorithm using Euclid's algorithm to get GCD/LCM. The slow method is to simply start guessing, incrementally, and seeing if the guess modulus of 1-20 is 0. The second method requires you to know that the least common multiple (LCM) of x,y,z is the same thing as LCM(x,LCM(y,z)). The LCM function is transitive (or whatever, I'm not a math guy). Therefore, you just loop from 2 to 20, and get the accumulative LCM. The LCM function can be written to be dependent on the greatest common denominator (GCD) function, which can be implemented efficiently using Euclid's algorithm.

At this point, I created a "MathHelper" static class to hold methods like GCD and LCM for future use (for Project Euler or otherwise).

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

I wrote two methods: SumOfTheSquaresForNumbers1Through(n) and SquareOfTheSumForNumbers1Through(n), both implemented in a very straightforward way--no surprises or anything fancy here. Works very efficiently too.

#7 - What is the 10001st prime number?

I got in a bit of a rush here for some reason, so I cranked out a very brute force solution, just to "get the answer". I felt hollow right away, and decided to take a break after this problem. I read the solution notes which outlined a more efficient way to test if a number is prime or not. I added this implementation to the MathHelper class. Anyway, this problem made me slow down and rethink why I'm doing these problems: it's not to "just solve them" in some sort of competitive sense, and it's not to learn a bunch of mathy stuff either. The point, for me, is to practice my programming, test my own skills, and maybe learn new ways to think about program/method design.

Well, that's all for now. As always, check out the latest source at codeplex, which will almost surely be farther ahead than my blog.

I've finished some more Project Euler problems. Here's some notes:

Problem 3. So, I finally had to break down and write some unit tests for this one. I also had to brush up on what 'prime factors' are, because it's not exactly something I use every day. My solution involved recursion: find the lowest number that divides evenly, divide by it, and repeat using the dividend. If that number is ever itself, it's prime, which is an ending condition for the recursion.

At this point, I also refactored the structure of the project code. Each problem will still be in its own class, but each of those classes implements a common interface. This way, I can simply loop through all solved problems and output the answer without having to repeat formatting and stuff like that.

Problem 4. This one was fun, because it involves palindromes! I again used unit tests, because I knew I would have to watch out for off-by-one errors. I also created a string extension method to reverse the string. I could have created a "IsPalindrome" extension, but generally speaking, the use of such a method is pretty narrow, and thus doesn't really fit as an extension method. My first approach to this problem was to gradually reduce two integers from 999 on down until I got a palindrome from the product. This turned out to not work as expected, and I ended up with a brute force O(n²) algorithm instead. It runs pretty fast, but if the problem called for 4,5,6,etc digit numbers, it would start to get really slow.

As before, you can check out my ongoing source code on CodePlex.com.

Project Euler is an ongoing series of math/programming problems. I'm going to try to go through as many of these as I can this year, post the code for them, and talk about anything interesting that I learn in the process.

You can follow my progress by checking out a CodePlex repository for Project Euler that I've set up. If you have a Project Euler account, you should be able to see my progress on the mgroves Project Euler profile page.

The first problem was pretty easy: "Find the sum of all the multiples of 3 or 5 below 1000." To do this, I just loop through each number from 3 to 999, and take the modulus 3 and 5 of that number. If either modulus is 0, add it to a list. When done, sum up the list:

            for (int i = 3; i < x; i++)
            {
                if (((i%3) == 0) || ((i%5 == 0)))
                {
                    list.Add(i);
                }
            }

The second problem is slightly more difficult: Find the sum of all even numbers in the Fibbonaci sequence which do not exceed 4,000,000. My code takes a straightforward approach; I'm sure the math majors out there can think of a better way:

        public static IList FibonacciAllEvenValueTermsLessThan(int x)
        {
            var list = new List();
            int term1 = 1;
            int term2 = 2;
            list.Add(term2);
            while(term2 < x)
            {
                var newterm1 = term2;
                var newterm2 = term1 + term2;
                if((newterm2 % 2) == 0)
                {
                    list.Add(newterm2);
                }
                term1 = newterm1;
                term2 = newterm2;
            }
            return list;
        }

For both problems, I take the result and use the Linq Sum() extension method, because I'm a total Linq junky these days. I also started out using longs instead of ints, before I realized that, hey, 32-bit numbers go up to around 4 billion (2³²), not 4 million.