Project Euler Problem 41: Pandigital Prime¶
The source code for this problem can be found here.
Problem Statement¶
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 Discussion¶
First, observe that a decimal representation is assumed, so, only integers up to nine digits in length need be considered. However, the search space may be reduced even further by observing that some \(n\)digit pandigital patterns cannot possibly be prime. In particular, by enumeration of all pandigital numbers for a given \(n\) or by the application of rules of divisibility.
Case: 1digit pandigital (by enumeration)
\(1\) is not prime
\(\therefore\) no \(1\)digit pandigital number is prime
Case: 2digit pandigital (by enumeration)
\(12 = 2^2 \times 3\) is not prime
\(21 = 3 \times 7\) is not prime
\(\therefore\) no \(2\)digit pandigital number is prime
Case: 3digit pandigital (by rules of divisibility)
Observe that any such number must contain the digits \(1,2,3\)
Now, observe that \(1 + 2 + 3 = 6\), which is divisible by \(3\)
\(\Rightarrow\) any \(3\)digit pandigital is divisible by \(3\)
\(\therefore\) no \(3\)digit pandigital number is prime
Case: 5digit pandigital (by rules of divisibility)
Observe that any such number must contain the digits \(1,2,3,4,5\)
Now, observe that \(1 + 2 + 3 + 4 + 5 = 15\) which is divisible by \(3\)
\(\Rightarrow\) any \(5\)digit pandigital is divisible by \(3\)
\(\therefore\) no \(5\)digit pandigital number is prime
Case: 6digit pandigital (by rules of divisibility)
Observe that any such number must contain the digits \(1,2,3,4,5,6\)
Now, observe that \(1 + 2 + 3 + 4 + 5 + 6 = 21\) which is divisible by \(3\)
\(\Rightarrow\) any \(6\)digit pandigital is divisible by \(3\)
\(\therefore\) no \(6\)digit pandigital number is prime
Case: 8digit pandigital (by rules of divisibility)
Observe that any such number must contain the digits \(1,2,3,4,5,6,7,8\)
Now, observe that \(1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36\) which is divisible by \(3\)
\(\Rightarrow\) any \(8\)digit pandigital is divisible by \(3\)
\(\therefore\) no \(8\)digit pandigital number is prime
Case: 9digit pandigital (by rules of divisibility)
Observe that any such number must contain the digits \(1,2,3,4,5,6,7,8,9\)
Now, observe that \(1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45\) which is divisible by \(3\)
\(\Rightarrow\) any \(9\)digit pandigital is divisible by \(3\)
\(\therefore\) no \(9\)digit pandigital number is prime
So, we only need to consider \(4\)digit and \(7\)digit numbers.
Originally, my solution enumerated primes up to (and including) \(7\)digits and then checked whether each prime is \(n\)digit pandigital. While this algorithm produces the correct answer, we can do better. The runtime of this algorithm is dominated by the cost of prime sieving.
My second, superior, solution enumerates \(n\)digit pandigital numbers and checks whether they are prime. This solution is faster because there are generally less pandigital numbers than primes for the same number of digits (at least for the search interval considered):
 The number of \(7\)digit primes is about \(\frac{10^7}{\log(10^7)} \approx 620420\)
 The number of \(7\)digit pandigital numbers is precisely \(7! = 5040\)
Solution Implementation¶
from itertools import chain
from lib.numbertheory import is_probably_prime
from lib.sequence import Pandigitals
def solve():
""" Compute the answer to Project Euler's problem #41 """
answer = 0
for candidate in chain(Pandigitals(n=4), Pandigitals(n=7)):
if is_probably_prime(candidate):
answer = max(answer, candidate) # the ndigit pandigital is also prime
return answer
expected_answer = 7652413

solutions.problem41.
solve
()¶ Compute the answer to Project Euler’s problem #41