Project Euler Problem #41

May 18, 2010

Read the details of the problem here

Summary

What is the largest n-digit pandigital prime that exists?

Solution

Straightforward brute force solution. It’s not possible to have 8 or 9 digit pandigital primes as the sum of integers in each case is divisible by three (either 36 or 45 respectively) and hence the number itself would be divisible by 3. Rather than generating a sieve of primes and then checking for pandigitals it seems better to generate permutations of pandigitals and then check for primality. This means that I can just use BigInteger#isProbablePrime() and hope that the performance will be OK for this purpose as there are only some 5,040 permutations.

def permutations(val, yield) {
    permutations(0, -1, val, yield)
}

def permutations(k, id, val, yield) {
    id++
    val[k] = id
    if (id == val.size()) yield(val)
    for (t in 0..<val.size()) {
        if (val[t] == 0) permutations(t , id, val, yield)
    }
    id -= 1
    val[k] = 0
}

def primes = []

permutations([0]*7) {
    def n = it.join("").toBigInteger()
    if (n.isProbablePrime(100)) primes << n
}

def answer = primes.max()

This runs in 0.42 seconds. Quite satisfactory for the scale of this problem. I could have made it more efficient by searching downwards through the permutations – the generator I used just does it in numerical order – and breaking at the first one found.

Conclusion

Groovy’s support for listops, closures and tight integration with Java made this solution very straightforward to create.

Update: In Groovy 1.7, List has had a permutations() method added to it which returns an unordered list of all the permutations for elements in the collection. Using this feature reduces the code down to that shown below and the runtime drops to 0.18 seconds. Nicely done.

def answer = 
  (1..7).toList()
        .permutations()
        .collect { it.join().toBigInteger() }
        .findAll { it.isProbablePrime(100) }
        .max()

Advertisements

One Response to “Project Euler Problem #41”


  1. […] of the string that it’s given. The implementation is pretty much the same as that for Problem 41. (Note: This callback is also used by other generators hence the non-specific Object […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: