Project Euler Problem #50

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

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

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

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

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

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

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.

Project Euler Problem #49

Read the details of the problem here

Summary

Find arithmetic sequences, made of prime terms, whose four digits are permutations of each other.

Solution

Quite straight-forward to do. In this case I made use of the BigInteger.isProbablePrime() method to select the primes rather than creating a sieve as the prime range was fairly limited. It was then a case of grouping them by their sorted sequences and filtering out any that didn’t have any permutations (as well as the exemplar value). It was then just a case of running through the list of permutations for each prime and seeing if three values with the same difference could be found by taking two values at a time and seeing if a suitable third value was present in the list.

def answer = ""

(1003..9997).findAll { BigInteger n -> n.isProbablePrime(100) }
            .groupBy { it.toString().toList().sort().join() }
            .findAll { it.key != "1478" && it.value.size() > 2 }
            .each {
              def p = it.value
              for (i in 0..<p.size()-2) {
                for (j in (i+1)..<p.size()-1) {
                  def p3 = 2 * p[j] - p[i]
                  if (p.contains(p3)) {
                    answer = [ p[i], p[j], p3 ].join()
                  }
                }
              }
            }

This executes in 0.42 seconds. Not particularly fast but good enough for this solution. It could be made faster by causing the loop to break when the answer was found, in this case it would require an exception to be thrown & caught which would just add noise into the solution for such a small benefit.

Conclusion

Groovy listops made it simple to provide declarative filtering for the list of primes and kept the syntax terse in the inner-loops. All-in-all a win for Groovy over straight Java for this particular problem.

Project Euler Problem #48

Read the details of the problem here

Summary

Find the last ten digits of 1¹ + 2² + … + 1000¹⁰⁰⁰.

Solution

It’s a one-liner in Groovy, using the useful BigInteger.modPow() function to raise the base to the required power and then only retain the trailing digits required.

def answer =
    (1G..1000G).sum { it.modPow(it, 10**10) }.toString()[-10..-1]

This executes in 0.11 seconds.

Conclusion

Groovy listops prove their worth once again when combined with Java’s BigInteger support.

Project Euler Problem #47

Read the details of the problem here

Summary

Find the first four consecutive integers to have four distinct primes factors.

Solution

Easy enough. Just use a simple sieve (as we’re not actually interested in what those factors are) to count the number of prime factors for any particular number, looking backwards to see if the last four (including the current one) have the requisite number of factors.

def (f, i) = [ [0] * 1e6, 2 ]

while ((0..3).any { f[i-it] != 4 }) {
  if (f[i] == 0) (i+i).step(f.size(),i) { f[it]++ }
  i++
}

def answer = i - 3

This runs in 3.85 seconds. The size of the sieve is somewhat arbitrary, it just assumes that the answer will be found within a 6-digit range – in fact, in under 500000 due to the (i+i).step(…) statement which would run backwards otherwise! A version that avoid the use of Groovy lists and listops and uses more conventional while-loops run in 1.12 seconds. A Java version runs in…well, it’s just embarrassing…14 ms (so 80x faster).

Conclusion

Again, Groovy provides a quick time-to-solution but at a considerable overhead for the actual runtime.