Solutions to Problem 41. Written in Python.
Problem: 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?
Method 1: This is my slowest (and original) solution without using any tricks or analysis of the problem. I also used a fast prime number generator from this StackOverflow answer. I first generate all primes up to 987654321 (the largest pandigital integer) and then parallelize the pandigital check and print the maximum of the returned values.
Method 2: Method 2 is much faster with runtimes of around 0.6s on my i7 machine (running on PyPy). We only need to permute on the pandigital numbers. Python’s itertools package has a sweet permutations function that does this for us. For a 9 digit number, the permuations are
9! = 362,880, for 8 digits
8! = 40,320, and so on.
Method 3: As it turns out, we only need to check the permutations of a 7 digit pandigital number. The Divisibility Rule states that if the sum of a digits’ numbers are divisible by 3 or 9, then the original number is divisible by 3 or 9. This means that all numbers that are 1 to n pandigital are not prime, where n = 9, 8, 6, 5, 3, and 2. The runtime for this solution hovers around 0.15s.