Problem 041

Project Euler

Pandigital prime

Problem 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?

First, the largest pandigital number is 987654321. Also, a quick way to know if a number is divisible by 3 is to see if the sum of all the digits is divisible by 3. Therefore, we can check each n-digit pandigital to see if it is possible to contain a prime.

Nay 1+2 = 3
Nay 1+2+3 = 6
Yes 1+2+3+4 = 10
Nay 1+2+3+4+5 = 15
Nay 1+2+3+4+5+6 = 21
Yes 1+2+3+4+5+6+7 = 28
Nay 1+2+3+4+5+6+7+8 = 36
Nay 1+2+3+4+5+6+7+8+9 = 45

Therefore, we should only search 4-digit and 7-digit pandigital number. Since we are looking for the largest pandigital prime, we should start the search at 7654321 and decrement the value by 2 (odd number only) until we found a number that is also a prime. By re-using the prime sieve from problem 37 and the pandigital checker from problem 38, this problem can be solve very quickly.