# Project Euler

### A Taste of Number Theory

#### Problem 41: Pandigital Prime

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?

#### The Catch

How to check if a number is pandigital.
How to efficiently check if pandigital numbers are also prime, since checking from 2 to 978,654,321 is extremely time consuming.

#### The Light

A pandigital number uses each digit from 1 - 9 exactly once, thus there are essentially 9 "templates" for pandigital numbers. The only 1-digit pandigital number is 1. If you take the digits from any 2-digit pandigital number and sort them numerically, you will get 12. Similarly, if you take the digits from any 3-digit pandigital number and sort them numerically, you will get 123. This concept applies for all pandigital numbers, so make 9 static template pandigital numbers. To check if a number with n-digits is pandigital, sort all digits numerically and if the result matches with n-digit template, then the number is pandigital.

Recall that a number is divisible by 3 if and only if the digit sum of the number is divisible by 3. The list below shows that only 4-digit and 7-digit pandigital numbers can be prime, since the others are divisible by 3. Thus first check from the largest 7-digit pandigital number downward for the largest instance of a pandigital-prime-number. If it is not found, move to the 4-digit numbers range.

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

Since primes are odd, eliminate all even numbers in the search to speed up execution. Use discussion in Problem 3 to check for prime numbers.

#### The Code

```import java.util.*;

public class Problem41
{
public static char[][] p = {"1".toCharArray(), "12".toCharArray(),
"123".toCharArray(), "1234".toCharArray(),
"12345".toCharArray(), "123456".toCharArray(),
"1234567".toCharArray(), "12345678".toCharArray(),
"123456789".toCharArray()};

public static void main(String[] args)
{
for(int i = 7654321; i > 1000000; i -= 2)
{
if(isPan(i))
if(isPrime(i))
{
System.out.println(i);
break;
}
}
}

public static boolean isPrime(int n)
{
if(n < 2)
return false;

if(n != 2 && n % 2 == 0)
return false;

for(int i = 3; i * i < n; i++)
{
if(n % i == 0)
return false;
}

return true;
}

public static boolean isPan(int n)
{
String s = Integer.toString(n);
char[] c = s.toCharArray();
Arrays.sort(c);
return (Arrays.equals(c, p[c.length - 1]));
}
}
```