Project Euler Problem #46

May 18, 2010

Read the details of the problem here

Summary

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

Solution

Pretty straightforward solution. Just subtract twice a square from a candidate set of numbers and see if the number is a prime. For this fairly limited scope I made use of BigInteger#isProbablePrime() rather than building a sieve. As twice the square is always going to be even, and I’m going to need an odd number for the prime I only check through the odd numbers for the range.

def LIMIT = 9999
def SQRT_LIMIT = (int)Math.sqrt(LIMIT)
def ( answer, i ) = [ 0, 1 ]

while ((i < LIMIT) && (answer == 0)) {
  answer = i
  for (j in 0..SQRT_LIMIT.intdiv(2)) {
    def r = (i - 2 * (j * j)).toBigInteger()
    if (r.isProbablePrime(100)) {
      answer = 0
      break
    }
  }
  i += 2
}

This runs in 0.72 seconds. Making use of a sieve instead brings the runtime down to 93 ms – quite a time saving but at the expense of substantially more code. The range limit was a bit of a guess but proved valid.

Conclusion

Groovy didn’t really help or hinder with this, apart from allowing a somewhat terser syntax than Java.

As a matter of curiosity I wrote a version that made use of listops and it actually ran somewhat faster than the original – 0.55 seconds.

def LIMIT = 9999
def SQRT_LIMIT = (int)Math.sqrt(LIMIT)

def primes =
    (1..LIMIT).findAll { it.toBigInteger().isProbablePrime(100) }
def nums =
    (3..LIMIT).findAll { (it & 1) == 1 }
def tsqr =
    (0..SQRT_LIMIT.intdiv(2)).collect { 2 * it * it }

def answer =
    nums.findAll { i ->
        tsqr.every { !primes.contains(i - it) } }.min()

Is this declarative version any clearer?

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: