(35 votes, average: 5.00 out of 5)

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

Runs < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 41 Solution Python 2.7 source.
HackerRank version runs in under a second and a half for 100,000 trials. Here we generate a list of 7 and 4 digit prime numbers from largest to smallest and keep only the ones that test as a pandigital number. Then we host queries against this list and report an answer.

```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`.
Project Euler 41 Solution last updated

## Discussion

### 2 Responses to “Project Euler 41 Solution”

1. This is a good question. You could even ask why not seven-digit prime numbers with only the digits 1-7 in them. We’re not really sure how much overhead that would generate and by counting backwards from 7654321 will find it without any lists. In fact, it took only 954 iterations.

I did change the looping structure to make it look cleaner.

Posted by Mike | May 12, 2011, 9:46 AM
2. Why not just check the permutations of 1…7 instead of looping through all numbers?

Posted by shafaet | May 12, 2011, 2:27 AM