# 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?

``````

In [1]:

import time
import itertools

def is_prime(n):
if n <= 1:
return False
elif n <= 3:
return True
elif (n%2)==0 or (n%3)==0:
return False
else:
i = 5
while (i*i) <= n:
if (n%i)==0 or (n%(i+2))==0:
return False
i += 6
return True

def pandigitals():
digits = [9,8,7,6,5,4,3,2,1]
for n in range(9,0,-1):
for p in itertools.permutations(digits):
x = 0
for d in p:
x = x*10 + d
yield x
digits.remove(n)

def prime_pandigitals():
for p in pandigitals():
if is_prime(p):
yield p

def num_digits(n, base=10):
"""
Number of digits for the number 'n' given some 'base'.
"""
if n < 0:
return num_digits(-n, base)
if n < base:
return 1
return 1 + num_digits(n//base, base)

def search():
last = None
num_digits_in_last = None
for p in prime_pandigitals():
if last is None or p > last:
last = p
num_digits_in_last = num_digits(last)
elif num_digits(p) < num_digits_in_last:
return last
return last

``````
``````

In [2]:

import time
t0 = time.time()
t1 = time.time()
print('Elapsed:', t1-t0)

``````
``````

Elapsed: 0.9000570774078369

``````
``````

In [ ]:

``````