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.

Advertisements

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: