Project Euler 41: What is the largest n-digit pandigital prime that exists?

Written by on 10 May 2011

Topics: Project Euler

This time we mix two old topics together and form a new question. This time Project Euler has mixed pandigital numbers and primes and Problem 41 asks us to find the largest such number. The problem description reads

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?

I will start solving it by brute force and as we shall see the approach is possible but very inefficient, so after that I will show you how to speed the process up by using a small property of numbers that I was taught in 4th grade or so – And no, I am not particularly gifted, the trick is just really simple.

Brute Force

We already have methods for generating prime numbers and checking if a number is pandigital, so all we need is to combine those.

The C# code for the problem looks like

int[] primes = ESieve(987654321);
int result = 0;

for (int i = primes.Length - 1; i >= 0; i--) {
    if(isPandigital(primes[i])){
        result = primes[i];
        break;
    }
}

I generate all primes up to 987654321 which is the largest number that can be pandigital and then loops through them until I find a prime. The only problem is that the execution of the algorithm takes 27 seconds. The result is

The largest Pandigital prime is 7652413
Solution took 27057 ms

That is just not good enough. I know it is within the 1 minute limit proposed by Project Euler, but it isn’t satisfactory for me, so We will have to slightly revise the method.

Digit sum

The trick I learned in 4th grade was that a number is divisible by 3 if and only if the digit sum of the number is divisible by 3. The digit sum is as the name implies the sum of the digits. We can rather easily find the digit sum of pandigital numbers since we know the digits.

1+2+3+4+5+6+7+8+9 = 45

1+2+3+4+5+6+7+8 = 36

1+2+3+4+5+6+7 = 28

1+2+3+4+5+6 = 21

1+2+3+4+5 = 15

1+2+3+4 = 10

1+2+3 = 6

1+2 = 3

From here it is pretty clear that all pandigital numbers except 4 and 7 digit ones are divisible by 3 and thus can’t be primes.  I have chose the lazy method and just lowered the upper limit of the prime generation to 7654321 in the previous example which then gives us a running time of 68ms which gives us a factor 400 in speed up.

Wrapping up

I am pretty sure I could speed up the second part even more if I didn’t use a Sieve method to generate primes, but it is an easy way to do it and the result is pretty fast.

Just for the curious people there is a total of 538 pandigital primes only 4 of those are 4 digit, the rest is 7 digits.

As usual you can find all the code details in the uploaded source code. Did you choose another solution strategy? If so please let me know about it.

