## Project Euler Problem #51

### January 19, 2010

Read the details of the problem here

**Summary**

Find the smallest prime which, by changing the same part of the number, can form eight different primes.

**Solution**

This was more of a programming challenge than a mathematical one. The logic was quite simple. To begin with I assumed that a 6-digit number was going to be required so the range of primes to check was 100003-999983 (which I used the usual sieve to generate). I also figured that the least significant digit can’t be one that would be swapped as this would never allow eight primes to be formed. It also appeared that leading-zeroes were not going to be permitted, though this isn’t mentioned explicitly in the question. So this then became simply a matter of looking through for a triplet of numbers, in the first five-digits of the prime that could be exchanged for a total of eight primes. As there were to be eight combinations it was only necessary to check up for initial triplets of “0”, “1” or “2”.

def isPrime = new boolean[1000000] Arrays.fill(isPrime, true) isPrime[1] = false for (i in 2..isPrime.size()**0.5) { if (isPrime[i]) { def j = i + i while(j < isPrime.size()) { isPrime[j] = false j += i } } } def (answer, i) = [ 0, 100001 ] while ((i < isPrime.size()) && (answer == 0)) { if (isPrime[i]) { def s = i.toString() def s1 = s[0..-2] for (n in "0".."2") { if (s1.findAll { it == n }.size() == 3) { def c = 0 for (j in n.."9") { def pp = (s1.replace(n, j) + s[-1]).toInteger() if ((pp > 99999) && isPrime[pp]) c++ } if ( c == 8 ) answer = i break } } } i++ }

This completed in 0.88 seconds with the sieve taking about 0.71 seconds.

**Conclusion**

Groovy’s range operators made this quite nice to do, allowing specification of ranges in terms of characters without requiring explicit casting or conversion. In fact, I did initially do this but it actually added to the runtime and this syntax is nicer and more intention revealing. The **findAll()** listop made it easy to count the digits to select eligible initial primes.