Project Euler Problem 4

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!