## Project Euler Problem #53

### May 19, 2010

Read the details of the problem here

**Summary**

How many values of C(n,r), for 1 ≤ n ≤ 100, exceed one-million?

**Solution**

From the look of the question it appeared that it was going to require a lot of multiplication and division of the fairly non-performant BigIntegers as *n!* gets very large, very quickly. As per other problems of this nature it seemed that using log values might be better.

This would involve reformulating the combinations equation as

*log(n!)-(log(r!)+log((n-r)!)* so quite straightforward really. In order to reduce the time spent calculating factorials (and their logs) I just initialised them into an array up front rather than using any special memoization technique.

The actual summation was then easy to do with Groovy listops.

def MAXNUM = 100 def LIMIT = Math.log10(1e6) def fact = new double[MAXNUM+1] (0..1).each { fact[it] = Math.log10(1) } for (i in 2..MAXNUM) { fact[i] = Math.log10(i) + fact[i-1] } def answer = (1..MAXNUM).sum { n -> (1..<n).findAll { r -> fact[n] - (fact[r] + fact[n-r]) > LIMIT } .size() }

This runs in just under 80 ms which seems quite reasonable given that it’s essentially a listop-based declarative solution.

**Conclusion**

Groovy’s features made the creation of this solution quite simple and was surprisingly performant.