Project Euler Solution 41: Pandigital prime

In this blog post we will look at Problem 41: Pandigital prime where we have to find the largest prime number with unique digits.

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?

What is the upper bound here? Since there are 9 possible digits, it could be a number with 9 digits and therefore 987,654,321. We can already exclude this because the sum of the numbers 1 to 9 is 45 and therefore divisible by 3. It is impossible to have a pandigital prime with nine digits. The same goes for 8 digits, the sum of the numbers 1 to 9 is 36 and also divisble by 3. Therefore it can only be a number with up to 7 digits.

Since the ceiling is known, we take the prime sieve from Solution 7: 10001st prime and generate the primes up to 7,654,321. Then we just filter out the numbers which are not pandigital.

def is_pandigital(number: int) -> bool:
    s = str(number)
    if "0" in s:
        return False
    digits = set(s)
    return len(digits) == len(s)


def solution() -> int:
    return max(
        itertools.islice(filter(is_pandigital, reversed(prime_sieve(7_654_321))), 1)
    )

When we iterate the primes in reverse we can also just take the first one that is pandigital and go with that one. This takes 3.4 s to compute, so it should be fine.

Since we already know that the number has to have all digits in it, we could also try all permutations. There are just 7! = 5,040 possible permutations in there. And we also know that itertools.permutations can generate them in lexicographical order. The problem is that we have to check whether the number is a prime number without having a list of primes. For this we can write a really simple function that just checks all the numbers as potential divisors up until the square root of the number to test.

def is_prime(number: int) -> bool:
    for divisor in itertools.count(2):
        if number % divisor == 0:
            return False
        if divisor * divisor > number:
            return True

This function will be costly for larger numbers, but since we are only going to go to ten million, we only have to test divisors up until about 3300, which is fine.

def solution_permutations() -> int:
    for digits in reversed(list(itertools.permutations("1234567"))):
        number = int("".join(digits))
        if is_prime(number):
            return number

The solution then is just going through the reversed list of permutations, checking them for being a prime and return that once we have it. This now runs in 802 µs, which is much faster than before.