(20 votes, average: 5.00 out of 5)

## Project Euler Problem 41 Solution

#### Problem Description

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

What is the value of n? We know it’s between 4 and 9 but that leaves a huge set of prime number candidates to search through. So let’s eliminate some values of n by using the rule that any integer is divisible by 3 or 9 whose sum of digits is divisible by 3 or 9; therefore composite and not prime.

9+8+7+6+5+4+3+2+1 = 45,
8+7+6+5+4+3+2+1 = 36,
6+5+4+3+2+1 = 21, and
5+4+3+2+1 = 15,
all of which are divisible by 3 and therefore could not yield a 1 to {5, 6, 8, 9} pandigital prime. So that leaves 4 and 7 digit prime numbers less than 4321 and 7654321 respectively. Since we want the largest pandigital prime we’ll check the 7 digit group first.

#### Solution

Runs < 1 second in Python.

```from Euler import is_prime, is_pandigital   n = 7654321 while not(is_prime(n) and is_pandigital(n, 7)): n-=2 print "Answer to PE41 = ", n```

• BTW, the largest 4 digit pandigital prime is 4231.
• More information on the Euler module can be found on the tools page.

## Discussion

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

1. Why not just check the permutations of 1…7 instead of looping through all numbers?

Posted by shafaet | May 12, 2011, 2:27 AM
2. 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 955 iterations.

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

Posted by Mike | May 12, 2011, 9:46 AM