Pandigital prime

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?

Idea

Fisrt of all, $ n \le 9 $.

  • If n = 9, then $ \sum_{i=1}^{n} i = 45 $, and $ 45 \bmod 3 = 0 $, which means 9-digit pandigital cannot be prime.
  • If n = 8, same as n = 9
  • So largest n-digit pandigital prime might start with 7, and is 7-digit pandigital
  • And last digit of multi-digits prime could only be 1 or 3 (for 7-digit pandigital)
In [1]:
from itertools import permutations
from functools import reduce
from math import sqrt
In [2]:
def get_digits(last):
    return [6, 5, 4, 3, 2] if last == 1 else [6, 5, 4, 2, 1]
In [3]:
def combine_digits(digits):
    return reduce(lambda n, d: n*10+d, digits, 0)
In [4]:
combine_digits([1,2, 3])
Out[4]:
123
In [5]:
def is_prime(n):
    # n is already not even
    assert n % 2 != 0
    return all((n % i for i in range(3, int(sqrt(n))+1, 2)))
In [6]:
is_prime(11)
Out[6]:
True
In [7]:
is_prime(49)
Out[7]:
False
In [8]:
def solve():
    highest = 7
    for last in [3, 1]:
        for p in permutations(get_digits(last)):
            n = combine_digits((highest, ) + p + (last, ))
            if is_prime(n):
                return n
In [9]:
solve()
Out[9]:
7652413