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]:
def prime_factors(n): # from eratosthenes
factors = []
d = 2
while n > 1:
while n % d == 0:
factors.append(d)
n /= d
d = d + 1
if d * d > n:
if n > 1:
factors.append(n)
break
return factors
def primes_less_than_n(n):
""" Returns a list of primes < n """
sieve = [True] * n
for i in xrange(3,int(n**0.5)+1,2):
if sieve[i]:
sieve[i*i::2*i]=[False]*((n-i*i-1)/(2*i)+1)
return [2] + [i for i in xrange(3,n,2) if sieve[i]]
max_num_digits = 7
all_primes = primes_less_than_n((10**max_num_digits+1)-1)
max_p = all_primes[-1]
all_primes = set(all_primes)
print len(all_primes)
def is_prime(n):
if n <= max_p:
return n in all_primes
return len(prime_factors(n)) == 1
Misc number theory fact: if 3 | sum of digits of N then 3 | N.
For 4: 10 = 2x5
For 5: 15 = 3x5
For 6: 21 = 3x7
For 7: 28 = 227
For 8: 36 = 223*3
For 9: 45 = 335
So we only need to try 4 and 7 digit numbers.
In [2]:
import itertools
for n in [4,7]:
if n == 5 or n == 6:
continue
d = range(1,n+1)
for p in itertools.permutations(d):
if p[-1] % 2 == 0 or p[-1] == 5:
continue
pt = int("".join([str(i) for i in p]))
if is_prime(pt):
print 'n:',n,'p:',pt
In [ ]: