Month: October 2010

Project Euler

Project Euler Problem 4

TACOCAT is a palindrome!Continuing on from my previous adventures in Euler, we now come to problem 4. Problem 4 asks you to find the largest palindrome that is the product of two 3 digit numbers.

My solution is brute force, and originally, I started two loops both at 999 and counted down, figuring the first palindrome found would be the largest. I was wrong, however, and was required (sticking to brute force) to check all products for palindromes and just keep the largest. The “count backwards” code returned “Using 995 and 583, the max palindrome is 580085”, which is incorrect. My correct code is as follows:

using System;

namespace ProjectEuler
{
	/// <summary>
	/// A palindromic number reads the same both ways. The largest
	/// palindrome made from the product of two 2-digit numbers is 
	///  9009 = 91 x 99.
	/// Find the largest palindrome made from the product of two 3-digit numbers.
	///  http://projecteuler.net/index.php?section=problems&id=43
	///
	/// The answer is 906609
	/// </summary>
	public class Problem4
	{
		public static void Main(string[] args)
		{
			var max = 0;
			var theI = 0;
			var theK = 0;
			
			for (var i = 100; i <= 999; i++)
			{
				for (var k=100; k <= 999; k++)
				{
					var product = i * k;
					if (IsPalindrome(product) && product > max)
					{
						theI = i;
						theK = k;
						max = product;
					}
				}
			}

			Console.WriteLine("Using {0} and {1}, the max palindrome is {2}", theI, theK, max);
		}

		public static bool IsPalindrome(int number)
		{
			var forward = number.ToString();
			var reverse = forward.ToCharArray();
			Array.Reverse(reverse);

			return forward == new string(reverse);
		}
	}
}

That returns “Using 913 and 993, the max palindrome is 906609”.

After you put in the correct answer on the Project Euler site, you are allowed to then view the forums to discuss your answers. I found some interesting math inside that made other algorithms much more efficient. Here is what I gleaned:

A six digit palindrome would be in the format abccba. If we take our real answer of 906609, that could also be written as 9(100000) + 0(10000) + 6(1000) + 6(100) + 0(10) + 9(1). The same way, our generic answer can be written as 100000a+10000b+1000c+100c+10b+1a. Simplified again, that is 100001a+10010b+1100c. You can factor 11 out of that, leaving you with 11(9091a + 910b + 100c). That means that the product would have to be easily divisible by 11 (saving you the lengthy – by comparison – palindrome check). My original algorithm ran in 9.219022 seconds on my Mac Mini running Mono. When I add in the “divide by 11 check” to short-circuit every palindrome comparison, the algorithm now runs in 1.63679 seconds. That is a HECK of an improvement. Math… I think this might just catch on!

Project Euler

Project Euler Problem Three

Optimus PrimeIt has been almost two years since I tackled Project Euler Problems One and Two. I really wanted to get back into it, so there really is no time like the present to do the work. I’m on my Mac Mini right now, so I developed this in C#.Net using MonoDevelop.

This problem needs us to find the largest prime factor of a very large number. Obviously, to do this, you need to be able to generate a set of prime numbers to work with. I have an IsPrime method that uses a very brute force method (with the shortcut of only checking as high as the square root of the number). I Googled around for ways to generate primes and looked into the Sieve of Eratosthenes, but it was a little complicated for the time I had allotted myself to work on this problem (basically the ten minutes until I had to put my son to bed). Plus, it turns out that this entire piece of code runs in under a second on my several year old Mac Mini, so there was no need to optimize yet. I know that later Project Euler problems also deal in primes, so I may need to break it out then.

Once I had that method in place, it was really a simple matter of working up to the square root of the number in the problem, 600851475143, using the same shortcut. If the number in my loop was prime and evenly divided into our number, I stored it as the current largest number. When I was done, whatever number was currently in that variable was our champion. Pretty simple logic.


using System;

namespace ProjectEuler
{
	/// <summary>
	/// The prime factors of 13195 are 5, 7, 13 and 29.
	///  What is the largest prime factor of the number 600851475143 ?
	/// http://projecteuler.net/index.php?section=problems&id=3
	///
	/// The answer is 6857
	/// </summary>
	public class Problem3
	{
		protected static double number = 600851475143;
		
		public static void Main(string[] args)
		{
			double limit = Math.Floor(Math.Sqrt(number));
			double currentLargestPrime = 0;

			for (double i = 2; i <= limit; i++)
			{
				if (IsPrime(i) && (number % i == 0))
				{
					currentLargestPrime = i;
				}
			}			
			
			Console.WriteLine(currentLargestPrime);
		}

		public static bool IsPrime(double n)
		{
			if (n%2 == 0) return false;

			var upperLimit = Math.Floor(Math.Sqrt(n));

			for (double i = 3; i <= upperLimit; i++)
			{
				if (n % i == 0) return false;
			}

			return true;
		}
	}
}

Have you attempted this problem yet? What is your solution? I’d love to see them. You can post it in the comments or post a link if you’ve blogged it already.

Windows Phone 7

Windows Phone 7 Launch Event

I’m excited about the new Windows Phone 7 device, especially developing for it. I’ve written two blogs posts about it as of this date (Filed here) and I plan on writing many more.

I also plan on buying a Windows Phone 7 when it launches and getting as many apps as I can in the marketplace.

Microsoft has long shown that it is very focused on developers and always does launch events up big. As such, the launch events that are available here:

Windows Phone 7 Launch Event - Click for Details (Edit: Link removed, since it was taken down)

are sure to be awesome.

I’ve also added a small banner in my sidebar to stay up while the events are going off for two reasons. 1) There is a contest and 2) My hope is that a lot of developers will get excited and get tons of fantastic apps in the marketplace.

Go download the tools and let’s make this platform great!