Project Euler Problem #77

September 4, 2010

Read the details of the problem here

Summary

What is the first value which can be written as the sum of primes in over five thousand different ways?

Solution

Straightforward and quick to solve using the solutions to Problem #31 and Problem #76 as a starter. The values of primes just replace the values of coins from Problem #31. It’s a quick hack to wrap it in a loop that increments total and selects a suitable list of primes to work with on each iteration.

def primes =
    (1..<100).findAll { new BigInteger(it).isProbablePrime(100) }

def ( answer, total ) = [ 0, 11 ]

while (!answer) {

  def nways = [1] + [0]*total

  primes.findAll { it < total }.each { prime ->
    prime.upto(total) { nways[it] += nways[it - prime] }
  }

  if (nways[total] > 5000) answer = total
  total++
}

This runs in 190 ms. It’s not the most efficient of algorithms but it’s well within my 15 seconds target. The length of the prime list was arbitrary but sufficient.

Conclusion

Groovy’s listops made the solution terse to write but nothing that couldn’t be done in normal Java.

Project Euler Problem #76

September 4, 2010

Read the details of the problem here

Summary

How many different ways can one hundred be written as a sum of at least two positive integers?

Solution

Simple to solve using the solution to Problem #31 as a base by just assuming that coins with face values of 1-99 are available (as at least two integers are required). Strictly speaking, of course, it’s not necessary to use the coins array here as all values are present and a simple loop would be adequate – however doing it like this, given I had the previous solution available, shows the similarity between that problem and this one (and appealed to my laziness).

 
def ( total, coins ) = [ 100, (1..<100) ]

def nways = [1] + [0]*total

coins.each { coin ->
  coin.upto(total) { nways[it] += nways[it - coin] }
}

def answer = nways[total]

This runs in 54 ms. A Java version, which doesn’t use a coins array, runs in 220 microseconds – that’s 245 times faster.

After gaining access to the Project Euler forum for this problem, I found that there is a way to solve it in a much more time-efficient manner using partitions. This would provide a far more scalable solution for solving this kind of puzzle for far larger number ranges.

Conclusion

Groovy features made the loops terse to write but not fundamentally different to a normal Java solution.

Read the details of the problem here

Summary

Determine the number of factorial chains that contain exactly sixty non-repeating terms.

Solution

Quite a straightforward programming problem, nothing really mathematical in nature, just a matter of being able to do the processing in a sufficiently efficient manner to meet the 15 second deadline.

My initial attempt just used an array to record which numbers had been seen in the chain (by recording the current number being inspected) but this was taking around 18.3 seconds. As I’d seen on earlier problems Groovy seems to have adverse performance when handling large arrays (more investigation necessary) and it had to be quite large at 6*362880*4 = 8.3+MB (not including overheads) to handle the possible digital sums. Using a native Java method to carry out the summing of the digit factorial reduced the time down to 14.1 seconds but I felt that a better implementation of the chaining algorithm might allow the job to be done wholly in Groovy.

I reimplemented the algorithm building a list of the numbers seen in the chain and this ran fast enough to be acceptable. It used the same technique of caching chain lengths for previous results so that, should that number be seen again, the length of the partial chain can just be appended to the current one.

Integer.metaClass.sumDigitFactorials { ->
  def factorials = [ 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 ]
  def sum = 0
  def str = delegate.toString()
  for (i in str) {
    sum += factorials[i.toInteger()]
  }
  sum
}

def cache = new int[6 * 362880 + 1]
def answer = 0

for (i in 1..<1000000) {

  def len = 0

  if (cache[i] != 0) {
    len = cache[i]
  }
  else {
    def chain = [i]
    def n = i.sumDigitFactorials()

    while ((cache[n] == 0) && !chain.contains(n)) {
      chain << n
      n = n.sumDigitFactorials()
    }

    len = chain.size()
    if (cache[n] != 0) len += cache[n]
    cache[i] = len
  }

  if (len == 60) answer++
}

