## 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)) {
for (j in 0..SQRT_LIMIT.intdiv(2)) {
def r = (i - 2 * (j * j)).toBigInteger()
if (r.isProbablePrime(100)) {
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 }