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

May 20, 2010 at 22:51

[…] 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 […]