Project Euler Problem #41

Question

I recently finished the project Euler problem # 41 :

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?

And I'm having trouble optimizing it.

Explanation

So we know that the upper bound should be a maximum of 987654321 which is the biggest pandigital number it's not a prime however so we probably can lower this but for now let's keep it like this.

We are working with primes and more specifically pandigital primes. First we need an algorithm that calculates all the primes up to our upper limit (987654321 ), I went for the sieve of Eratosthenes :

    bool[] primes = SetPrimes(987654321);
    private static bool[] SetPrimes(int max)
    {
        bool[] localPrimes = new bool[max + 1];
        for (long i = 2; i <= max; i++)
        {
            localPrimes[i] = true;
        }
        for (long i = 2; i <= max; i++)
        {
            if (localPrimes[i])
            {
                for (long j = i*2; j <= max; j += i)
                {
                    localPrimes[j] = false;
                }
            }
        }
        return localPrimes;
    }

Good those are all the primes that we will need now all that's left is to implement a pandigital number checker and iterate through the boolean array :

    private static bool IsPandigital(long input)
    {
        char[] digits = input.ToString().ToCharArray();
        for (int i = 1; i <= input.ToString().Length; i++)
        {
            int count = digits.Count(x => char.GetNumericValue(x) == i);
            if (count != 1)
            {
                return false;
            }
        }
        return true;
    }

Pretty simple check just taking the current index of the primes array, convert's it to a char array and we know that a pandigital number is that number that it has each from 1 to it's length exactly one (1, number.Length) so we do that in the for loop and than we check if it's contained exactly once if so we return true else we return false.

Lastly we iterate through the array of prime :

        long lastIndex = Array.LastIndexOf(primes, true);
        while (!IsPandigital(lastIndex))
        {
            lastIndex--;
            while (!primes[lastIndex])
            {
                lastIndex--;
            }
        }

Here we take the last index that has true value (the last prime number) and than we start decreasing the index that we are looking for if we incur a number that is pandigital and it's prime we just break out of all the loops and print it on the screen. It's currently running for about 75-78k milliseconds which really bothers me that's a lot of time. Any improvements concerning the performance and the code style are welcome.

Full Code :

    private static void Main()
    {
        Stopwatch sw = Stopwatch.StartNew();
        bool[] primes = SetPrimes(987654321);
        long lastIndex = Array.LastIndexOf(primes, true);
        while (!IsPandigital(lastIndex))
        {
            lastIndex--;
            while (!primes[lastIndex])
            {
                lastIndex--;
            }
        }
        sw.Stop();
        Console.WriteLine(lastIndex);
        Console.WriteLine("Time to calculate in milliseconds : {0}", sw.ElapsedMilliseconds);
        Console.ReadKey();
    }

    private static bool[] SetPrimes(int max)
    {
        bool[] localPrimes = new bool[max + 1];
        for (long i = 2; i <= max; i++)
        {
            localPrimes[i] = true;
        }
        for (long i = 2; i <= max; i++)
        {
            if (localPrimes[i])
            {
                for (long j = i*2; j <= max; j += i)
                {
                    localPrimes[j] = false;
                }
            }
        }
        return localPrimes;
    }

    private static bool IsPandigital(long input)
    {
        char[] digits = input.ToString().ToCharArray();
        for (int i = 1; i <= input.ToString().Length; i++)
        {
            int count = digits.Count(x => char.GetNumericValue(x) == i);
            if (count != 1)
            {
                return false;
            }
        }
        return true;
    }

Answer 1

You can exclude all n-digit pandigitals for n = 2,3,5,6,8,9 since they cannot be prime due to the Divisibility by 3 or 9 rule.
There only the 4-digit and 7-digit numbers left.

Since you need only the largest pandigital number, it makes sense to scan down starting from the largest 7-digit pandigital number.

My implementation of IsPandigital method:

private static bool IsPandigital(int number)
{
    int maxDigit = (int)Math.Log10(number) + 1;
    int allBitsExceptBitOne = (1 << (maxDigit + 1)) - 2;

    int digitBits = 0;
    while (number != 0)
    {
        int digit = number % 10;
        int mask = 1 << digit;
        if (digit == 0 || digit > maxDigit || (digitBits & mask) != 0)
            return false;
        digitBits |= mask;
        number /= 10;
    }
    return digitBits == allBitsExceptBitOne;
}

Sieve of Eratosthenes:

private static int[] GetPrimes(int n)
{
    BitArray a = new BitArray(n + 1, true);

    int sqrtn = (int)Math.Sqrt(n);
    for (int i = 2; i <= sqrtn; i++)
    {
        if (a[i])
        {
            for (int j = i * i; j <= n; j += i)
            {
                a[j] = false;
            }
        }
    }

    List<int> primes = new List<int>();
    for (int i = 2; i < a.Length; i++)
    {
        if (a[i])
            primes.Add(i);
    }

    return primes.ToArray();
}

Usage:

const int Max = 7654321;

var primes = GetPrimes(Max);
Array.Reverse(primes);

Console.WriteLine(primes.First(IsPandigital));

Answer 2

Sieve implementation

The Sieve of Eratosthenes is a reasonably good choice. There are other prime number sieves, but the SofE is pretty simple to implement and surely adequate for this task. Your particular implementation could be more efficient, however:

1. You test every candidate number for primality, even though the only even prime is 2. It would be a bit more efficient to make a special case for 2, and then to test only the odd candidates in the main loop.

2. The inner loop can start at i*i instead of at i*2, because the smaller multiples of i will already have been sieved out by the time you get around to testing i.

3. You therefore do not need to even consider candidate primes greater than sqrt(max), for by the time you reach those candidates, there cannot be any multiples less than or equal to max left to sieve out. (But this changes if you decide to build a list of primes, as discussed below.)

Pandigital testing

You are making a tremendous sacrifice of efficiency here to implement this in terms of Count(). Count itself, although not terrible, is also not great. To even get there, however, you need to format your number as a String, which by itself is more expensive than one whole pandigital test needs to be. You could instead just pick off the digits one by one via the modulo and integer division operators, and keep track in an array, or even in bit-array form in a single long (only 40 bits of the 64 are needed).

General

long is a wider data type than you need for representing the numbers being tested. int is wide enough to express all integers having nine or fewer digits in their decimal representations. You could, and probably should, use int -- or even better, uint -- everywhere you currently use long.

Also, there is a space vs. speed tradeoff available here, where you have opted for using less space. It is possible to augment your sieve to efficiently fill an array with the actual primes it discovers, particularly if you're willing to declare a big-enough array at the beginning, and not worry about unused space. It would be more efficient to process the elements of that array that are in use than to iterate over the whole range, testing directly against the sieve. In fact, if you do this then some of the extra space need be consumed only transiently, because you can let the sieve itself go after you finish filling the array of primes.