Project Euler

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]));	
  }
}