Project Euler 41: Find the largest n-digit pandigital prime that exists

Project Euler 41 Problem Description

Project Euler 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?

Analysis

This problem asks us to investigate the realm of pandigital numbers for the largest prime. An obvious question is: what is the value of n in n-digit pandigital prime? We know it’s between 4 and 10 but that leaves a huge set of prime number candidates to search through. So let’s eliminate some values of n by using the divisibility rule which states that an integer is divisible by 3 whose sum of digits is divisible by 3 and therefore composite and not prime.

9+8+7+6+5+4+3+2+1+0 = 45, 45/3 = 15
9+8+7+6+5+4+3+2+1 = 45, 45/3 = 15
8+7+6+5+4+3+2+1 = 36, 36/3 = 12
7+6+5+4+3+2+1 = 28, 28/3 = 9.333…
6+5+4+3+2+1 = 21, 21/3 = 7
5+4+3+2+1 = 15, 15/3 = 5
4+3+2+1 = 10, 4/3 = 1.333…
3+2+1 = 6, 6/3 = 2
2+1 = 3 3/3 = 1

Only pandigital numbers of length 4 and 7 can form a prime number. The others cannot because any combination of their digits will sum to a number divisible by 3 as affirmed by the commutative law of addition. So that leaves us to search odd 4 and 7 digit pandigital numbers for a prime number less than 4321 and 7654321 respectively. We also know that the candidate must end with a 1, 3, or 7 to be considered as a possible prime number, but this turned out to be of little consequence. Since we want the largest pandigital prime we’ll start with 7 digit numbers.

The result is quickly found by the 954th iteration of our investigation. Starting with 7654321 we check each decreasing odd number for being pandigital and prime. The first number meeting both these conditions is our solution.

The HackerRank Project Euler 41 version wants us to find the largest n-digit pandigital prime below some limit, N < 10¹⁰-1 with up to 100,000 trials per test case. This is a more compelling problem to solve and required a modified solution to meet the time constraints.

This program and method
solves all test cases for
Project Euler 41 on HackerRank

Project Euler 41 Solution

from Euler import is_pandigital, prime_sieve
def fn(n):
    for px in p:
        if px<=n: return px
    return -1

p=[k for k in prime_sieve(7654321)[::-1] if k>1000000 and is_pandigital(k, 7)]
p+=[k for k in prime_sieve(4321)[::-1] if k>1000 and is_pandigital(k, 4)]

k = int(input('Find the first pandigital prime below? '))
print fn(k)

Afterthoughts

• BTW, the largest 4 digit pandigital prime is 4231.
  
• Functions prime_sieve, is_prime, is_pandigital are listed in Common Functions and Routines for Project Euler
  
• Swapping (is_prime(n) and is_pandigital(n, 7)) with (is_pandigital(n, 7) and is_prime(n)) sped up the program by a factor of 10 because the is_pandigital function is much faster than the is_prime function. IF statements for most languages stop checking ‘AND’ Boolean expressions after finding a previous one returns false. So, if is_pandigital fails, Python stops checking other expressions in the IF statement such as the more ‘expensive’ is_prime.