12 Comments For This Post I'd Love to Hear Yours!

  1. Pubudu says:

    I tried it the other way.. first generating the permutations, from the highest possible (987654321), checking each number to see if it’s a prime… it runs in 0.08 seconds (according to ideone) when i start it from k=9 (all 9 digits) but runs in no time at all, when started from 7 (ideone gave as 0 seconds), after considering the fact that 8 and 9 digit pandigital numbers arent primes..

    #include <stdio.h>
    #include <math.h>
    #include <string.h>
    #include <stdint.h>
    //#include <inttypes.h>
    
    int used[10] = {0}; // used this array to keep track of numbers which were used in building up a number
    char num[12]; // the number that will be built will be saved in this
    int count = 0;
    int found = 0; // flag to mark that the solution was found;
    
    void generate(int,int,int); // function to generate the permutations
    int isPrime(uintmax_t);
    
    int main(){
        int i,j,k;
        
        for(k=9; k>=1; k--){ // keep on reducing the no of digits used.. starting with k=9 since we are looking for the max prime
            for(i=k,j=0; i>=1; i--){ // loop for producing the permutation of each size k..
                used[i] = 1;
                num[j] = i+'0';
                num[j+1] = '\0';
                generate(k,i,j);
                used[i] = 0;
            }
        }
        return 0;
    }
    
    void generate(int k,int n,int j){
        if(!found && strlen(num)==k){
            if(isPrime(atoi(num))){
                printf("%d\n",atoi(num));
                found = 1;
            }
            return;
        }
        
        int i;
        for(i=k; i>=1; i--){
            if(!used[i]){
                used[i] = 1;
                num[j+1] = i+'0';
                num[j+2] = '\0';
                generate(k,i,j+1);
                used[i] = 0;
            }
        }
    }
    
    int isPrime(uintmax_t n){ // an algorithm from this site as i remember..
        if(n%2==0 || n%3==0)
            return 0;
        uintmax_t x = (int)sqrt(n);
        uintmax_t i;
        for(i=1;(6*i-1)<=x;i++){
            if(n%(6*i-1)==0)
                return 0;
            
            if(n%(6*i+1)==0)
                return 0;
        }
        return 1;
    }
    
  2. Kristian says:

    Nice speedup when you use that method. It does make sense that it would be more efficient doing it that way, thanks for the code.

  3. Kuba says:

    Hi,
    knowing, that the permutations 1..7 will be the right ones, I used algorithm from P.E. 24 to generate all permutations of 1..7 and then from the top (7654321) was checking, if the number is a prime. When I found the first, I simply break :).

  4. Sonali says:

    Kuba’s one is the most efficient I think..

  5. Julian says:

    I realised that the number had to be seven digits using pen-and-paper which I won’t describe here. I hence decided to generate primes from 7000000 to 7654321 on the off-chance the solution was above 7000000 (it was my lucky day). This generation is very quick.

    I next created a rudimentary IsPandigital function which I am still not happy with – it is messy and looks ugly, but hey – it’s 2am!

    I iterate down from 7654321 until the number is both Pandigital and Prime. This is obviously the answer.

    My solution runs in 2 milliseconds, by far one of the quickest solutions I’ve made yet.

    I popped the source code on pastebin here.

    I’m sure further optimisations could be made but I was happy with this result.

    Cheers
    Julian

  6. Gary Walker says:

    Probably a classic example of dumb luck. I do the Euler problems in Python since my motivation was to improve my Python skills. I start with a dumb algorithm if is seems reasonable and improve it.

    But instead of generating primes with a sieve, or generating all pandigitals, I just started with 7654321 counting down by 2. I first test if pandigital() and then for primality(). Ran so fast I was sure it was wrong till I checked it.

    The solution just happens to be so close to the starting point my algorithm checked less than 1000 candidate number before terminating.

    I had expected to write the code to generate pandigital numbers directly in descending order … but it seemed pointless in this case.

  7. zakariae says:

    hello , i get this number : 7652483

    it’s a prime number and is a 7-digit pandigital :

    why the solution is 7652413 and not 7652483.

    my program looks like:

    def isPandigital(n1):
        liste = [0,0,0,0,0,0,0,0,0,0]
        #print liste
        temp = n1;
        while temp &gt; 0:
            liste[temp % 10]+=1
            temp /= 10
        #print liste
        #print &quot;here we are&quot;
        i=0
        firstOcu = 0
        lastOcu  = 0
        while i &lt; len(liste):
            #print liste[i]
            if liste[i]==1 and firstOcu==0:
                firstOcu=i
            if liste[i]==1 and firstOcu!=0:
                lastOcu=i
            if liste[i] &gt;1:
                return False
            i+=1
        #print str(firstOcu)+&quot; et &quot;+str(lastOcu)
        j=firstOcu
        while j&lt;= lastOcu:
            if liste[j]==0:
                return False
            j+=1    
                
        return True
    def isPrime(n):
        entier = n/2
        j=2
        while j &lt;= entier:
            if n % j == 0:
                return False;
            j=j+1
        return True
    max = 7654210
    i   = 7652410
    while max&gt;=i:
        if isPrime(max)==True and isPandigital(max) :
            print max
        max=max-1
    
    
  8. Trystan says:

    The reason why 7652413 and not 7652483 is the 8. I didn’t notice it at first but rereading very carefully it says 1 to n, so with a 7 digit number, it’s 1 to 7. The 2nd number has an 8 which is outside of that range and does not have a 1.

  9. Chris says:

    I think this is one of those moments when the C++ Standard Library really shines. It makes for very readable, but still efficient code. The following solves the problem in 0.002 seconds.

    #include &lt;iostream&gt;
    #include &lt;algorithm&gt;
    using namespace std;
    
    bool isPrime(int i)
    {
    	for(int j = 2; j &lt;= sqrt(abs(i)); ++j)
    	{
    		if(i%j == 0) return false;
    	}
    	return true;
    }
    
    int main()
    {
    	string pan=&quot;7654321&quot;;
    	do {
    		int i=stol(pan);
    		if(isPrime(i)) break;
    	} while(prev_permutation(pan.begin(), pan.end()));
    	cout &lt;&lt; pan &lt;&lt; endl;
    	return 0;
    }
    
  10. Chris says:

    Looks like it mangled my lessthans and greaterthans. 🙁

  11. Julian says:

    I used some ideas of this blog.
    The correct solution was calculated in 15 ms.

    final int uBound = 7654321;
    int largest = 0;
    int halfSqrt = ((int)Math.sqrt(uBound)-1)/2;
    int halfBound = (uBound-1)/2;
    BitSet cache = new BitSet();
    cache.set(0, halfBound+1, true);
    
    // ESieve
    for(int i = 1; i <= halfSqrt; i++){
    	if(cache.get(i)){
    		for(int del = 2*i*(i+1); del < halfBound; del += 2*i+1){
    			cache.set(del,false);
    		}
    	}
    }
    
    		
    for(int k = halfBound-1; k >= 1; k--){
    	if(cache.get(k)){
    		int tmpPrime = k*2+1;
    				
    		// if the prime is in the range of 4 or 7 digits
    		if((tmpPrime >= 1234567 && tmpPrime <= 7654321) || (tmpPrime >= 1234 && tmpPrime <= 4321)){
    			if(this.isPandigital(tmpPrime, tmpPrime > 4321 ? 7 : 4)){
    				largest = tmpPrime;
    				break;
    			}
    		}
    	}
    }
    
  12. Maximus says:

    Even though I used Python, I want to say that I checked a number for being prime by creating a list of its factors and checking the length. It was pretty fast.

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.