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()
print('Answer:', search())
t1 = time.time()
print('Elapsed:', t1-t0)


Answer: 7652413
Elapsed: 0.9000570774078369

In [ ]: