## Project Euler Problem #50

### May 19, 2010

Read the details of the problem here

Summary

Which prime, below one-million, can be written as the sum of the most consecutive primes?

Solution

Another straightforward brute-force solution. Just generate a list of primes (using the usual sieve to start with) and then see what prime values can be attained by adding up subsequent primes whilst remaining under the limit. Keep track of the maximum prime found and that’s that.

```def LIMIT = 999999
def SQRT_LIMIT = (int)Math.sqrt(LIMIT)

def isPrime = new boolean[LIMIT+1]
Arrays.fill(isPrime, true)
(0..1).each { isPrime[it] = false }

for (i in 2..SQRT_LIMIT) {
if (!isPrime[i]) continue
def j = i + i
while (j < LIMIT) {
isPrime[j] = false
j += i
}
}

def primes = (2..LIMIT).findAll { isPrime[it] }

def ( max, answer ) = [ 0, 0 ]

primes.eachWithIndex { prime, idx ->
def ( len, sum ) = [ 1, prime ]
for (i in idx+1..<primes.size()) {
sum += primes[i]
if (sum > LIMIT) break
len++
if ((len > max) && isPrime[sum]) (max, answer) = [ len, sum ]
}
}
```

This runs in 1.93 seconds with the construction of the sieve & prime list taking 1.14 seconds (59%) of that. A Java version completes in 0.12 seconds – only 6x faster as there is a lot of work being done in the Collections libraries in both versions. As they both use Lists for the primes there’s a lot of Integer auto-(un)boxing going on during processing. (Loading the primes into a native int-array drops the Java run time down to a much more respectable 34 ms.)

Conclusion

Groovy made it nice & easy to construct the list of primes from the sieve in a declarative manner, although an explicitly coded loop would be faster. I used an eachWithIndex()

closure for the outer loop but, as I wanted to be able to break out of the inner loop when values exceed the limit, I had to use a normal for-loop there (as I didn’t want to have to use Exceptions to do it). The transparent use of lists in Groovy always makes for a terse syntax.

## 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 }

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

Is this declarative version any clearer?

## 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
}

```

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

## Project Euler Problem #42

### April 28, 2010

Read the details of the problem here

Summary

How many triangle words does the list of common English words contain?

Solution

Another one of the text processing problems that Groovy excels at. Not much to say about the solution as it’s all self-explanatory.

```def answer =
new File("euler_p42_words.txt").text
.replaceAll("\"","").split(",")
.findAll { word ->
def wv = word.collect { c -> ((char)c).charValue() - 64 }.sum()
def sqrt = (int)((wv * 2) ** 0.5)
sqrt * (sqrt + 1) == wv * 2
}.size()
```

This runs in 0.24 seconds.

Conclusion

As mentioned, Groovy is really good to use for solutions like this.

## Project Euler Problem #43

### April 28, 2010

Read the details of the problem here

Summary

Find the sum of all pandigital numbers with an unusual sub-string divisibility property.

Solution

I initially started to do this with a brute-force solution based on permutations but it became quickly apparent that Groovy just wasn’t going to be performant enough to run this sort of solution with 15 seconds.

I then opted to try a recursive solution, where the program attempts to find matching eligible substrings for each of the primes in turn. The “6” in the call to matching() relates to the highest index of the primes array in getCandidates(). It works, though it’s not the most elegant piece of programming!

```def uniqueDigits(s) {
(s.toList() as Set).size()
}

def getCandidates(lvl) {
def primes = [17, 13, 11, 7, 5, 3, 2]
def result = []
for (i in 1..<1000) {
def s = ("000" + i.toString())[-3..-1]
if ((i % primes[lvl] == 0) && (uniqueDigits(s) == 3)) result << s
}
return result
}

def matchSets(p1, p2) {
def res = []
for (s1 in p1) {
p2.findAll { s2 -> (s1[-2..-1] == s2[0..1]) && (!s2.contains(s1[0])) }
.each { res << (s1[0] + it) }
}
return res
}

def matching(lvl) {
if (lvl == 0) return getCandidates(lvl)
return matchSets(getCandidates(lvl), matching(lvl-1))
}

def pandigitals = matching(6).collect {
for (n in "0".."9") {
if (!it.contains(n)) return n + it
}
}

def answer = pandigitals.sum { it.toLong() }
```

This runs in 0.17 seconds. So, not bad considering the mess.

Conclusion

Groovy did quite a good job with this. The syntax was quite terse and the performance adequate. I stayed clear of metaClass extensions which might have improved readability in places as they don’t perform as well as straight method invocations (but given that it ended up being quite fast this was probably unnecessary).

## Project Euler Problem #44

### April 28, 2010

Read the details of the problem here

Summary

Find the smallest pair of pentagonal numbers whose sum and difference is pentagonal.

Solution

Straightforward enough to do, but I ended up having to use Java arrays rather than Groovy lists as performance of the latter was so bad in this scenario. All I do is to create a list of pentagonal numbers and then try to find pairs that match the criteria, preserving the best difference when I find a match. I tried several runs, extending LIMIT on each, until I got an answer.

```def ( LIMIT, answer ) = [ 2500, Integer.MAX_VALUE ]
def penta = new int[LIMIT+1]

for (n in 1..LIMIT) {
penta[n] = (n * (3 * n - 1)).intdiv(2)
}

for (i in 1..<LIMIT) {
def pi = penta[i]
for (j in i+1..LIMIT) {
def pj = penta[j]
def diff = pj - pi
&& (Arrays.binarySearch(penta, diff) > 0)
&& (Arrays.binarySearch(penta, pi + pj) > 0))
{
}
}
}
```

This runs in 3.60 seconds. A Java version takes 273 ms – only 13x faster as much of the work is being done in the Arrays class library in both cass.

Conclusion

I wasn’t able to use Groovy’s lists and listops here are the performance was absolutely dreadful. An equivalent version of this solution using such features had a runtime of 70 seconds.

## Project Euler Problem #45

### April 28, 2010

Read the details of the problem here

Summary

After 40755, what is the next triangle number that is also pentagonal and hexagonal?

Solution

Easy enough using Groovy to use a brute-force set-based approach. Just create three lists containing the numbers in the sets and then use the intersection method to whittle them down, remembering to remove the exemplar before taking the first element from the remainder. (I kept the exemplar in range to make sure the algorithm was working.)

```def ( tri, penta, hexa ) = [ [], [], [] ]

for (n in 143L..<100000L) {
tri   << (n * (n + 1)).intdiv(2)
penta << (n * (3 * n - 1)).intdiv(2)
hexa  <<  n * (2 * n - 1)
}