## 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)) { 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?

## 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 } def answer = primes.max()

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 if ( (diff < answer) && (Arrays.binarySearch(penta, diff) > 0) && (Arrays.binarySearch(penta, pi + pj) > 0)) { answer = diff } } }

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) } def answer = (tri.intersect(penta) .intersect(hexa) - [40755] )[0]

This runs in 0.79 seconds. The upper bound on the creation of the lists was somewhat arbitrary and, once the answer is known, can be reduced which obviously brings the runtime down.

**Conclusion**

Groovy made this quite simple to write by using the list set operators. Performance was adequate for the scale of the solution. Note that it’s important to use the Long (L) suffix on the numbers in the loop to prevent subsequent overflow in the bodies of the calculations.