Project Euler - Problem 41

Project euler again! This time, a fun little one that looks for pandigital primes:

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?

My strategy here was to utilize my Primes function to generate a boolean array of primes, and then check possible numbers against it. I also needed to utilize a method that checked if a number was pandigital or not.

public static bool IsPandigital(Int64 num)

{

string strNum = num.ToString();

int size = strNum.Length;

if (strNum.Contains("0"))

return false;

char[] digits = new char[size];

for (int i = 1; i <= size; i++)

digits[i - 1] = char.Parse(i.ToString());

char[] chars = strNum.ToCharArray();

if (chars.Intersect(digits).Count() == size && chars.Distinct().Count() == size)

return true;

return false;

}

Pretty simple here. First does a quick check: if a number contains a 0, it's not pandigital. Then, based on the size of the number, figures out which digits it'll check for (ie a 4 digit number needs to have 1, 2, 3, and 4) and then checks that the number contains each of those digits, and each one only once.

Great! Now we're ready to go. The only remaining problem is that the largest pandigital number is 987,654,321 - almost 1 billion! That's a little bit too big for my boolean prime array to handle - it tops out around 300 million. Fortunately, we can eliminate 9 and 8 digit pandigital numbers as candidates for primality.

How do we do that? Well, one test for primality is to sum the digits of a number and find out if it's evenly divisible by 3. Since 9+8+7+6+5+4+3+2+1 = 45, which is divisible by 3, no 9 digit pandigital number is prime. Same for 8 digit pandigitals. Thus our ceiling is only 7,654,321 - just a little over 7 million!

Final code to get the answer:

public static ValueType Go()

{

// we can eliminate 9 and 8 digital pandigitals because their sum is divisble by three, and hence not prime.

var primes = CustomMath.Primes(7654321);

int nMax=0;

for (int i = 1; i < 7654321; i+= 2)

if (i < primes.Length)

if (primes[i] && CustomMath.IsPandigital(i))

nMax = i;

return nMax;

}

The answer is 7652413. This code runs a little bit more slowly than most - executing in 1422ms. I could probably optimize it futher, but it gets the job done well!