This runs in 8.3 seconds. A Java equivalent, which uses more usual moddiv functions to calculate the sum of digits runs in around 230 milliseconds (36x faster) and a Java version of the original array-based solution ran in only 270 ms so doesn’t seem to have the odd pathological behaviour of Groovy’s performance with large arrays.

As a matter of record, the sumDigitFactorials() method is called around 1.32 million times during processing so it’s efficiency is important. I tried memoizing the results but it actually had a slight detrimental effect on the run time, so I’m guessing that the cache was relatively sparse and the maintenance overhead outweighed the benefits.

Conclusion

Groovy was slooooow but had some nice language features around the processing of lists that made the solution relatively simple to put together.

Read the details of the problem here

Summary

How many fractions lie between 1/3 and 1/2 in a sorted set of reduced proper fractions?

Solution

This is really just a variant of Problem 71 that I solved using Farey Sequences. I found that I could use the same approach but the implementation proved trickier that I was hoping due to the magnitude of the problem.

I started by simply implementing a recursive version with a function that took the left-hand and right-hand denominators of a Farey pair, and calculated the mediant denominator. If it was within the specified limit it incremented the count and then called itself with the left-hand and mediant denominators, and then mediant and right-hand denominators. Very straightforward…but it blew the call stack.

I switched over to a manual heap-based stack, which is easy to do in Groovy, and used the same algorithm. The code for this is shown below and is very straightforward. However, this ran in 18.9 seconds so quite a way outside my 15 second limit. A port of this to Java ran in around 6 seconds, so I expect that most of the work was being done in the java.util.Vector (or Stack) code which, being synchronized, isn’t the fastest.

def stack = [ [3, 2] ]
def answer = 0

while (stack.size() > 0) {

    def (c, d) = stack.pop()    
    def m = c + d

    if (m <= 12000) {
        answer++
        stack.push( [c, m] )
        stack.push( [m, d] )
    }
}

Though this was sufficient to pass my time-limit criteria I felt that it would be possible to do this using a manually managed stack and avoiding tuples for the pairs. This meant that the code had to be changed somewhat and just preserved the right-hand denominator of the Farey pair. The code for this is shown below.

def ( stack, top ) = [ new int[12000], 0 ]
def ( c, d ) = [ 3, 2 ]
def answer = 0

while (true) {
    def m = c + d
    if (m <= 12000) {
        answer++
        stack[top++] = d
        d = m
    }
    else {
        if (top == 0) break
        c = d
        d = stack[--top]
    }
}

This runs in 6.0 seconds and so satisfies my success conditions! A Java version of this runs in 83.5 milliseconds (so around 70x faster – as I’ve come to expect from Groovy for computationally intensive programs).

Conclusion

The Groovy capability of using tuples and stacks meant that it was easy to create the initial heap-based stack solution albeit not particularly performant. The final solution didn’t really use any specific Groovy features.

Read the details of the problem here

Summary

Listing reduced proper fractions in ascending order of size.

Solution

This problem reminded me of the Achilles and the Tortoise Paradox in that everything must reach a half-way stage before reaching a final destination. As there are an infinite amount of half-way points you’d never arrive at the destination. In essence it’s possible to solve this problem by calculating the half-way points between the two fractions given…well, not exactly but it makes for a nice story!

In the realm of reduced fractions this is called a Farey Sequence. As you’ll see though they aren’t exactly half-way points, they are called mediants and are just created from adding the numerator and denominator of neighbouring terms.

So seeing how it works for this problem. The whole fractional space (if you can call it that) lives between 0 and 1 or, for this purpose, 0/1 and 1/1. This is a Farey sequence of order 1 (the highest denominator in use).

0                          1
-..........................-   
1                          1

Just partition the space according the mediant rules a/c + b/d = (a+b)/(c+d). This creates a Farey sequence of order 2.

0            1             1
-............_.............-   
1            2             1

