Project Euler Solution #41: Pandigital prime

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?

Solution

I think there are two straight-forward approaches. The first is naively generating primes from 2 to 987654321 and find the largest pandigital number. The second approach generates a list of all digits from 1 to \(k\) where \(k\) is between 1 and 9.

But we can do a little better by improving the bounds. The order of the digits will be re-arranged by the permutation, but the sum will always be the same. We know that if the digit sum is divisible by three, the whole number is divisible by three and as such not a prime number. Starting with \(1+2+3+4+5+6+7+8+9=45\), which is divisible by three. Doing the same without the 9 leads to \(1+2+3+4+5+6+7+8=36\) - which is also divisible by three. We can check the next sum, which is \(1+2+3+4+5+6+7=28\). Okay, the largest pandigital number has at most 7 digits and as such is 7654321. Generating the primes to be checked with the first approach would require only 0.8% of the previous search space. But we can do a bit better. We first check all lengths we need to take into account, even if chances are high that the resulting number will be a 7 digit number:

s = 0
for n in range(1, 7 + 1):
    s+= n
    if s % 3 != 0:
        print(n)

The result are 1, 4 and 7. A length of 1 can be ignored, since it is just the one itself, which is unlikely to be the maximum. We can concrete the suspicion that the number must be a 7 digit number by calculating the search space again. All permutations with 4 digits are just \(4!=24\), which is just 0.5% of the total search space. When we use the permutation generator of python, we can implement the routine quite easily:

m = 2
for p in itertools.permutations(range(1, 7 + 1)):
    s = reduce(lambda b, a : 10 * b + a, p)
    if s > m and is_prime(s):
        m = s

print(m)

However, by walking the permutations backwards, we can improve the performance drastically:

for p in itertools.permutations(range(7, 0, -1)):
    s = reduce(lambda b, a : 10 * b + a, p)
    if is_prime(s):
        print(s)
        break

with the prime check function:

def is_prime(n):
    if n % 2 == 0 or n % 3 == 0:
        return False
    for i in xrange(5, int(n**0.5) + 1, 6):
        if n % i == 0 or n % (i + 2) == 0:
            return False
    return True