## 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
}

```

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()
```