This problem is interested in values less than 1/2 (as 3/7 < 1/2) so just partition again to the left hand side. Giving an order 3 sequence.

0     1      1             1
-....._......_.............-   
1     3      2             1

And again. This time to the right of the 1/3 as 2/5 > 1/3.

0     1  2   1             1
-....._.._..._.............-   
1     3  5   2             1

Repeat to the right of the 2/5 to get the 3/7 that the problem is expecting as the upper bound. This means that, in a Farey Sequence of order 7, 2/5 and 3/7 are neighboring terms (also known as a Farey Pair).

0     1  2 3 1             1
-....._.._._._.............-   
1     3  5 7 2             1

So, to solve this problem it’s just necessary to keep performing this calculation between 2/5 and 3/7, adding 3/7 each time to the resulting fraction, whilst the denominator doesn’t exceed 1,000,000.

So the next few terms would be:

    2/5 + 3/7 = 5/12,

    5/12 + 3/7 = 8/19,

    8/19 + 3/7 = 11/26, etc.

The coding is extremely straightforward.

def ( answer, c ) = [ 2, 5 ]
def ( b, d ) = [ 3, 7 ]

while (c + d <= 1000000) {
    answer += b
    c += d
}

This is another one of those Euler questions that goes to show it’s worth knowing a few little tricks like this rather than relying on brute force for a solution.

The program runs in 0.17 seconds, easily within my time limit.

Note: It’s actually not really necessary to write a program to solve this at all. From the algorithm above, it’s obvious that the solution is (2+3n)/(5+7n) where the denominator is limited by 1,000,000, and so 7n < 999,995. 999,992 is divisible by 7, giving a denominator of 999,997 and n =142856. Just plugging this into the formula for the numerator gives the answer.

Conclusion

As it was Groovy didn’t play any significant part in this solution. It just required simply addition which Groovy is quite capable of handling in a performant manner.

Project Euler Problem #80

January 21, 2010

Read the details of the problem here

Summary

For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all the irrational square roots.

Solution

My initial thought on this was that Java’s BigDecimal class would offer a high-precision square root method but, but my disappointment, it didn’t. However, whenever arbitrary precision square roots come up, I always remember Newton’s method as this was something I learnt when I was interested in fractals years ago — generating Newton’s patterns as graphics on my BBC micro (which used to run for hours). From there it was a quick check on Wikipedia to remind myself of the details of Newton’s Method which I then coded as an extension to BigDecimal. Once that was done the solution was very straightforward.

BigDecimal.metaClass.sqrt() { scale ->
    def (x0, x1) = [ 0.0G, delegate ** 0.5 ]
    while (!x0.equals(x1)) {
        x0 = x1
        x1 = delegate.divide(x0, scale, BigDecimal.ROUND_HALF_UP)
                     .add(x0)
                     .divide(2.0G, scale, BigDecimal.ROUND_HALF_UP)
    }
    return x1
}

def answer = (1..100).sum {
    [1, 4, 9, 16, 25, 36, 49, 64, 81, 100].contains(it) ? 0 :
            new BigDecimal(it).sqrt(101).toString()[0,2..-3].toList()*.toInteger().sum()
}

This completed in 0.77 seconds. Slow for Java, but fine for this solution.

One little problem I had was that I didn’t read the question correctly, initially I assumed that it was the first 100 decimal digits that needed to be summed but a test against 2 ^ 0.5 showed that not to be the case. I also found that it was necessary to extend the scale a little further than might be obviously required otherwise there was a rounding error creeping in, hence the –3 for the tail index, rather than the –2 that you might expect.

Overall quite a fun little problem. Mostly programming rather than mathematical assuming that you’re aware of Newton’s Method.

Conclusion

Groovy really did make this solution quite nice to write. The ability to extend the BigDecimal class makes for a good clear syntax. The way that substring extraction can specify multiple ranges and the spread-dot operator for character conversion made this solution almost a one liner. The Java solution wouldn’t have been much more verbose but would have been a little more cryptic.